CODEWITHSUNDEEP
javascripthtmlpath-findinga-star
james
james

Reputation: 1041

Mass astar pathfinding

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

Upvotes: 5

Views: 1703

Answers (2)

Metalstorm
Metalstorm

Reputation: 3242

Just cache the result.

Store the path as the value in a hash table (object), give each node a UUID, concatenate the UUIDs to form a unique hash table key and insert the path into it.

When you retrieve the path back out of the hash table, walk the path, and see if it's still valid, if not, recalculate and insert the new one back in.

There are many optimization that you can do :)

Like c69 said swarm AI or hive mind come to mind :P

Upvotes: 0

c69
c69

Reputation: 21517

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

Upvotes: 2

Related Questions