I'm using an A* implementation built upon an influence map (small map, grid based, diagonals are OK). The basic setup is that each actor in the game has a medium sized surrounding circle of influence, with a downward sloping gradient of value. In other words, each actor has a 2D sphere of influence around them, sort of like: 0000000 0111110 0122210 0123210 0122210 0111110 0000000 Where the 3 marks the actual position of the actor, and the numbers are then the "influence" each actor is imposing on each grid square of ground in the nearby area. I'm using an "occupance" influence map, which means that all actors "add" their influence values into the general influence map. The summed map is then used by various actors to pathfind from place to place. By having the actors re-path quite frequently (I can afford this, since I have a very small map and few actors), it has the effect of performing collision avoidance while also allowing me to custom tailor costing functions for various actors so they will still favor certain paths while answering the dynamic avoidance. My question is this: I'm currently using a combination heuristic (manhatten distance, plus the influence data), but I'm getting the feeling that some of my headaches are because the combination is adding up in ways that violate the premise of A*: do not underestimate your heuristic. I think I'm getting bad paths, and possibly cyclical paths (since I'm using more search steps then I estimate I need) to get around. So, does anybody have any good ideas for a better costing system, as welll as any ideas in general as to how to improve my system? Thanks in advance.... Lederhosen

Hi,

Your heuristic seems good to me.

Are you sure your A* "works"? I mean, before throwing agents in a dynamically modified map, have you tried having 1 agent pathfind over a static map? A map you know what results should be?

Also, its just an opinion, but I believe that your influence would be cooler if "oriented" when an agent moves. What I mean is that say, an agent going to the right would leave something like :

0000000
0000010
0001210
0013221
0001210
0000010
0000000

This way, an other agent could pass right behind him without avoiding an "old trail".

Hope this helps

Eric

Yeah, it does orient. I'm actually experimenting with all kinds of shapes due to actor type, action, etc.

Yeah, the A* works. If there's an empty map, or even a few people in the map, it seems to work just fine. It's when there's a lot of people, moving fast, when things seem to mish-mash. I was assuming it was due to unforseen combinations happening during these blender moments.

Thanks.
Lederhosen