# Influence Maps for Pathfinding?

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

• You can use a breadth first search like Dijkstra's from the player out. Each step would point back the way it came. Then enemies can just use the direction for the grid location they're currently in to path towards the player. – MichaelHouse Nov 16 '12 at 18:53
• But it sounds like you're looking for a discussion (not what this site is about). I recommend you search around the site, looking at the different path finding questions. When you decide on something to implement, go for it. Come back and ask a question specific to any problem you face when implementing it. – MichaelHouse Nov 16 '12 at 18:57
• ahhhh I thought this site was more for this kind of question. I thought stackoverflow was for when you get down to the actual code I'll take a look around see what I come up with and head back – james Nov 16 '12 at 18:58
• @James Both this site and GameDev.SE deal with code; that isn't how they're divided up. From our FAQ (which I suggest you read): General programming questions more likely belong on Stack Overflow instead of here. A good rule of thumb is to ask yourself... "Would a professional game developer give me a better/different/more specific answer to this question than other programmers?" If yes, then feel free to ask it here. – doppelgreener Nov 17 '12 at 1:55

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.

Rather than searching from each enemy to the player, search outwards from the player to every enemy at once. This way, rather than doing 300 searches, you only need to do one.

More specifically, just do a breadth-first search (or djikstra's, if your graph is weighted) from the player outwards, until every enemy has been reached.

You could alter this strategy to work with A* by changing your heuristic EstimatedDistanceToEnd (aka h(x)) to be the minimum estimate to any enemy, but with a lot of enemies this may end up being slower than the simpler option. The heuristic must be consistent for this to work.

Also remember that you don't need to run your pathfinder every single frame for most games - often you can get away with only once or twice a second, or even less, depending on the game.

If that is still too slow, you could look into using D* lite to reuse information between subsequent searches. But, I would bet money that running a single breadth-first search a few times a frame will be more than fast enough.

• Good thinking. It's the same way I would do it too. – MichaelHouse Nov 16 '12 at 21:50

Rq1 : if one enemy'path encounters the path of another allready computed enemy's path, it just has to follow it to reach the player, which quite breaks down the cumulated length of path to compute.
Rq2 : If we take that into account, you might :
- compute the right path for near enemy only (?distance <10 ?), using rq1.
- And then just compute a few (8 ?? more ??) path from various location on the map,
- Then each monster's task is to reach the nearest path (...still using rq1). (This would lead to possibly non-optimal path for the far away enemies, but all the best for the poor player who will have to face the 300 monsters :-) )

• thanks for the answer. Because this is a learning experience I might actually try and create a simulator with different methods – james Nov 16 '12 at 19:06