Good afternoon developers,
I’m currently trying to make a Quadtree system as part of an extreme optimization overhaul for a project I’m working on. It heavily utilizes recursive and callback functions, which has caused me some interesting issues I can’t quite figure out.
The two functions in question are part of the Node Class, the functions Node:Insert and Node:Subdivide these both call each other under specific circumstances, and eventually should resolve and stop execution when the point has been properly inserted and the Node subdivided if necessary. Unfortunately that is not the case, and these seem to be calling each other infinitely for a reason I can’t figure out.
Additionally, this does not happen every time a point is inserted, but only sometimes. It is most likely to happen when the Node has a low point capacity and many points are being inserted at once.
I have tried to put print statements and use Breakpoints but unfortunately due to the random nature of the bug these attempts have been unsuccessful (Print statements do not actually print when the bug occurs for some reason.)
There are some functions here that should be self-explanatory based on their names, but I know it’s specifically these two functions because the output window shows them being called infinitely, and no other function upon the bug occurring.
-- Point = A metatable that contains a Vector2 for Position
-- Self.Points = A table of all the points the node and it's children nodes contain
-- Self.ChildrenNodes = A table of all the children nodes of the node.
-- Self.Boundry = A rectangle class that acts as the Bounds for the Node
-- Contains a few methods that work with 2D space and use computational geometry
-- Self.Divided = A bool that describes if the node has been divided or not
-- Self.Capacity = The maximum amount of points that a node can have before it subdivides
function Node:Subdivide(Point) -- Creates 4 children nodes, subdivisions of the parent node
if self.Divided then -- If the node is already divided, try to put the point under one of the child nodes via brute force
for _, node in ipairs(self.ChildrenNodes) do
node:Insert(Point)
end
return
end
self.Divided = true
-- Create variables for the Node's relevant boundary info for ease of access
local Pos = self.Boundry.Position
local Size = self.Boundry.Size
-- Create the bounds for the new nodes
local BoundsNE = Rectangle.new(Pos.X + Size.X / 2, Pos.Y - Size.Y/2, Size.X/2, Size.Y/2)
local BoundsNW = Rectangle.new(Pos.X - Size.X/2, Pos.Y - Size.Y/2, Size.X/2, Size.Y/2)
local BoundsSE = Rectangle.new(Pos.X + Size.X/2, Pos.Y + Size.Y/2, Size.X/2, Size.Y/2)
local BoundsSW = Rectangle.new(Pos.X - Size.X/2, Pos.Y + Size.Y/2, Size.X/2, Size.Y/2)
-- Create the new nodes themselves
local NorthWest = Node.new(BoundsNW, self.Capacity)
local NorthEast = Node.new(BoundsNE, self.Capacity)
local SouthWest = Node.new(BoundsSW, self.Capacity)
local SouthEast = Node.new(BoundsSE, self.Capacity)
-- Insert the new nodes into the ChildrenNodes table
table.insert(self.ChildrenNodes, NorthEast)
table.insert(self.ChildrenNodes, NorthWest)
table.insert(self.ChildrenNodes, SouthEast)
table.insert(self.ChildrenNodes, SouthWest)
-- Put the point under one of the newly created children nodes
for _, child in ipairs(self.ChildrenNodes) do
for _, point in ipairs(self.Points) do
child:Insert(point)
end
end
end
function Node:Insert(Point) -- Inserts a point
if not self.Boundry:Contains(Point) then return end -- If the point is not within the node, do nothing
table.insert(self.Points, Point) -- Insert the point into the node
if #self.Points >= self.Capacity then -- Subdivide if the node is over capacity
self:Subdivide(Point)
end
end
The functions are supposed to be able to be called under the Master Node, or the Node that has no parent and is the parent for all other nodes, and go down the chain automatically to properly assign the points to the correct nodes.
P.S. I do realize I spelt “Boundary” wrong, as “Boundry” in the code, I’m too lazy to fix it, sue me.
