A* Pathfinding Project

Scale and deterministic questions


#1

Hello everyone!
I’m just on the edge of buying this, but after searching through the forums, I still need to questions answered.
I’m looking to be using this in a networking matter, so I’m wondering if it’s possible to calculate the path, given a start and an end position, and have that path be deterministic, ie generated the same way each time.
If so, it would make networking tremendously easier.

For the last question, is maybe a bit wierd one, is it possible to scale the navigation mesh uniformly without having to regenerate it? Some of the moveable places in my game will be scaled uniformly, and would be great if the navigation mesh supported this so a re-generation isn’t necessary.

Best Regards
Niels


#2

Hi

Given the same graph and the same start and end positions, yes the calculated path is deterministic. You may want to use the path.BlockUntilCalculated method to force the path to be completed immediately as path calculations are otherwise asynchronous.

Yes, you can use NavGraph.RelocateNodes. For some graphs there are other overloads that may be more useful.
For example here is one for grid graphs.
And here is a useful one for recast/navmesh graphs.


#3

Ah yes, alright, interesting, so I can generate the path so I’ll just make sure my bots start and end at the right positions and it should be all good.

Ah, nice, so RelocateNodes for scaling it down. That’s neat!
Thanks a bunch for your replies!


#4

Note that while path calculations are deterministic, following the paths using the built-in movement scripts AIPath and RichAI is not determinstic, or rather, it is affected by the frame rate. The AILerp script should be very close to independent of the frame rate though (modulo floating point errors). For networking you may want to write your own movement scripts with higher guarantees of determinism regardless of the framerate.


#5

Yeah, the exact position of the agent might differ, but in terms of bot play, it’ll be very minor I’m sure. As long as the path is deterministic, that’s the most important.
Thanks a bunch


#6

About the path.BlockUntilCalculated though, there isn’t a way to get a path returned from point to point? Say a navmesh agent hasn’t reached the target on all clients before calculating a new one, desync would appear. Therefor the server should probably generate the navmesh path or give some greenlight to the clients or similar.


#7

I’m not quite sure what you mean.
Here are the docs for searching for paths, they might be helpful: https://arongranberg.com/astar/docs/callingpathfinding.html