0
\$\begingroup\$

I am looking for a way to distribute the load of the agents over multiple paths. Ideally, the calculation would be executed multiple times a tick.

One use case would be for traffic balancing for a set of vehicles going from point A to B. When a road gets congested, the AI would know to change path to get to the location more efficiently. Best way to visualize this is the traffic issue in every simcity-like game.

The worst case I can think of for now is to just perform A* with a modifier attached to the cost function. I can think of ways to optimize this but it will eventually stack up.

Are there better alternatives?

\$\endgroup\$
  • \$\begingroup\$ We don't support questions asking for technology recommendations. Please read the help center. \$\endgroup\$ – Bálint Oct 17 '17 at 14:21
  • \$\begingroup\$ @Bálint I rephrased the question to ask for the existence of such an algorithm \$\endgroup\$ – DarkDestry Oct 17 '17 at 14:52
  • 1
    \$\begingroup\$ I've never heard of this referred to as load balancing path finding (to me that suggests the problem of splitting the work evenly among multiple cores), I've always heard of it as multi agent pathfinding. Sometime the problem includes formations (coordinated movement) constraints; algorithms exist for both variants, searching with the correct terms will yield several. \$\endgroup\$ – Pikalek Oct 18 '17 at 20:34
  • \$\begingroup\$ @Pikalek Thanks for informing me of the correct terms. \$\endgroup\$ – DarkDestry Oct 30 '17 at 9:48
2
\$\begingroup\$

Load Balancing is used confusingly here, but yes, there are path finding algorithms that consider congestion.

This answer briefly introduces Continuum Crowds algorithm that will avoid congestion, and will even prefer paths that "go with the flow" over going "against the flow."

It does not just solve how to get from A to B, as A-Star does. Instead it solves how to go from anywhere on the map, to B. The agent then just follows a gradient, which is dynamically updated as congestion changes: if a door suddenly opens, agents will change their course if it benefits them, until the doorway gets flooded, and they adapt again.

Look at the videos linked by the stackexchange answer I mentioned.

Note that for small crowd sizes, Continuum Crowds is a lot more expensive. Yet for huge crowd sizes, Continuum Crowds is much more efficient than doing many A* paths.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.