- Joined
- Apr 24, 2012
- Messages
- 5,113
Work In Progress
I'm currently writing this to improve my flocking system and possibly to write the GetClosestTile lib
JASS:
library Quadtree/* 1.0 by Almia
*************************************************************************************
*
* For map partitioning
*
*************************************************************************************
*
* */ uses /*
*
* */ AABB /*
*
* */ Table /*
*
*************************************************************************************
*
* API
*
*
*************************************************************************************/
//! textmacro QUADTREE
globals
private constant integer VALUE_CAPACITY = 4
private constant real MINIMUM_WIDTH = 16
private constant real MINIMUM_HEIGHT = 16
endglobals
private struct Point
real x
real y
integer data
endstruct
private struct Quadtree
readonly AABB bounds
readonly boolean hasChildren
readonly thistype NE
readonly thistype NW
readonly thistype SE
readonly thistype SW
readonly integer size
private Table values
static method create takes real x, real y, real halfWidth, real halfHeight returns thistype
local thistype this = allocate()
set bounds = AABB.create(x, y, halfWidth, halfHeight)
set hasChildren = false
set size = 0
set values = Table.create()
return this
endmethod
method subdivide takes nothing returns nothing
local real halfWidth
local real halfHeight
if not hasChildren then
set halfWidth = bounds.halfWidth/2
set halfHeight = bounds.halfHeight/2
if halfWidth >= MINIMUM_WIDTH and halfHeight >= MINIMUM_HEIGHT then
set NE = create(bounds.centerX + halfWidth, bounds.centerY + halfHeight, halfWidth, halfHeight)
set NW = create(bounds.centerX - halfWidth, bounds.centerY + halfHeight, halfWidth, halfHeight)
set SE = create(bounds.centerX + halfWidth, bounds.centerY - halfHeight, halfWidth, halfHeight)
set SW = create(bounds.centerX - halfWidth, bounds.centerY - halfHeight, halfWidth, halfHeight)
set hasChildren = true
endif
endif
endmethod
method subdivideAll takes nothing returns nothing
local thistype array sstack
local thistype i
set sstack[0] = this
loop
set i = sstack[0]
exitwhen i == 0
if i.hasChildren then
set sstack[i.NE] = sstack[i]
set sstack[i.NW] = i.NE
set sstack[i.SE] = i.NW
set sstack[i.SW] = i.SE
set sstack[0] = i.SW
else
call i.subdivide()
set sstack[0] = sstack[i]
endif
endloop
endmethod
method get takes real x, real y returns integer
local integer i
local Point p
if bounds.containsPoint(x, y) then
set i = 0
loop
exitwhen i == VALUE_CAPACITY
set p = Point(values[i])
if p.x == x and p.y == y then
return p.data
endif
set i = i + 1
endloop
endif
return 0
endmethod
method getAll takes real x, real y returns integer
local thistype array gstack
local thistype i
local integer temp
set gstack[0] = this
loop
set i = gstack[0]
exitwhen i == 0
set temp = i.get(x, y)
if temp == 0 then
set gstack[0] = gstack[i]
if i.hasChildren then
set gstack[i.NE] = gstack[0]
set gstack[i.NW] = i.NE
set gstack[i.SE] = i.NW
set gstack[i.SW] = i.SE
set gstack[0] = i.SW
endif
else
return temp
endif
endloop
return 0
endmethod
method insert takes real x, real y, integer value returns boolean
local Point p
if bounds.containsPoint(x, y) and size < VALUE_CAPACITY then
set p = Point.create()
set p.x = x
set p.y = y
set p.data = value
set values[size] = p
set size = size + 1
endif
return false
endmethod
method insertAll takes real x, real y, integer value returns boolean
local thistype array istack
local thistype i
set istack[0] = this
loop
set i = istack[0]
exitwhen i == 0
if i.insert(x, y, value) then
return true
elseif i.bounds.containsPoint(x, y) then
call i.subdivide()
set istack[i.NE] = istack[i]
set istack[i.NW] = i.NE
set istack[i.SE] = i.NW
set istack[i.SW] = i.SE
set istack[0] = i.SW
else
set istack[0] = istack[i]
endif
endloop
return false
endmethod
endstruct
//! endtextmacro
endlibraryI'm currently writing this to improve my flocking system and possibly to write the GetClosestTile lib
Last edited:
