Tips for optimising A-Star pathfinding?

Due to the current limitations of the built-in pathfinding-service (see PathfindingService Woes - #6 by sparker22 - specifically the inability to specify parts to ignore), I implemented my own a-star pathfinding algorithm in Lua. It works well, and is extremely fast (calculates paths in ~0.005 seconds).
The game it is being used in is a tycoon game in which guests are moving around the area along designated paths in a grid, as such, there are a lot of calculations going on at once for each guest in the park. While this seems to be not a problem while running the game in studio:

Pathfinding in-studio

pathfinding01 on Vimeo

(excuse the vimeo, it was easier lol)

it becomes a problem when running the game in a server:

Pathfinding in a Test Server

pathfinding02 on Vimeo

[notice the lag in-between the movement of guests; once a guest reaches a path, they pause]
the lag noticed here is even more prominent in an online game.

As such, I’m struggling to figure out how I could optimise this.

A-Star Pathfinding Code

Is there any way this could be made more efficient? Or are there any other suggestions for other pathfinding methods or a way to make Roblox’s pathfindingservice compatible with this scenario?

(I have tried the pathfindingservice, and it’s what is currently being used as a replacement for the a-star method. What I’m doing is calculating a path using the service, and then finding the nearest path to each waypoint the service provides, but this doesn’t work well when the service creates a path that cuts across the grass).

7 Likes

I would be cautious to put that down to ‘lag’.

The pauses after each movement could be caused by using Humanoid.MoveToFinished, which seems to fire a little late outside of Play Solo - I don’t know what you are using for this purpose.

3 Likes

Hmm, that is in fact what I’m using. I’ll have a little play-about and report back.

1 Like

I’d strongly suggest shifting to a distance-from-target check. That’ll probably make the movement look a little smoother in any case as you’ll likely be able to cut corners a bit more closely.

1 Like

I changed the humanoid.MoveToFinished:wait() to using magnitude to find the difference between the torso’s position to the target point, and this worked. However, this did eventually confirm that it is indeed lag that is causing this problem. Both in studio and in a test-server, the guests worked fine. So, I tested this in an online server, and this occured:

Definitely not a result of the :MoveToFinished() event unfortunately.

2 Likes

I can tell you what not to do: don’t try to implement and use a heap for your open list. All of the extra indexing involved in trying to use a heap for pathfinding in Lua will just slow things down unless you’re trying to pathfind through a very large space (and I’m still skeptical that you can get it to run faster than a flat list even then… I couldn’t when I tried back a few years ago).

3 Likes

So essentially, a-star pathfinding in lua is a no-go in this sort of scale?

1 Like

A particular method of optimizing A* would not be good to implement in Lua. A* itself is completely fine, and your scale is very small. Your problems shouldn’t be coming from your pathfinding code, they’re coming from how you’re handling the humanoids. If you could share the code relating to having the humanoids follow the path then that would make it more clear what’s going on.

1 Like

It’s fairly simple. I require the module and call the function that returns a table with every path object from the closed list. I then iterate over the table, making the humanoid move to each path.

Edit:
Also, using this same movement code, but using the roblox pathfinding, doesn’t yield lag at all

Edit 2:
This code is in a script in the ServerScriptService that is used in a while loop upon each guest.
pseudocode to demonstrate:

local tycoons = workspace.Tycoons:GetChildren()
for i,tycoon in pairs(tycoons) do
tycoon.Players.ChildAdded:connect(function(guest) spawn(controller(guest) end)
end
local function controller(player)
...
...
...
local function movePlayer()
...
end

while true do
movePlayer()
wait(.25)
end

end
1 Like

I came across this NPC lag while on server/client test mode. I set SetNetworkOwner(nil) on my NPC’s HumanoidRootPart and it solved that network physics difference. I hope this can help out.

21 Likes

Thank you so much! This worked perfectly <3

1 Like