So my latest game creation will be using the A* pathfinding algorithm. In brief, A* works from it's starting point, evaluating each of the neighbouring squares and seeing how far away it is from the target. It picks the nearest one to the target. I've bolded "nearest" here because in gaming, calculating the distance to the target is a somewhat hot bed of potatoes (if that's a metaphor?). Let's look at an example:
Here we have a grid and we need to get from point A to point B. The A* algorithm sums up the cost of moving to an adjacent square (g-cost) and adds in the distance from that square to the target (h-cost). It does this for every square and moves to the square with the lowest value. There's a bit more to it than that (a great article can be read on it here), but the key problem we have is with how to calculate the h-cost.
We could use the Euclidean Distance, which is a pretty straightforward formula once you get your head round it, and obviously very accurate. But this involves using something that game programmers try and avoid like the plague. The dreaded Square Root !! Of course, using square roots in the example above would be fine. We're talking about 6 diagonal gaps to fill before we reach the target. But what about a bigger grid? Or even multiple start points with multiple targets? I hope you can see that it might not always be the first choice.
And here's where I bring in the Manhattan Method (or Manhattan Heuristic as it might be more appropriately called). All the Manhattan Method does is work out how many units horizontally and vertically it would need to move to get to the target.
Clearly it's not the quickest route, but because the same algorithm is being applied to all the adjacent squares to A, you can (hopefully) see that the one to the bottom right of A is going to return the best score. Why am I using units of 10? Don't worry about it for now, but read the A* article above and it should become clear why.
It's lovely and fast because no division or square root calculations need to be done. Everybody's happy... Right?
Well I thought I was until a rather strange thing happened when I put a wall in the way:
Now the squares to the right of A are not available and are hence their distance is not considered. I have diplayed above the two points with the lowest Manhattan distances. But which point do you think has a lower "Manhattan" distance above, Point 1 or Point 2? I hope you are thinking that it is point 2, and you'd be right. But I'm afraid you'd also be right if you picked point 1! Don't believe me? Well, let's take the number of steps inbetween point 1 and B:
As you can see it's 6 places (or 60 as I'm using units of 10 here). Let's look look at point 2:
Oh dear, also 60 units away. So depending on which order you work through the adjacent squares, you may end up with a rather skewed route towards your goal. I should point out that the A* algorithm still finds it's way to the target in this example, but it might take a rather skewed route!
So how do you get round this? Well, I am pretty sure this anomaly will only occour in situations where the source and the target are either vertically or horizontally equal. Therefore, the Manhattan Heuristic could penalise the straight route by a small number (eg 1).
Interested to hear others !
No comments:
Post a Comment