A* + Influence Maps = ?

Always add it to G, but if you can quickly calculate a better heuristic, then by all means do so.

You want to add it to G as stated above, but you also want to take it into accout in the heuristic though I'm not sure how to do that easily (maybe take some random samples along a line to the target and take the average of those as the average cost all the way to the target?) because that'll make it generate the right path faster.

Also, in the other thread you said you're using the dx+dy distance as H for your hex map, and really I don't think that is a good idea as it is designed for square tiles where you can only move in 4 directions and will overestimate the distance for hexes which makes it a bad heuristic.

A better one for hexes would be to take the straight-line distance, divide by hex width (longest distance across a hex with side length = 1 is from corner to opposite corner which is 2 units, so 2 times the side length of your hexes) then multiplied by the lowest transition cost. Calculating this new H might be slightly slower, but overall it should speed up your search by making fewer nodes get searched.

Quote:

Original post by Extrarius You want to add it to G as stated above, but you also want to take it into accout in the heuristic though I'm not sure how to do that easily (maybe take some random samples along a line to the target and take the average of those as the average cost all the way to the target?) because that'll make it generate the right path faster.

Just the typical nitpick: It won't necessarily give you the "right path" (lowest cost) if you do approximations as suggested above. And on the other hand, improving heuristic won't give you right path faster if computing the heuristic takes very long.

Mmm, interesting...

An Influence Map is a discrete version of a conservative Potential Field and therefore one can obtain a lowest 'cost' path between any two points in the field by choosing the path that minimises the energy function along the path, which equates to finding the path of minimum work to generate the transition from the starting point to the end point. Thus, work becomes the cost function of the search algorithm. In this case, the work done in getting from the start node in the search tree to the current node is your node cost and you need a heuristic estimate of the work done in getting from the node to the goal. The combination of the two is your estimate of the path cost through the current node (from the start to the goal).

Cheers,

Timkin

Quote:

Original post by shorter How do you incorporate an influence map into pathfinding? Many of the articles I've seen on A* have a mention somewhere of "and if you want to account for reactions to enemy or friendly units, you can add an influence map" but then proceed to not detail recommendations on how that's done.

Shorter: Please have a look at the demonstrator I wrote to illustrate the "Tactical Pathfinding with A*" chapter in Game Programming Gems 3. The demonstrator (along the lines of James Matthews' A* Explorer, on which it is based) allows you to place obstacles and threats, configure how the influence "being in the line-of-fire" is determined and interpreted in the cost function, and visualize the results (path and search space). In particular, it shows the sometimes drastic consequences for the search space. The demonstrator comes with source code and examples. You can download the demonstrator from ( http://www.cgf-ai.com/products.html#tacastarexplorer ) and you can see a brief explanation together with screen shots can in the site's old news ( http://www.cgf-ai.com/old_news.html ).

I've added costs for "being in a threat's line of fire" to the G component, but did not add it to the H heuristic: efficiently predicting how much cover you'll at least have or not have in the remainder of the path is pretty much impossible.

William