Kinda got it skipping the time outs till it finds a good path…
https://gyazo.com/af36588d418810da5f27b7c4f21ee3e3
But now I’m just getting similar path patterns 
up and a bit right basically
So i’ve gotten pretty far with this, and its pretty solid now. Only issue is,
During server startup it takes a full 80 seconds to actually create all the nodes for the map.
IS there a way to lower this time?
I’m thinking same the data that is get created each time during server startup and just read it in from somewhere but the data size would be quite large… any ideas?
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
assuming my size 2048x2048, you can see why this would take a considerably large time…
I’d have to use httpservice i think to parse the large dataset. But i’m not sure how much more effective it would be on the load time.
Save it as a string with LZW compression. Your map will probably have enormous lines of same values. Also, save it as a row-major order with the size specified at the start. You can further increase the quality by saving 6 nodes per character.
This article offers a good string to LZW compression optimized for Roblox’s DataStores (some ASCII characters take more than 1 char space):
One improvement to mention that could potentially improve performance by quite a noticeable amount: use ipairs instead of pairs. I notice you add a placeholder underscore when not working with dictionaries and the key is irrelevant.
ipairs is designed to work with arrays and iterate over an i++ basis, given your keys are known and in numerical order. It is also quicker than ipairs I most regards and you will almost definitely see a difference as you are working with relatively large arrays.
pairs is designed for dictionaries where the keys are not known and are arbitrary. In addition, ordered iteration is not guaranteed.
1 Like
Does Luau optimize ipairs though? I know it does it for pairs and next, but I haven’t seen ipairs mentioned anywhere.
It does, yep. There was mention about a certain percentage increase, but I don’t have the citation on me right now. It was either through the RDC19 presentation Lua As Fast As Possible or on one of the Luau release threads. I’ll edit the post if I can find it.
EDIT
Video starts at the performance improvements chart with benchmarks. Look at the top two entries of the table on the right. As for discussions regarding pairs/ipairs, you can actually see a lot of them via the VM beta thread (I saw you took part in those conversations too actually).
https://devforum.roblox.com/search?q=ipairs%20topic%3A298659
Does this answer your question?
1 Like
I don’t know if this part was intentional, and I also have little to no clue if it actually effects anything, but you’re using : in the closedset = Heap:new() instead of a .new() as your module calls for and I’ve known this to cause slight issues when working with certain things.
1 Like
Good catch! slightly old code which has been fixed already but thank you for pointing it out again for having me double check! 
Much appreciated sir. I will defiantly put this into affect. Still fairly new to lua and roblox.
Been leaving my pathfinding to run for a couple hours, no problems at all! My next step is to optimize the way it create the grid data. Currently i create the grid data every time server startsup, which takes close to 81 seconds.
I’m not sure how fast it would be if i stored the grid data to datastore and just read it in on server startup (ofc saving the datastore data would be optimized for less bits)
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.
1 Like
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.
Attempting to test what? Creating an octree? If so make another thread, post the code, and I’ll assist.
Attemting to test saving the table thats created from the octree:adds()