The goal of a heuristic in A* is to return the length of the most direct path from the current node to the destination, assuming no obstructions. For a game in which movement is constrained to right angles, manhattan distance (abs(x1-x2)+abs(y1-y2)) makes sense. Approximating a diagonal path by moving "left, up, left, up, left, up" is going to be just as long as the following path: "left, left, left, up, up, up." So that''s a perfect heuristic for a world in which movement is constfrained to right angles. But what about a world where movement is constrained to other arbitrary angles? The most common - and therefore most useful - example I can think of is a world in which movement is constrained to 45 degree angles. What kind of heuristic could be used for that? I have not solved the problem, but here are my thoughts so far: Movement due north, south, east, or west has a cost of 1. Movement northeast, northwest, southeast, or southwest has a cost of sqrt(2). Given the angle between two points (atan2(y1-y2, x1-x2)), I think that we can make some assumptions: We can find the angle between that angle and the nearest 45 (that is not also a 90), and the nearest 90. Then, the ratio of 45-degree movements to axial (90 degree) movements would be inversely proportional to the ratio of these distances. The cost of each of these 2 types of movement is also known, as I mentioned before. But, now given the ratio between the two types of movements and the cost of each, I can''t figure out what the length of the optimal path would be. Can you?

As long as your heuristic is admissible, that is it does not over estimate, then it''ll work. It doesn''t have to return the most direct path. In your case, an heuristic that over estimates would be the manhatten distance. Since if your squares are diagonally opposite, the manhatten distance will be twice as long as the actual distance.

That means that for any problem, you can still use the regular distance formula to perform the heuristic, since sqrt((x1 - x2)^2 + (y1 - y2)^2) will never be larger than the actual distance.

---

dHarding.net - Just click it.

quote:

---

Original post by TerranFury
But, now given the ratio between the two types of movements and the cost of each, I can''t figure out what the length of the optimal path would be.

Can you?

---

Yeah.
Estimated Distance = (minimum (deltaX, deltaY) * sqrt(2)) + (maximum(deltaX, deltaY) - minimum(deltaX, deltaY))

The first half of the equation counts how many diagonal steps you would have to take, given an open map with no obstacles. Example: if target is 10 steps to the west and 4 to the north, the optimal path would involve 4 steps in a northwest direction. Multiply that by sqrt(2) for the distance travelled northwest. You now need to walk the other 6 steps (out of 10 to the west in total), and the 6 comes from taking the larger of the 2 numbers and subtracting the smaller. (You can also get this result by subtracting them in any order and taking the absolute result.) This is the 2nd part of the equation.

It should be marginally better than simple Pythagoras since it won''t underestimate by as much.

Thanks Kylotan; that''s a pretty common-sense solution. Too bad I couldn''t think of it! I can guess how I''d use that basic idea to deal with any arbitrary angle (though I''m not sure why you''d want anything other than diagonals; that''s just useless curiosity on my part).

And Dean, I know I can use any admissable heuristic. Heck, h() could simply be 0, and I''d just end up with Djitska''s (sp?) algorithm (not necessarily a bad thing). And if I use an overestimate, I''ll just end up with A instead of A* (not a good thing).

Except, my current implimentation of A* is all screwed up, and doesn''t work at all half the time, so I think I''m gonna have to fix that before I fool around with adding diagonal movement! Now if I can only track down these bugs...

Okay. Let''s see what we can do with the case of regular and diagonal moves, with diagonal moves taking ~1.4142 units of distance (the approximate square root of two).

Any optimal move can be represented as a diagonal and an axial component. The diagonal move lines up with the objective, then the axial takes up the slack in one dimension (the one that is further away).

So if dx <= dy, the heuristic could be (dx * sqrt(2)) + (dy-dx).
and if dx > dy, the heuristic is (dy * sqrt(2)) + (dx - dy).

And to use my favorite operator, the ternary, the full expression is

h = (dx < dy) ? ((dx * sqrt(2)) + (dy - dx)) : ((dy * sqrt(2)) + (dx - dy))

this can be optimized slightly.
(dx * sqrt(2)) + (dy - dx) = dy + dx * (sqrt(2) - 1)

So:

h = (dx < dy) ? ((dx * 0.4142) + dy) : ((dy * 0.4142) + dx)

Have a good evening... don''t forget to tip your waitress.

Just be careful using Euclidean distance as a heuristic for A* search. It is only the shortest distance between two points in Euclidean spaces. Admittedly, most game worlds are Euclidean, or at least locally approximated by a Euclidean space, but this is not always the case. Here's a simple non-Euclidean pathing problem. Your game has a space ship in orbit around a planet and the ship can drops bombs onto the surface of the planet directly below it. Perhaps the ship is an NPC bombing your cities? The game AI must determine the orbital adjustments necessary to move between the locations of the cities. If you model the orbital space as the surface of a sphere then the shortest distance between two points on that sphere is NOT the Euclidean distance, but is rather the arc segment on the Great Circle that intersects those two points. A Great Circle is the circle inscribed on the spheres surface by a bisection of the sphere that cuts through the central point of the sphere.

As Dean pointed out, the heuristic doesn't have to be shortest distance. A search heuristic can be almost anything. A* requires only an admissable heuristic and one that is monotonic. The admissability criterion is transferrable to the cost funcation and so we can think of admissability as: a heuristic is admissable if, for an estimated cost of a path through the node i given by f(i) = g(i) + h(i) (where g(i) is the actual cost of moving from the start node to node i and h(i) is a heuristic measure of the cost of getting from node i to the end node) then h is admissable iff f(i) <= f*(i), the actual cost of the path traversing the graph and passing through node i.

Monotonicty requires that the sign of the derivative of the cost function never changes.

Given these requirements, there are many heuristics (possibly infinitely many) for a given search problem.

Hope this helps with understanding A* better.

Cheers,

Timkin

Edited by - Timkin on August 27, 2001 2:04:10 AM

If diagonal cost is the same as straight, then the shortest path is just Max(dx, dy). But, the other thing you have to do is take into account how complex the path might be, if it involves lots of twists and turns, and you can be sure of that before you begin the search, you should overestimate that straight line/manhattan/whatever distance by a bit. If you can''t be sure what it is going to be like, you could even do a quick test, say ratio of walkable to unwalkable in the map, or walkable to unwalkable along the straight line between A and B.

quote:

---

The goal of a heuristic in A* is to return the length of the most direct path from the current node to the destination, assuming no obstructions.

---

Actually, it isn''t. The best heuristic you could get would be one which doesn''t assume no obstructions, so it can just tell you the distance from A to B. If you did that, then you would have a really efficient pathfinder. Unfortunately, to get such a heuristic, would require finding the path to the goal anyway, destroying the purpose of the heuristic . So, just remember to take into account the obstructions where possible, and the search will be more efficient.

Trying is the first step towards failure.

quote:

---

Actually, it isn''t. The best heuristic you could get would be one which doesn''t assume no obstructions, so it can just tell you the distance from A to B. If you did that, then you would have a really efficient pathfinder. Unfortunately, to get such a heuristic, would require finding the path to the goal anyway, destroying the purpose of the heuristic . So, just remember to take into account the obstructions where possible, and the search will be more efficient.

---

True. I just skipped the obvious fact that, since A* is finding the best path, the path is unknown, so the distance is unknown. Therefore, the highest underestimate you can make is one which assumes no obstructions. (Since obstructions lengthen the path, if a heuristic assuming obstructions were used when there were none it would overestimate the distance and would therefore not be admissable) You''re right, you could probably add 2 to the heuristic cost if an obstruction is in an adjacant tile between the current node and your goal, or something like that, but it would probably be more trouble than it''s worth! It''s 4 (or 8) more conditionals, and probably not much of a speed improvement. But even though it isn''t practical, I like your idea, simply because I would have never thought of it!

I don''t use it either , normally I just shove in an extra parameter to all my paths, the "Overestimate" value, which is determined by me, or the person who created a map, or whatever. It could possibly be automated, but that isn''t as exciting

Trying is the first step towards failure.

To those talking about using an overestimating heuristic, you''re making a crucial mistake... the heuristic for a given node should NEVER overestimate the actual cost of a path through that node. If you do overestimate the cost, then you will not be guaranteed of a solution, let alone an optimal one.

Timkin