This is a simple example of what I mean, though it doesn’t exactly show the advantage. Imagine there is a small cave-like dead-end between the character and the target. With normal A*, you would have to check if the cave has a passage, but by dividing the map into pre-processed sectors, you can completelly avoid it.
If you want an example of jump-point A*, then PathFinding.js has it under Jump Point Search. It is essentially A*, but it eliminates the need to evaluate straight lines.
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…
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.
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 -.-’
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…
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.
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 Possibleor on one of the Luau release threads. I’ll edit the post if I can find it.
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).
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.
up and a bit right basically
