Original Post
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