Best approach for multiplayer pathfinding?

Beginner Questions
#1

Hey, I am working on a multiplayer game and I am not sure what is the best approach here.

It’s a procedural generated world where different players can load different chunks.
Since I want the server to do the AI pathfinding I am wondering if it’s possible to create a small grid layered graph for every AI spawned.

Is it possible to do in A*?

Thank you in advance.

1 Like
#2

Hey,

Sorry for the simple response here. I’m on mobile.

Procedural map generation is definitely possible. There is an example scene included with the project. However I’m not sure if it’s working for layers gridgraphs, you might have to tweak it a little to get to work.

The best approach for multiplayer really depends on the size of the maps, etc.

1 Like
#3

Thanks for the response.

I’ve got it setup for single player using the grid mover and a single graph.
I don’t need to do any pathfinding for the player in the server but I do however want to do the AI logic there. I am wondering if it’s a good idea to create a graph for each game object (a small graph).
Basically, I am asking if it’s smart to have a lot of small graphs since I can’t have a huge one.

#4

Many small graph vs one large really depends on the size of the map, amount of enemy groups, are these groups really close, far apart etc.

You need to be careful how far you go from the origin for grid graphs, due to floating point precision.

Aron also wrote in an similar post that large recast graphs are better than large grid graphs.
So that’s also something you might want to keep in mind.

1 Like
#5

Hi

Sorry for the late answer. I am currently traveling and I lost my laptop on a flight, so I haven’t been able to work for a while.

If you can use a single graph, that is definitely preferable. The recast graph can handle large worlds (kilometers in size). If you cache it you will not have to suffer the long calculation time when the game starts (https://arongranberg.com/astar/docs/saveloadgraphs.html).

#6

And what about determinism? We are working in a multiplayer game also and we plan to do pathfinding only in the localhost because in all the pathfinding systems we have tested we always have non deterministic behaviours.

#7

@Adrian_Mesa

Hi

Pathfinding is deterministic as long as the following requirements are met:

  1. You do not use any explicitly non-deterministic classes (e.g. RandomPath, FleePath, AlternativePathModifier)
  2. The floating point operations on both machines are the same. In rare cases floating point operations on different machines can give different results due to extended precision. This is a very problematic point for doing any kind of deterministic operations with C# that uses floating point. The C# spec explicitly allows evaluating floating point calculations with a higher precision that strictly necessary (e.g. using 86 bits instead of 32 or 64 bits). Some computers will differ here. For this reason alone I would strongly recommend not to rely on deterministic behavior across multiple different machines (unless you completely avoid floating point operations).
  3. Path requests and graph updates are ordered in the same way for both machines (if you update the graph on one machine before some path was calculated it may give a different result compared to on another machine where the graph update was done after the path request).

Note that since path requests in this package are asynchronous they may take different amounts of time to calculate on different computers. This could be a source of non-determinism. You can force paths to complete immediately using the path.BlockUntilCalculated method if you want to avoid this.

Also note that the included movement scripts are only deterministic if the frame rate is identical. Otherwise they may diverge veeery slightly. For example moving over two frames with a delta time of 0.1 and then 0.2 is not necessarily the same as moving with a delta time of 0.3.

The RVO requires some minor changes to be deterministic. I assume you have some kind of fixed frame rate tick that you use for the rest of the game. You’ll have to modify the RVOSimulator and RVOCoreSimulator classes so that the RVOSimulator is ticked at the same time as your fixed frame rate.

Here is a diff that simplifies this a bit for you: https://pastebin.com/Dpywr6ai you essentially need to change it so that the Update(deltaTime) method is called once per your fixed frame rate tick.

4 Likes
A* 4.3 multiplayer pathfinding
#8

Hi Aron! Thank you for your detailed response.
We plan to test calculating movement only in the localhost and send movement packets to sync entities in clients.
If wee see that bandwidth is too high, we will use your response to do some tests,

Thanks you very much!

1 Like
#9

Hi Adrian!
Which plan did you choose？
Can you share your solution?
We have gotten the same problem.
Can you give me some suggestions？

#10

please add my Telegram：LongStarStar