Hi all, I'm new around here, just registered so that I could ask this august body this question. Let me introduce myself a little bit before getting to the question though. I'm a hobbyist programmer. My most successful effort has now been spun off to a seperate development team, it's a online version of the Game of Thrones boardgame. I lost some momentum when the publisher of the game objected to our creation of the online version, though I understand they have come to an agreement with my friends who are hosting the game now. My current project is a hex based medieval setting wargame, using the Hârn game world setting and elements of the mechanics combined with some inspiration from GURPS mass combat rules. This is the first time I've tried to build any real AI into a game. For now, I'm not concerned with an AI opponent, but rather I want the units to be very slightly autonomous, so the players can just tell them their movement goal and the units will find a good path to it. I've implemented A* on the hex based grid, after reading Amit and Patrick Lester's excellent articles on the subject, and I'm finding some interesting behavior. I'm hoping someone else has encountered and solved this problem already. :) The way I'm representing the map, movement from hex to hex is based on the terrain of the destination hex as well as the nature of the hexside that you cross to get there. Hexsides can have one of two characteristics - a river can run along the hexside (increasing movement cost for streams and preventing movement altogether for rivers) and a road can cross it (lowering movement cost and allowing the unit to ignore the terrain of the new hex). A road crossing a river is assumed to be a bridge and takes priority. Here's an example of the map: Because of the hexside movement cost feature, my cost calculation function takes into account both hexes involved in a step. This generally seems to work fine, but I'm running into a problem that I'm not sure how to get around. Basically, the A* algorithm stops when you've found a neighbor to the target hex. However, sometimes the neighbor you have found is not the best neighbor to step into the target hex from. Suppose the target is adjacent to a river - the path should find the bridge down the way, but the A* algorithm stops when it finds the neighboring hex across the river. Let me offer a concrete example here, based on the link I posted above. A path from 1507 to 0812 correctly makes an effort to restrict stream crossings to a minimum (streams are fordable at a signifigant but not impossible cost). The path generated is 1507 1408 1307 1207 1107 1008 1009 1010 0910 0911 0812 - basically heads up the stream, crosses at Dunlorik and approaches the target hex from the north. However, if the target is 1010, the path found will have too many stream crossings, because the algorithm will terminate after finding a neighbor to 1010. The path found, in this case, is 1507 1508 1409 1308 1209 1109 1010. Because the cost to enter the light green hexes is 30 and the cost to cross a stream is 120, it would be *much* more efficient to take the path 1507 1508 1409 1308 1209 1108 1009 1010. So what I'm envisioning is some change to the algorithm that continues to evaluate alternative paths to the target for some time after finding the first one, but I'm not sure how that should be done. I've also pondered finding a reverse path from the target back to the source, and somehow combining the two, but I can imagine cases in which the combination is not easy to accomplish. Any advice would be greatly appreciated! Regards, Scott [Edited by - shorter on November 23, 2004 10:01:25 AM]

Instead of stopping the search when a node adjacent to the target is reached, stop it when the target is reached. Am I missing something?

Alvaro,

That's not really how the algorithm works. The "current" hex that's being examined is always, conceptually, a *possible* step along a potential path - examining the target hex as a "current" hex isn't necessary because it's known to be the final hex of the path.

I actually had an inspiration over lunch today, which is that the algorithm should stop when every (valid) neighbor of the target has been examined. Then the path through each neighbor is compared and the lowest cost alternative is chosen.

I'll let y'all know how it works.

Okay I think it works. Here are the modification's I had to make:

1. terminationCheck() is now called whenever the current hex is adjacent to the target. It determines whether every valid (i.e. in-bounds) hex neighboring the target hex is either in OPEN or CLOSED - in other words has the cost to each neighbor been calculated.

2. If yes, find the lowest total of cost to the neighbor hex + cost to step to target from neighbor hex, build the path back to the source from that.

3. If no, keep searching.

4. In the main loop, had to add code such that the target hex would not ever be chosen as the current hex.

Now the path from 1507 to 1010 that's calculated is, as one would expect, 1507 1408 1307 1207 1107 1008 1009 1010.

I haven't completely tested it, but it seems much better.

I think alvaro had it correct. Simply stopping once the target node is selected as the current node, you have examined all the nodes needed to find the shortest path.

Your method is inefficient because, if for example the target node has a river on 5 sides, it might take a large number of steps for all 6 sides of the target to be explored, but it would be explored very soon after the riverless neighbor node is found (since moving from the neighbor to the target would probably cost very very little {0 in the typical square tile implementation, possible more since yours is more advanced})

I don't think so Extrarius - if you simply step on the target hex and examine it's neighbors, then all you're doing is finding paths to the neighbors that go through the target hex. What you need to do is find alternate paths to the target hex via the neighbors instead.

The algorithm isn't terribly inefficient - I haven't quite figured out how to tune the heuristic yet, but I can get best path in 100ms on my laptop, and fairly efficient paths in 50ms. I know that's not enough for realtime games, but I think it's decent, considering it's implemented in PHP. :)

shorter: Once you get the target hex to the top of the open list, you should have the absolutely shortest path to it. By then, all the links that have potentially lower costs have already been explored if you have an admissible heuristic (I forget the exact requirements but iirc it was mainly just don't overestimate the distance to the target), so whichever neighbors haven't been explored already will have higher costs than the neighbors of the target that have already been explored.

"Basically, the A* algorithm stops when you've found a neighbor to the target hex."

As others pointed, you should know A* must stop ONLY when the current node popped from the open list is the target one, since your example paths are correct. If not you have a flaw in your A* implementation or the way you have understood it. The termination check should be done right after you pop the best open node and only there, and it should only consist of checking if its the target node. Do not do it when you generate successors and check those successors, its wrong; or do not check if the node is next to the target, its wrong. Really, dont do it. Just use the standard A* algorithm you find everywhere and write your own cost functions and successors generation functions.

Now, if your problem is that your path looks sub-optimal (your example), its a completly different matter, and most probably lies with your estimation cost function H. You are problably using hex distance as H? H should ideally be as accurate as possible, as close as possible to the real best path. Maybe you can try this :
- to estimate the cost between Hex1 and Hex2, trace a line of hex from Hex1 to Hex2 and compute the actual cost of traversing this line.
This should give you better paths.
Now the problem with Hexs is that there is not such thing as a straight line in some cases, a line may pass by 2 hexes at the same spot, so you'll have to solve this as well ;)

Anonymous said: "As others pointed, you should know A* must stop ONLY when the current node popped from the open list is the target one, since your example paths are correct."

Perhaps I'm misreading Patrick's tutorial (I'm using the version at http://www.policyalmanac.org/games/aStarTutorial.htm)

In his summary of the algorithm, he states that you stop either when you add the target to the open list or when the open list is empty. Adding the target to the open list is not the same as evaluating it as the current node. Is Patrick misrepresenting the algorithm, or am I misunderstanding his description?

It must be that he is incorrect, as the A* algorithm finds the shortest path and you have noticed that implementing his algorithm does not do so. His way will generate a usually good path, but it doesn't take into account the weight of the neighbor->target link, which can be extensive. In the more common(for tutorials at least) application of A* to areas where each move has the same weight (or even slightly different weights like 14 for diagonal and 10 for up/down/left/right) the difference would hardly be noticable, but when you have weights that vary greatly as you do the difference can be big.