Code: Select all
/*
Copyright (C) 2008 Samuel Stauffer <samuel@descolada.com>
See LICENSE and COPYING for license details.
*/
;------------------------------------------------------------
;---------------------- QuadTree class ----------------------
;------------------------------------------------------------
Const #MAX_QT_DEPTH = 4
Local Quadtree = {}
Local Quadtree_mt = {}
Function Quadtree.new (_left, _top, _width, _height)
Return (SetMetaTable(
{
left = _left,
top = _top,
width = _width,
height = _height,
children = Nil,
objects = {},
}, Quadtree_mt))
EndFunction
Function Quadtree:subdivide ()
If (HaveItem (self, "children"))
For i,child In Pairs (self.children) Do child:subdivide ()
Else
Local x = self.left
Local y = self.top
Local w = Floor (self.width / 2)
Local h = Floor (self.height / 2)
;-- Note: This only works For even width/height
;-- For odd the size of the far quadrant needs To be
;-- (self.width - w, self.height - h)
self.children = {
Quadtree.new(x, y, w, h),
Quadtree.new(x + w, y, w, h),
Quadtree.new(x, y + h, w, h),
Quadtree.new(x + w, y + h, w, h)
}
EndIf
EndFunction
Function Quadtree:check (object, func, x, y)
Local oleft = x Or object.x
Local otop = y Or object.y
Local oright, obottom
; Check to see if object is an atlas texture and add width, height from this table
If (HaveItem (object, "texture"))
oright = oleft + object.texture.rect.w - 1
obottom = otop + object.texture.rect.h - 1
Else
; Object is not a texture but must have .w and .h representing object width and height
oright = oleft + object.w - 1
obottom = otop + object.h - 1
EndIf
If (HaveItem (self, "children"))
For _, child In Pairs (self.children)
Local left = child.left
Local top = child.top
Local right = left + child.width - 1
Local bottom = top + child.height - 1
If (oright < left) Or (obottom < top) Or (oleft > right) Or (otop > bottom)
;-- Object doesn't intersect quadrant
Else
func (child)
EndIf
Next
EndIf
EndFunction
Function Quadtree:addObject (object)
;Assert (Not self.objects [object], "You cannot add the same object twice to a QuadTree")
If Not (HaveItem (self, "children"))
self.objects [object] = object
Else
self:check (object, Function (child) child:addObject (object) EndFunction)
EndIf
EndFunction
Function Quadtree:removeObject (object, usePrevious)
If Not (HaveItem (self, "children"))
self.objects [object] = Nil
Else
;-- If 'usePrevious' is True Then use prev_x/y Else use x/y
Local x = (usePrevious And object.bx) Or object.x ; object:getX ()
Local y = (usePrevious And object.by) Or object.y ; object:getY ()
self:check (object, Function (child) child:removeObject (object, usePrevious) EndFunction, x, y)
EndIf
EndFunction
Function Quadtree:updateObject (object)
self:removeObject (object, True)
self:addObject (object)
EndFunction
Function Quadtree:removeAllObjects ()
If Not (HaveItem (self, "children"))
self.objects = {}
Else
For _, child In Pairs (self.children) Do child:removeAllObjects ()
EndIf
EndFunction
Function Quadtree:getCollidableObjects (object, moving, ignore)
If Not (HaveItem (self, "children"))
Return (self.objects)
Else
Local quads = {}
self:check (object, Function (child) quads [child] = child EndFunction)
If (moving) Then self:check (object, Function (child) quads [child] = child EndFunction, object.bx, object.by)
Local i, o
Local near = {}
For q In Pairs (quads)
For i, o In Pairs(q:getCollidableObjects (object, moving, ignore))
; -- Make sure we don't Return the object itself
If (o <> object)
; if there are no other objects to ignore add it
If IsNil (ignore)
InsertItem (near, o)
Else ; check ignore table
; if object is not in the table of objects to ignore add it
If (IsNil (RawGet (ignore, o)))
InsertItem (near, o)
EndIf
EndIf
EndIf
Next
Next
Return (near)
EndIf
EndFunction
Quadtree_mt.__index = QuadTree
Function QuadtreeInit (mapWidth, mapHeight)
Global entities = Quadtree.new (0, 0, mapWidth, mapHeight)
Local depth
For depth = 1 To #MAX_QT_DEPTH Step 1 Do qtEntities:subdivide ()
EndFunction
Once initialised you can use the entities class object to add entities, or modify the code to return an object if you prefer.
Objects that are added to the Quadtree can only be added once and must be unique. The must include the following table fields as a minimum :
x - representing the x location of the object on the map/screen.
y - representing the y location of the object on the map/screen.
w - represetging the width of the object in pixels.
h - representing the height of the object in pixels.
Optional fields to use if you want to update object positions in the quadtree without having to remove them first (see below)
bx - representing the x position before any moves (this should be initialised with the same value of x
by - representing the x position before any moves (this should be initialised with the same value of y
Add an object into the Quadtree.
Code: Select all
object1 = { x = 10, y = 20, w = 50, h = 25, bx = 10, by = 20 }
object2 = { x = 20, y = 30, w = 50, h = 10 } ; does not include optional fields
entities:AddObject (object1)
entities:AddObject (object2)
Code: Select all
entities:UpdateObject (object1)
Code: Select all
entities:RemoveObject (object2)
entities:AddObject (object2)