Mass astar pathfinding

Question

I'm trying to create a tower defence game in Javascript.

It's all going well apart from the pathfinding..

I'm using the astar code from this website: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript which uses a binary heap (which I believe is fairly optimal)

The problem i'm having is I want to allow people to block the path of the "attackers". This means that each "attacker" needs to be able to find its way to the exit on its own (as someone could just cut off a single "attacker" and it would need to find its own way to the exit). Now 5/6 attackers can pathfind at any one time with no issue. But say the path is blocked for 10+ attackers, all 10 of them will need to fire its pathfinding script at the same time which just drops the FPS to about 1/2 per sec.

This must be a common problem for anyone who has a lot of entities pathfinding at anyone time, so I imagine there must be a better way than my approach.

So my question is: What is the best way to implement mass pathfinding algorithm to multiple "bots" in the most efficient way.

Thanks,

James

Answer 1

Use Anti-objects, this is the only way to get cheap pathfinding, afaik : http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

Anti-object basically mean that instead of bots having individual ai, you will have one "swarm ai", which is bound to your game map.

---

p.s.: Here is another link about pathfinding in general (possibly the best online reference available): http://theory.stanford.edu/~amitp/GameProgramming/index.html