# A* Node Placement With Octrees

Using a modified version of @IdiomicLanguage’s Octree module, I’ve been attempting to find a way to achieve A*, but I really don’t get the algorithm, or how it works AT all.

So basically, my code gets everything in the workspace and puts it in an Octree. I want to pathfind using the information within the Octree. How would I do that?

``````-- MainScript.lua
local Octree = require("Octree")
local mapSize = 2048

function GetBoundingBox(part)
local min, max = part.Position - (part.Size/2), part.Position + (part.Size/2)
return min.X, min.Y, min.Z, max.X, max.Y, max.Z
end

local mainOctree = Octree.new(0, mapSize / 2, 0, mapSize)
for _, part in pairs(workspace:GetDescendants()) do
end

-- Octree.lua
local Octree = {}
Octree.__index = Octree

local MINIMUM_SIZE = 1 -- it's a constant
function Octree.new(x, y, z, size)
local self = setmetatable({}, Octree)

self.x = x -- all of these are the center
self.y = y
self.z = z -- (1, 2, 3)

self.size = size -- size^2 (4)
self.cell = {}

self.subCells = {false, false, false, false, false, false, false, false}

return self
end

function Octree:Child(minX, minY, minZ, maxX, maxY, maxZ)
local childrenSize = 2 ^ (self.size - 1) -- size of cell's children

-- check if the number isn't too small
if childrenSize < MINIMUM_SIZE then
return false
end

local x, y, z = self.x, self.y, self.z

local lesserX = minX <= x
local lesserY = minY <= y
local lesserZ = minZ <= z

if lesserX == (max_x <= x) and lesserY == (maxY <= y) and lesserZ == (maxZ <= z) then
return 1 + (lesserX and 0 or 4) + (lesserY and 0 or 2) + (lesserZ and 0 or 1)
end

return false
end

function Octree:Remove(minX, minY, minZ, maxX, maxY, maxZ, value)
local childIndex = self:Child(minX, minY, minZ, maxX, maxY, maxZ)

if childIndex then
local child = self.cell[childIndex]

if not child then
return false
end

local childUpdated = child:Remove(minX, minY, minZ, maxX, maxY, maxZ, value)

if childUpdated and #child.cell == 0 and not (child.subCells[1] or child.subCells[2] or child.subCells[3] or child.subCells[4] or child.subCells[5] or child.subCells[6] or child.subCells[7] or child.subCells[8]) then
self.subCells[childIndex] = false
return true
end
end

for i = 1, #self.cell do
if self.cell[i] == value then
table.remove(self.cell, i)
return true
end
end

return false
end

function Octree:Add(mixX, minY, minZ, maxX, maxY, maxZ, value)
local childIndex = self:Child(minX, minY, minZ, maxX, maxY, maxZ)

if childIndex then
local child = self.subCells[childIndex]

if not child then
local offset = 2 ^ (self.size - 2)
local childX = self.x + (minY <= self.x and -offset or offset)
local childY = self.y + (minY <= self.y and -offset or offset)
local childZ = self.z + (minZ <= self.z and -offset or offset)
child = Octree.new(childX, childY, childZ. self.size - 1)
self.subDivisons[child_index] = child
end
return child:Add(minX, minY, minZ, maxX, maxY, maxZ)
end

self.cell[#self.cell + 1] = value
end

function Octree:Intersection(minX, minY, minZ, maxX, maxY, maxZ, result)
local numResult = #result
for i = 1, #self.cell do
result[numResult + i] = values[i]
end

local x = self.x
local y = self.y
local z = self.z

local lesser = {}
lesser[3] = minX <= x
lesser[2] = minY <= y
lesser[1] = minZ <= z

local split = {}
split[3] = (lesser[3] ~= (maxX <= x))
split[2] = (lesser[2] ~= (maxY <= y))
split[1] = (lesser[1] ~= (maxZ <= z))

-- comments taken from the original
--This is very complex on multiple levels. The goal is to find out what octants contain
--the AABB defined by the min and max points. It does this by checking each axis. For each
--axis, the min and max points can be less than, greater than, or split around the center
--offset. Once one axis is determined, then it checks the next axis. Once all three are
--checked, it checks the current point defined by them. If an axis is split, it checks the
--first side for the rest of the axises, then checks the other side. It is simplest, fastest,
--and easiest to write in a recursive function.
local function check(current, i)

--If the checks are done
if i == 0 then
local child = self.subCells[current]
--Check if the child exists

if child then
--Add values contained in the child
return child:Intersection(minZ, minY, minZ, maxX, maxY, maxZ, result)
end

--Check if split
elseif split[i] then
check(current, i - 1)
return check(current + 2^(i - 1), i - 1)
--Check if on lesser side
elseif lesser[i] then
return check(current, i - 1)
else
return check(current + 2^(i - 1), i - 1)
end
end

--Start the checks. Returns nil
return check(1, 3)
end

function Octree:Print(tabs)
tabs = tabs or ""

--Print center
print(tabs .. "Center: <" .. self.x .. ", " .. self.y .. ", " .. self.z .. ">")

--Print values
print(tabs .. "Values: {" .. table.concat(self.cell, ", ") .. "}")

--Print children
tabs = tabs .. "\t"
for i = 1, 8 do
--Check if the child exists and print it
if self.subCells[i] then
self.subCells[i]:Print(tabs)
end
end
end

return Octree``````
2 Likes

Ok, so from my understanding I need to place down nodes. However, I have no idea on how I would place down these nodes.

Everything else is perfectly fine, I think I would get the AABB of these nodes and find it from there.

Another issue for me is telling the difference between what is able to be walked on and what is not so I can place the nodes accordingly.

Not really much of an answer but more of an explanation : /

A simple explanation of the A* algorithm is that it can be viewed as an extension to Dijkstra’s algorithm, which put simply, uses the distance from the starting node to the closest adjacent node of the current node.

A* adds onto Dijkstra’s algorithm by adding upon it the distance of each node from the target node.

Ok, so how would I place the nodes?

Unfortunately this octree wasn’t meant for storing simple open or closed data. It was designed to provide a quick way to determine which parts / surfaces were close to each other so that I could calculate if a NPC could walk between the surfaces, jump the gap, or perhaps only fall from one to the other. It is not well suited to storing a open/closed grid. My pathfinder was designed to use HPA on navigation meshes instead of grids.

The good news is that creating a open/closed octree should be easier. Only 3 pieces of information are required, the x, y, and z indices of the voxel. The octree should store a true / false value for every voxel in it. If a group of voxels all contain the same value, then the parent can store the value and the children do not need to be created. The octree will start as a single voxel covering the entire map with a value of true (open). To add closed voxels, iterate over every part and close the voxels of the part. You will have to voxelize every part; here is a voxelizer I wrote 5 years ago: Lua-Voxelizer/voxelizer.lua at master · idiomic/Lua-Voxelizer · GitHub

2 Likes