I’ve recently updated how nodes are generated on the map in my game. Instead of being evenly-sized and spaced in a uniform grid, I’ve created a QuadTree system that renders large, open spaces of nodes into a single, larger node, thereby saving computing time when a path needs to be generated from one point to another.
(In the image above, there are a total of 856 nodes. Originally, about 2,500 evenly-sized nodes would be spread out across the map every time the game was launched.)
Here is the issue I am facing: when a unit on the map needs to navigate from its position to another point on the map, it must first figure out which node it is located in. Originally, with a uniform grid, it was rather easy to do so: simply round the unit’s position so that it matched one of the nodes on the map. However, with a QuadTree system as shown above, nodes are not evenly-spaced on the map, so rounding is not very practical. I have a couple ideas as to how to address this issue, but I didn’t feel like any of them were optimal. I wanted to know what your ideas were before I made any major changes to the pathfinding / QuadTree code.
Here’s some details about the QuadTree system that I thought might be important to know:
Nodes are stored as parts in a folder in the workspace. Inside these parts are values that store the node’s properties, such as object values that point to the node’s neighbors. I am content with the way nodes are stored, so unless changing this method is absolutely crucial to figuring out where a node is located, then they will remain this way. Also, because they are stored as parts, their positions are stored at the center, as opposed to one of their corners, as I have seen in some source codes.
There are only leaf nodes in this QuadTree system. When a node is split, the original parent node is destroyed, and the parent’s neighbors become neighbors of the split nodes. I did this on the assumption that it would be faster to index a leaf node directly, rather than recursively navigate a whole tree of nodes.
Units use an A* pathfinding algorithm to navigate nodes on the map.
Any assistance with this issue would be greatly appreciated!
Have you tried using BasePart:GetTouchingParts()? (Instantiate a new part at that position with the smallest size)
Other than that, I think you can check the exact node by comparing the position’s distance with the children of the top node, then check the distance again with the closest node’s children and rinse and repeat until the child’s distance from the position are greater than its parent’s distance from the position or when it has no children.
I understand that rounding a unit’s position might not exactly match the node, but if you can somehow get the closest node that it matched to and apply something like Breadth-first search to look at surrounding neighbors, that might prove to be the best method. Why BFS? Well, assuming that you can get an estimation for the closest node, you can also assume that the correct node will most likely be the neighboring nodes if it isn’t the estimated node.
You could try doing FindPartsInRegion3 with a very small Region3 around the point, and a whitelist containing the nodes folder. Then get the node from the table that’s returned.
You can see if a point is in an AABB square like this:
function is_point_in_square(corner0, corner1, point)
return point.X > corner0.X and point.X <= corner1.X and point.Y > corner0.Y and point.Y <= corner1.Y
end
You can then check if a point is in a quadtree node like this:
function is_point_in_node(node, point)
if #node.children == 0 then
--node is a leaf
return is_point_in_square(node.corner0, node.corner1, point)
else
--node is not a leaf
--recursively check child nodes
for _, leaf in pairs(node.children) do
if is_point_in_node(leaf, point) then return true end
end
--point is not in any of the leaf nodes
return false
end
end
Assuming you have a top-level node that contains the entire quadtree, you can figure out which node if any a point is in like this:
function find_point_node(quadtree, point)
if #quadtree.children == 0 then
--node is a leaf
if is_point_in_square(quadtree.corner0, quadtree.corner1, point) then
return quadtree
else
return nil --point is outside the quadtree
end
else
--node is not a leaf
--recursively check child nodes
for _, leaf in pairs(quadtree.children) do
local node = find_point_node(leaf)
if node then
return node
end
end
--no leaf nodes contained the point, so it's outside the quadtree
return nil
end
end
local quadtree = -- ... the top-level node of the quadtree / "the entire quadtree"
local some_point = - ...whatever you want
local node_of_the_point = find_point_node(quadtree, some_point)
