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
mainOctree:Add(GetBoundingBox(part))
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
--Add lesser side
check(current, i - 1)
--Add greater side
return check(current + 2^(i - 1), i - 1)
--Check if on lesser side
elseif lesser[i] then
--Add lesser side
return check(current, i - 1)
else
--Add greater side
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