Sign in to follow this  
shorter

A* algorithm with hex edges

Recommended Posts

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: a 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]

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"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 ;)

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
To answer your question, let's look at A*'s behaviour in terms of expanding nodes. Assuming an admissible heuristic and a monotonic cost function, then it is provable that A* will search(expand) all nodes within a given cost contour before expanding any nodes in a higher cost contour. Thus, adding the goal node to your open list does not mean that you have considered all nodes within the cost contour that contains the goal. However, assuming no variation to the algorithm, at the time you remove the goal from the OPEN list, you will have searched every possible node (given your discretisation of the state and action space) within the cost contour of the goal. Thus, the search can be ended and the path back through the ancestors of the goal can be obtained as the optimal solution.

Timkin

Share this post


Link to post
Share on other sites
My implementation of A* finds the shortest path until I start adding hexside effects - that was the point of my post but perhaps I didn't say so explicitly.

"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."

I think this is the crux of the issue - if you don't have hexside effects, but just per-hex movement costs, then every neighbor->target cost will be identical, i.e. just the cost of stepping into the target hex.

Thanks for all the feedback - I will see if I can adjust the alg to meet your suggestions, but if not I will probably be pleased with the current behavior.

Share this post


Link to post
Share on other sites
Yeah, I've made this mistake too :). You have to wait until the target is popped from the list. Otherwise, you could wind up in the case where there's a good-looking node at the top of the list with a long traversal to get to the target. If you accept that as your best path, you might miss a node that didn't look quite as good but has a shorter final traversal.

I used the psuedo-code from Game Programming Gems 1 and it worked great (once I figured out I'd missed that subtlety :) ).

Share this post


Link to post
Share on other sites
The other problem that can be faced is that your heuristic can become inadmissible. That is, it may overestimate the cost. Let's say your heuristic is based on a function of straight line distance and average hex-edge traversal cost (since you obviously don't want to check every edge to the goal... which would just give you a modified brute force search). When you are far away from the goal, any particular straight line path to the goal will typcially have an actual cost close to the heuristic cost, since the sampling of different edge traversal costs on that path would be close to the global probability distribution and thus the mean of the path (a sample from the population) will be close to the population mean.

Close to the goal though sampling errors take over. You might find yourself only 3 hexes from the goal and expect 'average' traversal costs to the goal. Of course, there might be 3 bridges to the goal. The heuristic cannot account for that and so overestimates the cost to the goal. Thus, the A* algorithm will end up having to search all nodes within the cost contour corresponding to the overestimated cost, which means that it will no longer be optimally efficient. Given that the cost to search the tree grows exponentially with depth, even a small over-estimate of the true cost can cause a lot of extra computation.

How do you get around this? There's no easy way around it other than modifying your heuristic. I would suggest that you compute the discrete probability distribution for edge traversal costs (from a normalised histogram count of different costs, which can be obtained for static maps during offline pre-processing of the map) and use an underestimated heuristic cost corresponding to something like the lowest (first) quartile value of the distrbution.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Hmm, my heuristic at the moment is just the manhattan distance times the minimum movement cost (i.e. road/bridge movement).

After a very small amount of experiementation, I found that sometime it will find optimal paths even when I add a large scaling factor to the heuristic, but if there's more interesting terrain between start and finish, even 1.5x the above formula starts to find non-optimal paths.

Which sort of points to the question of how vital it is that the very best path is found. I'm not modeling the AI of supergeniuses that are going to actually do cost-benefit analysis on different routes from A to B, rather they're gonna use their best guess or their captain's stubborn hunch. However, since as mentioned my game does all of it's pathfinding non-interactively, efficiency isn't such a concern that I'm looking for ways to compromise on it right now.

I have a question about influence maps now and how to integrate them into A* but I'll make that a new thread.

Happy Flightless Bird Day!

Share this post


Link to post
Share on other sites
Just be aware that underestimating the heuristic by 'too much' is almost as bad as overestimating the heuristic. The larger the underestimate the more and more the search behaves like an uninformed greedy search, which means you expand more nodes than necessary to find the optimal path to the goal. Optimal efficiency for A* occurs when the heuristic equals the true cost to the goal for every node.

Timkin

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