Rapid multi agent pathfinding

I have been trying to design a good path finding algorithm that will support a large number of agents by default. A* is not very good at supporting more then once agent at a time, where their paths may intersect, and can require lots of fudges to get it to work correctly in these situations.  Also when A* is implemented over a grid based world, it can require additional processing to produce non grid aligned paths (path smoothing).

For this demo, I threw A* out of the window and took a potential field approach.  I used bi-linear interpolation when sampling the potential field so that each agent wouldn’t have to be grid aligned. The results are really cool, and I can simulate upward of 1000 agents without any performance hit. Perfect for a nice hack and slash dungeon crawler.

Advertisements

One thought on “Rapid multi agent pathfinding

  1. Love this! as always, you do a great job. I have been working on optimizations of A-Star for massive multi agent pathfinding, and only skimmed (and disregarded) potential fields as a possible solution = you made me take another look and I like the solutions it provides… must test more! Thanks again!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s