Quadtree rewritten for Hollywood
Posted: Sun Apr 30, 2023 8:04 am
Information provided as is and could contain errors. For further information or to provide your own optimisations, feel free to contact me.
Initialise the Quadtree using QuadtreeInit (mapWidth, mapHeight) to encompass the entirety of your map or screen.
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.
When you move your object on screen you MUST update the object in the quadtree, this can be done in one of two ways. If you maintain the optional bx and by fields like object1 from above does, you can use the UpdateObjects method.
if you don't maintain the optional fields, you MUST remove the object first then add it back, this is actually what UpdateObject does but can only be used when the optional fields exist.
NOTE: The quadtree does not update bx and by after the move, you need to do this yourself.
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)