Sign in to follow this  
shorter

A* + Influence Maps = ?

Recommended Posts

shorter    122
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. Do you add it to the heuristic (H), so that there's a tendency to look for paths in preferred directions? Or do you modify the cost function (G) to actually make the calculated cost of moving towards an enemy (if the unit's behavior is set to 'cowardly', say) higher than moving towards an ally? Thanks in advance. Happy Flightless Bird Day!!

Share this post


Link to post
Share on other sites
Extrarius    1412
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.

Share this post


Link to post
Share on other sites
civguy    308
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.

Share this post


Link to post
Share on other sites
Timkin    864
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Uh... Timkin, mildly confused, if an Influence map is the discrete equivalent of a conservative field, then it wouldn't matter which path you take, the work done on each path would be the same right?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this