A* Pathfinding Project

1000 agents and more?


#1

Hi there,

I would love to know if your tech could handle a high number of agents (1000 >) like in Sim Airport, or Another Brick in the mall, in the context of a grid Builder simulation. Can it handle a large sized map like the games mentioned…?

Also if a grid is overkill, could it be possible to use your tech on a gridless environment, such as Planet Coaster? Meaning regenerating at runtime walkable path and so on…

Currently comparing this solution with a flow field solution, maybe both combined?

Thanks


#2

Hi

It can be done, however for 1000 agents you will want to use a custom movement script or at least use the AILerp movement script (the fastest of the built-in ones). AIPath and RichAI would probably have too much overhead due to all their flexibility when you have that many agents. You will probably want to be careful about when you recalculate the paths for units to reduce overhead.

Can it handle a large sized map like the games mentioned…?

I haven’t played either of those games so I’m not sure how large the maps can get. It can handle reasonably large maps though.


#3

Hello,

Thanks a lot for the quick answer,
Just to give you a bit more context:

Sim Airport:


Current max size is 141,352 tiles.

Another Brick in the Mall:


512 x 288 tiles

I suppose in such games, if I were to use your system, I would need to space out over several frames the number of path requests, as well as rebuilding current paths when new constructions happen?

Rimworld also deals with very large map (but much less number of agents) and the grid is split into chunks (or regions https://www.youtube.com/watch?v=RMBQn_sg7DA) for a more hierarchical path finding. Is that something your tech is built on as well?

In the case of Planet Coaster it is much more different as there are different flow field to generate for each goal in the map, agents just have to follow the vector providing by the flow field.
It is costly to regenerate each flow field every time a new goal or construction gets added:

What do you think?


#4

Those world sizes should be doable (assuming one tile equals one pathfinding node). Though path requests over the whole map may be a bit slow.
The package has support for something called flood paths which are similar to the ones you are talking about. They calculate the path from every single point on the map to a single target and later units can get the complete path to that point extremely quickly. See https://arongranberg.com/astar/docs/floodpath.html. It does use a bit of memory though.

This package does not support hierarchicalpathfinding, however it has something else which can speed up the pathfinding a lot. See https://arongranberg.com/astar/docs/heuristicopt.html. It is mainly intended for static maps and it will not perform very well if you have a lot of updates to the graph though. However it only really needs to be recalculated if an obstacle is removed, not when one is added. So depending on how your game works it can be a way to speed up the pathfinding. This workflow is not supported out of the box, but I’m thinking that whenever an obstacle is removed this optimization is temporarily disabled while you recalculate the necessary lookup data in the background.


#5

Thank you for all the great answers.

I think I will start with the basics using your package to get everything put together, and will go through all your documentation again later if optimization is needed, there are a lot of options apparently. There’s no point speculating yet on what can work or not until I have all the pieces in hand.

This package looks very promising, thank you so much for all this work.