cheap multi agent path planning algorithms

Question

I am trying to make a tower defence game where some critters are trying to make their ways through a 2D grid-like obstacle course. The idea is these critters cannot walk into the obstacles or into each other during their path, and they would like to get to the other side as soon as possible.

I just need a cheap, not-optimal solution that can path all the agents from one side of the map to another, moving in the grid (up-down-left-right) directions while not walking into each other nor into the obstacles.

I am not wanting an optimal solution, just one that looks reasonably greedily optimal would be nice (i.e. not like not moving the 2nd agent without completing the path on the first agent, etc).

I'm thinking about something with potential fields with a little bit of A* is as much as I am willing to compute. If there's anything simple to implement I'd be happy to know ! !

Answer 1

I would do a unique breadth exploration from the exit to get the shortest distance to exit of any position. Only obstacles (like walls) should be considered, not critters. This exploration should be done again each time an obstacle is added or removed. With some optimization, you may not have to recompute all the positions.

Then each time a critter should move, check if any accessible position has a better (lower) distance to exit. If not, the critter stay in position, else it moves to the one with the lowest distance to exit.

By "any accessible position", you can consider either up-down-left-right or something more complicated (moving more than one space, jumping obstacles and so on...).

Answer 2

A possible approach can be to use similar techniques to the ones used to solve some variants of sokoban.
First, you need to solve a one-to-all shortest path, in order to obtain the distance between any vertex and the destination on your original graph G, taking in account the obstacles, but not the critters.
Once you have that, you can consider the graph of configurations. A vertex of this graph is a configuration, meaning a representation of G along with the position of your critters.
You can define a heuristic h, which to a configuration associates a distance estimation, in this case the sum of the distances between the critters and the arrival.
All you have to do then is to run an A* algorithm on the graph of configurations. When you are in a configuration, the reachable configurations are the configuration where one of your critters has moved of one step on the grid.
The origin configuration is G with the critters in their original positions, and the destination configuration is G with the critter all on the destination vertex. The heuristic for A* is the one defined above.