Weirdly enough…During my first pass at finding a path. I do it pretty instantly, but during my second pass. I seem to break and it doesn’t work anymore. Distance is basically the same as first pass…
this is so weird
i can find path twice one after another (call getpath one after another) but if i move my player to the path
then re-path it will break…
Might be because you stored the data in the nodes, so the data from the previous path conflicts with the new one.
I would add to this conversation that JPS in 3D is probably one of the most difficult programming problems I have ever come across, and that it often performs slower in Lua. If you can limit it to 2D along walkable surfaces, it may yield a speed up. However, HPA* is much more performant and has other advantages like quick path existence checks, quick initial directions, and it does not require the full path to be planned in advance (works great when paths frequently change).
If your graph does not change often you could gain speedups by using HPA* with a hierarchical clustering algorithm, the simplest of which would be recursively applying Kargar’s mincut algorithm. There are also advantages to creating clusters of nodes which are convex. These clusters of nodes would gain the property that any points inside the cluster are connected by a straight line, allowing faster and more realistic pathfinding. This is also the idea behind navigation meshes.
Anyways, to summarize, A* is a very powerful, optimal, and basic algorithm. In order to make it more efficient, you need to change the states or graph it runs on. In particular, encode more information into less nodes. Represent assumptions and shortcuts in connections and clustering. Embed precomputed information in this graph to speed the runtime performance.
3 Likes
but when i loop through my GetNeigbours to add fcost and gcost it shouldn’tt affect the the global scope of Grid[x][y]'s should it? should only affect whats inside the loop till im out of scope?
I also seem to never really find a random neighbor. After i find my first path, and i walk back to my other position (lets say its a couple steps from my original start) during its 2nd to 3rd pass it seems to make a waypoint from wher i was originally standing to where i’m going. Rather then where im currently standing. I checked to see if StartPos in findpath was the same, and its not. They change… I think it has something to do with either my worldpos or my neighbors ?
Here they are.
function GetRandomPathTarget(CurrentPosition)
local Node = Grid:NodeFromWorldPosition((CurrentPosition))
local neigbors = Grid:GetNeighbours(Node)
local val = math.random(1, #neigbors)
print(val, " generated")
local point =val
neigbors[point] = Grid:GetNeighbours(Grid:NodeFromWorldPosition((neigbors[point].worldPosition)))
print(#neigbors)
if(#neigbors == 0 or #neigbors == 1) then
neigbors[1] = CurrentPosition
point = 1
else
for i = 1,5, 1 do
point = math.random(1, 8)
neigbors = Grid:GetNeighbours(neigbors[point])
end
end
return neigbors[point].worldPosition
end
function Grid:GetNeighbours(Node)
local neighbours = {}
local count = 1
if(Node == nil or Node.gridX == nil) then
return neighbours
end
for x = 0, 2, 1 do
for y = 0, 2, 1 do
local checkX = Node.gridX + x
local CheckY = Node.gridY + y
if(checkX >= 1 and checkX < gridSizeX and CheckY >= 1 and CheckY < gridSizeY) then
neighbours[count] = Grid[checkX][CheckY]
count = count + 1
end
end
end
return neighbours
end
function Grid:NodeFromWorldPosition(VectorWorldPos)
local percentX = (VectorWorldPos.X + gridWorldSizeX / 2) / gridWorldSizeX
local percentY = (VectorWorldPos.Z + gridWorldSizeY / 2) / gridWorldSizeY
percentX = Clamp01(percentX)
percentY = Clamp01(percentY)
local x = math.ceil((gridSizeX - 1) * percentX);
local y = math.ceil((gridSizeY - 1) * percentY);
return Grid[x][y]
end
also note in the random rolls. I seem to always find the same path no matter what…
Also no matter how many random neigbors i roll through i seem to always get same freaking paths lmao. If i set positions on startup to directly take me to a different path that works np… its getting flustered now -.-’
Live demo available here… MMO Rpg V4 - Roblox
IF he stops moving most likely the script on the server end is outputting this…
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)