Octrees / quadtrees work well for storing voxel or pixel data. You wouldn’t need to compress your map to store / transfer it, only serialize the tree. It also is very efficient for runtime queries, providing logarithmic access time. You can also perform spacial and region queries on it. I actually made an octree specialized for storing AABB on my github, here. I used roughly 5 years ago when I was working on a navigation mesh pathfinder. I would insert the AABB of all surfaces into this octree and use it to find the nearest neighbors for identification of connections, surfaces below points, and clearances above surfaces.
Back when I was working on this project, I also looked for ways to speed up the computations. I thought that instead of performing thousands of intersection tests (which were made much faster BTW if I used an octree to perform thousands of tests at once) I could generate the closed areas using the parts. This way, the computation would scale with the number / size of parts and not the total play area size. Here is the voxelization code I wrote for it.
Unfortunately that still wasn’t performant enough for me. That is part of the reason I moved to navigation meshes. In most games, they take meshes of objects, voxelize them, and then merge and optimize them to create efficient and high quality navigation meshes. I looked into this and there isn’t a whole lot of information on it. Luckily, Roblox’s parts is most cases provide a good starting point. I actually just wrote a script to obtain all surfaces and filter out the the ones that were facing upwards. Those were my initial navigation mesh nodes. I found nearby ones and connected them. Eventually, I needed to project surfaces down to find out if one part was on top of another and if there was enough clearance to walk on it.
I’m not sure i really understand. Wouldn’t i still have to create my grid some how and access an area which contains the data already that way i dont create it again? Maybe you can spoon feed me a little haha.
MY create grid is here… and this is what takes 80 seconds
function CreateGrid()
local worldBottomLeft = (Vector3.new(0,0,0) - Vector3.new(1,0, 0) * gridWorldSizeX / 2 - Vector3.new(0,0,1) * gridWorldSizeY / 2)
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)--]]
--wait()
end
wait()
end
Grid.CompletedLoad = true
repeat wait() until Grid.CompletedLoad == true
--DrawBlocks()
end
This video is a great introduction to quadtrees. Octrees are the 3D version and simply have 8 children instead of 4 (don’t worry, that is explained in the video).
Once you have created your octree, you serialize it. This means that you turn your octree into a string representation. When you start a new server, you read in this string and deserialize it into the octree. Essentially, the serialized octree is a string representing how to reconstruct the original tree. It is much faster than compression.
Oh wow! your explanation makes way more sense to now! But i’m not sure how effient a string would be to represent a octree of over 4 million + nodes? Wouldn’t that be worse? Your github octree seesm nice and all but I feel I’d need to modify it a bit… all this minx and max seems useless if im just tracking the node itself. I’m not to sure how I’d convert. Seems like you’re trying to also lean me towards not using
grid[x][y] not sure i’d have to really dig into it to get an understanding of its conversion.
Right, your octree will be much simpler than mine since you will not be storing AABBs inside of it. It will be much more efficient than simply storing the grid positions and if they are filled or not. The reason being that one octree node can represent thousands of nodes at once. It is like compression, however it offers runtime advantages as well.
i’ve been trying for awhile to convert tbh, and I’ve had no luck. Each time i go and attempt test it just take way longer then just sitting there and waiting for a grid to be created lmao.
