QuadTree A* Pathfinding?

Help and Feedback Scripting Support
#1

Hey guys, this thread might be a little vague so bare with me and please try and understand.

I’ve created my own custom pathfinding system which requires a grid[x][y] to be created for all possible nodes. On startup, my game takes about 81 seconds to load that grid data fully. I thought to my self if I’m already creating a set of data, and this set never changes, why don’t I just read it in from somewhere rather then recreate.

At this point, I was referred to Lua-AABB-Octree/Octree.lua at master · idiomic/Lua-AABB-Octree · GitHub

What i did was I tried to use this and create a Octree.Octree() with center as 0,0,0 and size as (gridsizeX*gridsizeY)

and basically with my current createGrid method during the create part
I have this currently

function CreateGrid()
	local worldBottomLeft = (Vector3.new(0,0,0) - Vector3.new(1,0, 0) * gridWorldSizeX / 2 - Vector3.new(0,0,1) * gridWorldSizeY / 2)
	local finalTable = {}
	local dataStuffTable = {}
	if(makeGrid == true) then
		for x=1,gridSizeX, 1 do
			Grid[x] = {}
			for y=1,gridSizeY, 1 do
				local WorldPoint = worldBottomLeft + Vector3.new(1,0,0) * (x * nodeDiameter + nodeRadius) + Vector3.new(0,0,1) * (y * nodeDiameter + nodeRadius)
				local min = WorldPoint - (((nodeDiameter + nodeRadius)) * part.Size)
				local max = WorldPoint + (((nodeDiameter + nodeRadius)) * part.Size)
				local currentRegion = Region3.new(min, max)
				local notWalkableFound = false
				for _,Part in pairs(game.Workspace:FindPartsInRegion3(currentRegion,nil,5)) do
	  				if(Part.Parent.Name == "Unwalkable" == true) then
						notWalkableFound = true
						break;
					end
				end
				
				local walkable = (notWalkableFound == false)
				local penalty = 0
				if(walkable == false) then
					penalty = penalty + obstaclePromityPenalty
					--print("obstacle found.")
				end
				Grid[x][y] = NodeClass.new(walkable, WorldPoint, x, y, penalty)--]]
			end
			wait()
		end
	else
		print("load from datastore.")
	end
	Grid.CompletedLoad = true
	repeat wait() until Grid.CompletedLoad == true
	
	
	print("added to datastore.")
	--DrawBlocks()
end

Using the octree i add octree:(min.X, min.Y, min.Z, max.X,max.Y, max.Z, NodeClass.new(walkable, WorldPoint, x, y, penalty)

Once this table is done loading, and i try to add the table I still get a datastore max character limit…

2 Likes
A* Pathfinding Support Using Heaps
Custom Pathfinding Just Isn't Working
#2

This is basically what the create grid for the octree looks like…

function CreateGrid()
	local worldBottomLeft = (Vector3.new(0,0,0) - Vector3.new(1,0, 0) * gridWorldSizeX / 2 - Vector3.new(0,0,1) * gridWorldSizeY / 2)
	local finalTable = {}
	local dataStuffTable = {}
	local OctreeList = Octree.Octree(0,0,0, gridSizeX*gridSizeY)
	if(makeGrid == true) then
		for x=1,gridSizeX, 1 do
			--Grid[x] = {}
			for y=1,gridSizeY, 1 do
				local WorldPoint = worldBottomLeft + Vector3.new(1,0,0) * (x * nodeDiameter + nodeRadius) + Vector3.new(0,0,1) * (y * nodeDiameter + nodeRadius)
				local min = WorldPoint - (((nodeDiameter + nodeRadius)) * part.Size)
				local max = WorldPoint + (((nodeDiameter + nodeRadius)) * part.Size)
				local currentRegion = Region3.new(min, max)
				local notWalkableFound = false
				for _,Part in pairs(game.Workspace:FindPartsInRegion3(currentRegion,nil,5)) do
	  				if(Part.Parent.Name == "Unwalkable" == true) then
						notWalkableFound = true
						break;
					end
				end
				
				local walkable = (notWalkableFound == false)
				local penalty = 0
				if(walkable == false) then
					penalty = penalty + obstaclePromityPenalty
					--print("obstacle found.")
				end
				OctreeList:add(min.X, min.Y, min.Z, max.X, max.Y, max.Z, NodeClass.new(walkable, WorldPoint, x, y, penalty))
				
				--Grid[x][y] = NodeClass.new(walkable, WorldPoint, x, y, penalty)--]]
			end
			wait()
		end
	else
		print("load from datastore.")
	end
	repeat wait() until Grid.CompletedLoad == true
	
	print(#OctreeList, " entries")
	--DrawBlocks()
end

Basically when i try to store the OctreeList to a datastore for serialization i get max character limit. I know i’m doing something wrong. Because i have to get my data in the form of grid[x][y] :confused:

#3

You do not need your data in the form of grid[x][y]. All you need to know is if grid[x][y] is empty. This is a key difference, one that quadtrees capitalize on. You do not need to check every single x and y coordinate. Imagine if instead of checking one cell at a time with FindPartsInRegion3, you checked four cells at a time as group. You would perform roughly 1/4th of the work. Now if one of those checks found that it was blocked, you can check each of the four cells to be sure that all of them are blocked. If there are open spaces 2x2 or larger, then this method will perform faster. We can scale this up and check four these groups of cells at once, effectively checking 16 cells at once. If this group of groups is blocked, then we check each group. If a group is still blocked, then we check the cells in the group.

The key advantage is that we perform many times less checks, and that if the region containing a cell is clear, we know the cell is clear without storing information for each cell.

Now, to implement this I would recommend not using my Octree. I would recommend creating 3 sizes of cells: 4x4 2x2 and 1x1. Check all 4x4 cells if they are blocked. If so, check the 2x2 blocks inside of it. For each of those 2x2 blocks, check the 1x1 blocks inside of them if they are blocked. Once you have this down, you can make larger cells like 8x8 and 16x16. You can also automate the process, checking each cell size is roughly the same procedure so you can use recursive calls to check the smaller nodes if a larger node is blocked. Finally, you can optimize by if all the children are blocked, we only need to store that the parent is blocked.

To check if a cell (x, y) is empty, we check the largest group it belongs to. If the group is open or blocked, so is the cell. Otherwise, we check the next smallest group the cell is in.

3 Likes
#4

Yeah this might be a bit out my knowledge. It was hard enough to create the grid[x][y]. :confused: Thank you for a detailed report though, i did try and read it and watch videos but setting it up without having nodes and using region 3 is somewhat out my knowledge. still new to roblox

#5

Hey, i watched this video to try and get a better understanding of quadtrees…

I kinda implemented it onto lua, but im having some minor trouble deciding how the grid should load up with a good width, and height value based on some data…

local Section = require(game.ServerStorage.DataStructures.QuadTree.Section)
local Point = require(game.ServerStorage.DataStructures.QuadTree.Point)
local QuadTree = require(game.ServerStorage.DataStructures.QuadTree.QuadTree)

local gridWorldSizeX = 2048;
local gridWorldSizeY = 2048;
local nodeRadius =  .025;
local nodeDiameter = nodeRadius * 2;
local gridSizeX = math.ceil(gridWorldSizeX / nodeDiameter)
local gridSizeY = math.ceil(gridWorldSizeY / nodeDiameter)
local part = workspace.Unwalkable.ClonePart:Clone()

function MapLoader:LoadMap()
	local worldBottomLeft = (Vector3.new(0,0,0) - Vector3.new(1,0, 0) * gridWorldSizeX / 2 - Vector3.new(0,0,1) * gridWorldSizeX / 2)	
	local section = Section.new(worldBottomLeft.X, worldBottomLeft.Z, gridSizeX, gridSizeY)
	local quad_tree = QuadTree.new(section, 4)	
	
	for x=1,gridSizeX, 1 do
		for y=1,gridSizeY, 1 do
			local WorldPoint = worldBottomLeft + Vector3.new(1,0,0) * (x * nodeDiameter + nodeRadius) + Vector3.new(0,0,1) * (y * nodeDiameter + nodeRadius)
			local min = WorldPoint - (((nodeDiameter + nodeRadius)) * part.Size)
			local max = WorldPoint + (((nodeDiameter + nodeRadius)) * part.Size)
			local currentRegion = Region3.new(min, max)
			local notWalkableFound = false
			for _,Part in pairs(game.Workspace:FindPartsInRegion3(currentRegion,nil,5)) do
	  			if(Part.Parent.Name == "Unwalkable" == true) then
					notWalkableFound = true
					break;
				end
			end
			local walkable = (notWalkableFound == false)	
			local point = Point.new(x, y, walkable, WorldPoint.X, WorldPoint.Y, WorldPoint.Z)
			quad_tree:Insert(point)
		end
	end
	quad_tree:Show()
	
end

When i use a low value like 20, for gridsize x and y instead of 2048 i get this result…

https://gyazo.com/3053b6aa1cd75fc05847b62b25d7a8b9

I feel like its kinda working. Just not exactly hmm…

#6

I adjusted the code a bit which now gives me an exact size of the baseplate which is 2048x2048

https://gyazo.com/76855d5e5dd87336eebe90b2599bbfdb

local gridWorldSizeX = 2048;
local gridWorldSizeY = 2048;
local nodeRadius = 2.65;
local nodeDiameter = nodeRadius * 2;
local gridSizeX = math.ceil(gridWorldSizeX / nodeDiameter)
local gridSizeY = math.ceil(gridWorldSizeY / nodeDiameter)
local part = workspace.Unwalkable.ClonePart:Clone()

function MapLoader:LoadMap()
	local worldBottomLeft = (Vector3.new(1024,0,1024) - Vector3.new(1,0, 0) * gridWorldSizeX / 2 - Vector3.new(0,0,1) * gridWorldSizeX / 2)	
	local section = Section.new(worldBottomLeft.X, worldBottomLeft.Z, gridWorldSizeX/2, gridWorldSizeY/2)
	local quad_tree = QuadTree.new(section, 4)	
	
	for x=1,gridSizeX, 1 do
		for y=1,gridSizeY, 1 do
			local WorldPoint = worldBottomLeft + Vector3.new(1,0,0) * (x * nodeDiameter + nodeRadius) + Vector3.new(0,0,1) * (y * nodeDiameter + nodeRadius)
			local min = WorldPoint - (((nodeDiameter + nodeRadius)) * part.Size)
			local max = WorldPoint + (((nodeDiameter + nodeRadius)) * part.Size)
			local currentRegion = Region3.new(min, max)
			local notWalkableFound = false
			for _,Part in pairs(game.Workspace:FindPartsInRegion3(currentRegion,nil,5)) do
	  			if(Part.Parent.Name == "Unwalkable" == true) then
					notWalkableFound = true
					break;
				end
			end
			local walkable = (notWalkableFound == false)	
			local point = Point.new(x, y, walkable, WorldPoint.X, WorldPoint.Y, WorldPoint.Z)
			quad_tree:Insert(point)
		end
	end
	quad_tree:Show()
end
#7 
local gridWorldSizeX = 2048;
local gridWorldSizeY = 2048;
local nodeRadius = 0.25
local nodeDiameter = nodeRadius * 2;
local gridSizeX = math.ceil(gridWorldSizeX / nodeDiameter)
local gridSizeY = math.ceil(gridWorldSizeY / nodeDiameter)
local part = workspace.Unwalkable.ClonePart:Clone()

function MapLoader:LoadMap()
	local worldBottomLeft = (Vector3.new(0,0,0) - Vector3.new(1,0, 0) * gridWorldSizeX / 2 - Vector3.new(0,0,1) * gridWorldSizeX / 2)	
	local section = Section.new(0,0, 1024, 1024)
	local quad_tree = QuadTree.new(section, 4)	
	
	for x=1,gridSizeX, 1 do
		for y=1,gridSizeY, 1 do
			local WorldPoint = worldBottomLeft + Vector3.new(1,0,0) * (x * nodeDiameter + nodeRadius) + Vector3.new(0,0,1) * (y * nodeDiameter + nodeRadius)
			local min = WorldPoint - (((nodeDiameter + nodeRadius)) * part.Size)
			local max = WorldPoint + (((nodeDiameter + nodeRadius)) * part.Size)
			local currentRegion = Region3.new(min, max)
			local notWalkableFound = false
			for _,Part in pairs(game.Workspace:FindPartsInRegion3(currentRegion,nil,5)) do
	  			if(Part.Parent.Name == "Unwalkable" == true) then
					notWalkableFound = true
					break;
				end
			end
			local walkable = (notWalkableFound == false)	
			local point = Point.new(x, y, walkable, WorldPoint.X, WorldPoint.Y, WorldPoint.Z)
			quad_tree:Insert(point)
			wait()
		end
		wait()
	end
	quad_tree:Show()
end

This part here takes an incredibly long time to load. Would help if i could get a tip on how to load the point datas to sections.

#8

https://gyazo.com/7fd07914b261f8752bd314911e1caca8

Green = walkable points… takes awhile to load this…

This is obviously wrong cause my unwalkables arent that large…

#9

https://gyazo.com/47e4f38cb6d6411b1c6202c54dc0188b

local maxGridSize = 1024;

local gridWorldSizeX = maxGridSize /2;
local gridWorldSizeY = maxGridSize /2;
local nodeRadius = 1.45
local nodeDiameter = nodeRadius * 2;
local gridSizeX = math.ceil(maxGridSize / nodeDiameter)
local gridSizeY = math.ceil(maxGridSize / nodeDiameter)
local part = workspace.Unwalkable.ClonePart:Clone()

function MapLoader:LoadMap()
	local worldBottomLeft = (Vector3.new(0,0,0) - Vector3.new(1,0, 0) * maxGridSize / 2 - Vector3.new(0,0,1) * maxGridSize / 2)	
	local section = Section.new(0,0, maxGridSize/2, maxGridSize/2)
	local quad_tree = QuadTree.new(section, 4)	
	
	for x=1,gridSizeX, 1 do
		for y=1,gridSizeY, 1 do
			local WorldPoint = worldBottomLeft + Vector3.new(1,0,0) * (x * nodeDiameter + nodeRadius) + Vector3.new(0,0,1) * (y * nodeDiameter + nodeRadius)
			local min = WorldPoint - (((nodeDiameter + nodeRadius)) * part.Size)
			local max = WorldPoint + (((nodeDiameter + nodeRadius)) * part.Size)
			local currentRegion = Region3.new(min, max)
			local notWalkableFound = false
			for _,Part in pairs(game.Workspace:FindPartsInRegion3(currentRegion,nil,5)) do
	  			if(Part.Parent.Name == "Unwalkable" == true) then
					notWalkableFound = true
					break;
				end
			end
			local walkable = (notWalkableFound == false)	
			local point = Point.new(x, y, walkable, WorldPoint.X, WorldPoint.Y, WorldPoint.Z)
			quad_tree:Insert(point)
			--wait(0.000001)
		end
		--wait()
	end
	quad_tree:Show()
end
#10

Ok now i see to get a better representation of the walkable and unwalkable…

ofc that pink area at the edge is not red cause its not within the main quadtree region…

I gues my question now would be, how can i find a path from point a to point b given a world position now using this newly created quad tree

local maxGridSize = 1024;

local gridWorldSizeX = maxGridSize /2;
local gridWorldSizeY = maxGridSize /2;
local nodeRadius = 0.95
local nodeDiameter = nodeRadius * 2;
local gridSizeX = math.ceil(maxGridSize / nodeDiameter)
local gridSizeY = math.ceil(maxGridSize / nodeDiameter)
local part = workspace.Unwalkable.ClonePart:Clone()

function MapLoader:LoadMap()
	local worldBottomLeft = (Vector3.new(0,0,0) - Vector3.new(1,0, 0) * maxGridSize / 2 - Vector3.new(0,0,1) * maxGridSize / 2)	
	local section = Section.new(0,0, maxGridSize/2, maxGridSize/2)
	local quad_tree = QuadTree.new(section, 4)	
	
	for x=1,gridSizeX, 1 do
		for y=1,gridSizeY, 1 do
			local WorldPoint = worldBottomLeft + Vector3.new(1,0,0) * (x * nodeDiameter + nodeRadius) + Vector3.new(0,0,1) * (y * nodeDiameter + nodeRadius)
			local min = (WorldPoint -  (((nodeDiameter+nodeRadius)) / part.Size))
			local max = (WorldPoint +  (((nodeDiameter+nodeRadius)) / part.Size))
			local currentRegion = Region3.new(min, max)
			local notWalkableFound = false
			for _,Part in pairs(game.Workspace:FindPartsInRegion3(currentRegion,nil,5)) do
	  			if(Part.Parent.Name == "Unwalkable" == true) then
					notWalkableFound = true
					break;
				end
			end
			local walkable = (notWalkableFound == false)	
			local point = Point.new(min.X, max.Z, walkable, WorldPoint.X, WorldPoint.Y, WorldPoint.Z)
			quad_tree:Insert(point)
			--wait(0.000001)
		end
		--wait()
	end
	quad_tree:Show()
end

this is how i use to create a path…
local function GetPath(StartPos, EndPos)
local OpenSet = HeapList2.new();
local ClosedSet = HeapList2.new();
local Path = {}
OpenSet:Insert(StartPos)

	local Start = tick();
	local Time = 0;
	local startTick = Start;
	local stop = false
	while #OpenSet.Items > 0 or (tick() - startTick > 1) do
		if(stop == true) then 
			OpenSet:Clear()
			ClosedSet:Clear()
			print("Clean reset.")
			Path = nil
			return nil;
		end
		if #OpenSet.Items > 0 then
			local Current = OpenSet:Pop()
			if Current == EndPos then
				break
			end
			
			ClosedSet:Insert(Current)
			if(Grid:GetNeighbours(Current) ~= nil) then
				local Neighbors = Grid:GetNeighbours(Current);
				for i = 1,#Neighbors do
					local Neighbor = Neighbors[i];
					local NewPath = false
					if((tick() - startTick > 1) ) then
						print("taking to long break out.")
						stop = true
						Path = nil
						break;
					end
					if (Current.walkable == true and not CheckInclusion(ClosedSet.Items,Neighbor)) then
						local _TempG = Current.gcost + 1;
						
						if CheckInclusion(OpenSet.Items, Neighbor) then
							if _TempG < Neighbor.gcost then
								Neighbor.gcost = _TempG;
								NewPath = true;
								OpenSet:Insert(Neighbor)
							end
						else
							Neighbor.gcost = _TempG;
							NewPath = true
							OpenSet:Insert(Neighbor)
						end
					end
					if NewPath == true then
						Neighbor.hcost = Heuristic(Neighbor, EndPos)
						Neighbor.fcost = Neighbor.gcost + Neighbor.hcost
						Neighbor.previous = Current;
						table.insert(Path, Current)
						OpenSet:SortDown(1)
					end
				end
			end
		end
	end
	print("Time it took to find path in ms:", (tick()-Start)-Time, " number of waypoints created in this time is :", #Path)
	OpenSet:Clear()
	ClosedSet:Clear()
	return Path
end
#11

Also here is my quad tree module…

local QuadTree = {}
local Section = require(game.ServerStorage.DataStructures.QuadTree.Section)

QuadTree.__index = QuadTree


function QuadTree.new(Section, Capacity)
	local tree = {}
	tree.Section = Section;
	tree.Size = Capacity
	tree.points = {}
	tree.divided = false
	setmetatable(tree, QuadTree)
	return tree
end

function QuadTree:Insert(Point)
	if(self.Section:Contains(Point) == false) then
		return false
	end
	
	if(#self.points < self.Size) then
		table.insert(self.points, Point)
		return true
	else
		if(not self.divided) then
			self:SubDivide()
		end
		
		if(self.northeast:Insert(Point) == true) then
			return true;
		elseif(self.northwest:Insert(Point) == true) then
			return true;
		elseif(self.southeast:Insert(Point) == true) then
			return true;
		elseif(self.southwest:Insert(Point) == true) then
			return true;
		end
	end
end

function QuadTree:SubDivide()
	local ne = Section.new(self.Section.x + self.Section.width/2, self.Section.y - self.Section.height/2, self.Section.width/2, self.Section.height/2)
	self.northwest = QuadTree.new(ne, self.Size)
	local nw = Section.new(self.Section.x - self.Section.width/2, self.Section.y - self.Section.height/2, self.Section.width/2, self.Section.height/2)
	self.northeast = QuadTree.new(nw, self.Size)
	local se = Section.new(self.Section.x + self.Section.width/2, self.Section.y + self.Section.height/2, self.Section.width/2, self.Section.height/2)
	self.southeast = QuadTree.new(se, self.Size)
	local sw = Section.new(self.Section.x - self.Section.width/2, self.Section.y + self.Section.height/2, self.Section.width/2, self.Section.height/2)	
	self.southwest = QuadTree.new(sw, self.Size)
	self.divided = true;
end

function QuadTree:Query(Boundary, found)
	if(not found) then
		found = {}	
	end
	if (not self.Section:Intersects(Boundary)) then
		return
	else
		for _, point in ipairs(self.points) do
			if(Boundary:Contains(point)) then
				table.insert(found, point)
			end
		end
		if(self.divided) then
			self.northwest:Query(Boundary, found)
			self.northeast:Query(Boundary, found)
			self.southhwest:Query(Boundary, found)
			self.southwest:Query(Boundary, found)
		end
		
		return found
	end
end

local maxGridSize = 2048;

local gridWorldSizeX = maxGridSize /2;
local gridWorldSizeY = maxGridSize /2;
local nodeRadius = 3
local nodeDiameter = nodeRadius * 2;
local gridSizeX = math.ceil(maxGridSize / nodeDiameter)
local gridSizeY = math.ceil(maxGridSize / nodeDiameter)
local part = workspace.Unwalkable.ClonePart:Clone()

function QuadTree:Show()
	local PartMain = Instance.new("Part")
	PartMain.BrickColor = BrickColor.Black()
	PartMain.Position = Vector3.new(self.Section.x, 1, self.Section.Y);
	PartMain.Anchored = true
	PartMain.Size = Vector3.new(self.Section.width*2, 2, self.Section.height*2)
	PartMain.Parent = workspace;
	if(self.divided == true) then
		self.northwest:Show()
		self.northeast:Show()
		self.southeast:Show()
		self.southwest:Show()
	end
	
	for _, point in ipairs(self.points) do
		local Part = Instance.new("Part")
		if(point.walkable == true) then
			Part.BrickColor = BrickColor.Green()
			Part.Position = Vector3.new(point.worldPosX, point.worldPosY+5, point.worldPosZ);
		else
			Part.BrickColor = BrickColor.Red()
			
			Part.Position = Vector3.new(point.worldPosX, point.worldPosY+Part.Size.Y+20, point.worldPosZ);
		Part.Anchored = true
		Part.Parent = workspace;
		end
		--wait()
	end
end



return QuadTree

and my Section module

local Section = {}
Section.__index = Section

function Section.new(x, y, width, height)
	local section = {}
	section.x = x;
	section.y = y;
	section.width = width;
	section.height = height;
	
	setmetatable(section, Section)
	return section;
end

-- Function that checks if point is within my bounds --
function Section:Contains(Point) 
	return (Point.x > (self.x-self.width) and
		Point.x < (self.x + self.width) and
		Point.y > (self.y - self.height) and
		Point.y < (self.y + self.height))
end

function Section:Intersects(Boundary)
	return (not (Boundary.x - Boundary.width > self.x + self.width 
		or Boundary.x + Boundary.width < self.x - self.width or
		Boundary.y - Boundary.height > self.y + self.height 
		or Boundary.y + Boundary.height < self.y - self.height))
end

return Section
#12

I guess after some more research my main question and what i understand after i get that solved…

How do I get my starting boundary point from my current vector 3 position and my end boundary point? Cause what it seems likes when i pass Start and End to FindPath, i’ll need to send the Sections, and then i need to get the start point as my start Node, and then same for end. Which i will then i guess check for neighbors?

When I query that boundary to my tree it will return found points in that region.

Which I then use to calculate the distance of each path to target. returning the final points which will contain the worldpos

I’m not to sure how this is suppose to look when creating the path to walk to…