Quadtree rewritten for Hollywood

[dwayne_jarvis]

Information provided as is and could contain errors. For further information or to provide your own optimisations, feel free to contact me.

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

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.

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)

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.

Code: Select all

entities:UpdateObject (object1)

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.

Code: Select all

entities:RemoveObject (object2)
entities:AddObject (object2)

NOTE: The quadtree does not update bx and by after the move, you need to do this yourself.

[dwayne_jarvis]

My last edit didn't finish so I will continue from here.

You can then use the Quadtree to check for other entities or objects within the same quadrant as another object/entity. The most common purpose would be to complete a collision check. The purpose of using the Quadtree is so you don't have to check every single object on the map/screen. The quadtree will filter out and return nearby objects.

You do this by passing an object that is already in the quadtree to the GetCollidableObjects. NOTE: This does not perform the actual collision check.

Code: Select all

local nearEntities = entities:GetCollidableObjects (object1)

You can then loop through the objects and perform your collision checks Collide is my own routine for performing collision checks, you will need to write your own. Mine uses an additional hitbox table that is defined for each entity, so that I can select a smaller or larger area for the actual collision check.

Code: Select all

Local thisEntity
For _, thisEntity in Pairs (nearEntities) 
	If (Collide (object1, thisEntity)) then ObjectCollides ()
Next

Please reach out if you want further explanation or assistance.

[dwayne_jarvis]

I noticed an erorr after I modified my original code to paste it to the forum with the QuadtreeInit Function so I have corrected this and made some basic modifications to make it more flexible. You can pass the maxDepth and it returns a class Object instead of defining a Global variable.

Code: Select all

Function QuadtreeInit (mapWidth, mapHeight, maxDepth)	
	Local maxDepth = maxDepth or #MAX_QT_DEPTH 
	Local entities = Quadtree.new (0, 0, mapWidth, mapHeight)
	
	Local depth
	For depth = 1 To maxDepth Step 1 Do entities:subdivide ()
	Return (entities)
EndFunction