Influence Maps for Pathfinding?

Posted by james on Game Development See other posts from Game Development or by james
Published on 2012-11-16T18:24:34Z Indexed on 2012/11/16 23:18 UTC
Read the original article Hit count: 210

Filed under:

I'm taking the plunge and am getting into game dev, it's been going well but I've got stuck on a problem.

I have a maze that is 100x100 with 0,1 to indicate if its a path or a wall.

Within the maze I have 300 or so enemies and a player.

The outcome I'm looking for is all the enemies work their way towards the player position.

Originally I did this using an A* path finding algorithm but with 300 enemies it was taking forever to path find each one individually.

After some research I found that an influence map / collaborative diffusion would be the best way to go.

But I'm having a real hard time working out how this is actually done.

Firstly.. How do you create a influence map?

From what I understand each of my walls with have a scent of 0 so that makes them impassable.. then basically a radial effect from my player position to each other cell (So my player starts at 100 and then going outwards from that each other cell will be reduced value)

Is that correct? If so,.. How would you do that (Math magic?)

My next problem is if that is correct how would my "enemies" stop from getting stuck if they have gone down the wrong way? As say if my player was standing on the otherside of a wall if the enemy is just looking for larger numbers wont it keep getting stuck?

I'm doing this in JavaScript so performance is key.

Thanks for any help!

EDIT:

Or if anyones got a better solution? I've been reading about navmeshs, steering pathing, pre calculating all paths on load etc etc

© Game Development or respective owner

Related posts about path-finding