Pathfinding in multi goal, multi agent environment

Posted by Rohan Agrawal on Game Development See other posts from Game Development or by Rohan Agrawal
Published on 2011-11-23T21:20:19Z Indexed on 2011/11/24 2:22 UTC
Read the original article Hit count: 349

Filed under:

path-finding

I have an environment in which I have multiple agents (a), multiple goals (g) and obstacles (o).

.  .  .  a  o  .  .  .
.  .  .  .  o  .  g  .
.  a  .  .  .  .  .  .   
.  .  .  .  o  .  .  .
.  o  o  o  o  .  g  .
.  o  .  .  .  .  .  .    
.  o  .  .  .  .  o  .
.  .  .  o  o  o  o  a

What would an appropriate algorithm for pathfinding in this environment?

The only thing I can think of right now, is to Run a separate version of A* for each goal separately, but i don't think that's very efficient.

Related posts about path-finding

Do I need path finding to make AI avoid obstacles?

as seen on Game Development - Search for 'Game Development'
How do you know when a path-finding algorithm is really needed? There are contexts, where you just want to improve AI navigation to avoid an object, like a space -ship that won't crash on a planet or a car that already knows where to steer, but needs small corrections to avoid a road bump. As I've… >>> More
Why is Reinforcement Learning so rarely used in pathfinding?

as seen on Game Development - Search for 'Game Development'
The venerable shortest-path graph theoretic algorithm A* and subsequent improvements (e.g., Hierarchical Annotated A*) is clearly the technique of choice for pathfinding in game development. Instead, it just seems to me that RL is a more natural paradigm to move a character around a game space. And… >>> More
Pathfinding Algorithm For Pacman

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I wanted to implement the game Pacman. For the AI, I was thinking of using the A* algorithm, having seen it on numerous forums. However, I implemented the Breadth First Search for some simple pathfinding (going from point a to point b with certain obstacles in between) and found it gave the optimum… >>> More
Graphical sandbox for pathfinding

as seen on Stack Overflow - Search for 'Stack Overflow'
If you needed a clean and consistent sandbox for pathfinding what would you use? I want to experiment with different pathfinding algorithms by sending virtual units (robots) around obstacles on a geometric plane. But I don't need a feature overkill like a game engine or Flash might have, just an… >>> More
method for specialized pathfinding?

as seen on Stack Overflow - Search for 'Stack Overflow'
I am working on a roguelike in my (very little) free time. Each level will basically be a few rectangular rooms connected together by paths. I want the paths between rooms to be natural-looking and windy, however. For example, I would not consider the following natural-looking: B … >>> More

Developer IT

Pathfinding in multi goal, multi agent environment - Developer IT

Pathfinding in multi goal, multi agent environment

path-finding

Related posts about path-finding

Do I need path finding to make AI avoid obstacles?

Why is Reinforcement Learning so rarely used in pathfinding?

Pathfinding Algorithm For Pacman

Graphical sandbox for pathfinding

method for specialized pathfinding?

Categories cloud