Can't you just change your heuristic? I assume you're using Manhattan Distance now. That's nice in that it's optimal for a square grid topology, but it gives no preference for straight-line paths. If you use, say, a Euclidian-distance heuristic instead, then on an open plane A* will reduce to a line-drawing algorithm.

Others, please confirm: I'm rusty.

If I'm right, that's the easy solution.

It won't reduce to a line drawing algorithm, because the amount spent moving one discrete tile horizontally is roughly 2/3rds of the cost of moving diagonally, while the improvement to the estimated distance in each case is almost identical, until the angle between the current point and the target becomes steep enough.

What about giving the heuristic a tiny preference (so that it only matters when considering otherwise equivalent-cost paths) for selecting paths that stray the least from a straight line (as measured by a dot product, for instance)?

The problem is that they won't be 'otherwise equivalent'. In a path from (0,0) to (100,1), once you get to about (50,0) it's adding about 0.4 onto the current path length by moving diagonally (as desired) rather than continuing on straight, whereas the amount cut off the estimated remaining path by being at (50,1) rather than (50,0) is about 0.01. So the amount of bias you'd have to apply would presumably be quite high, and that might create inoptimal paths at other times.

Hmm...

Looking at your illustration again I realize my comment about Manhattan Distance was silly, as if you'd been doing that then your character would have walked an L-shaped path.

I'm playing with this on paper. I still suspect that breadth-first search with a heuristic can reduce to line-drawing.

Example: Consider your 6x3 grid.

Let's number squares so we know what we're talking about: The top-left square is (1, 1), its neighbor to the right is (2, 1), and the neighbor below it is (1, 2) -- etc, so that the bottom right cell is (6, 3).

We probably agree that the 'ideal' path is,
(1,1)->(2,1)->(3,2)->(4,2)->(5,3)->(6,3)

We start at (1, 1). We add (2, 1), (2, 2), and (1, 2) to the OPEN list, and move (1, 1) to the CLOSED list. For these, the costs are,

C=P+T+H

where

P is the cost from the start to the parent cell,
T is the cost of the transition from the parent cell to this cell
H is the heuristic cost to get from the child cell to the goal.

(As you can see, I've split up the "parent cost" of A* (called G) into seperate P and T terms; I think that's clearer).

So, for these children, the costs are as follows:

(2,1):
P = 0
T = 1
H = 4.47
=> C = 5.47

(2,2):
P = 0
T = sqrt(2) = 1.414
H = 4.123
=> C = 5.54

(1, 2):
P = 0
T = 1
H = 5.10
=> C = 6.10

The lowest-cost one is (2, 1), so that's the one we look at.

Next, consider the children of (2, 1) not already in the OPEN list, and their costs. They are,

(3, 1)
P = 5.47
T = 1
H = 3.61
=> C = 10.08

(3,2)
P = 5.47
T = 1.414
H = 3.162
=> C = 10.05

Ah hah! (3, 2) has a lower cost than (3, 1)! So we go there!

Now we have in the OPEN and CLOSED lists (in no particular order, except that (3,2) is on top of the OPEN list -- I won't bother to keep things sorted as we won't hit that part of the OPEN list in this example):

OPEN: (3,2), (3, 1)
CLOSED: (2, 1)

Now consider the children of (3, 2) (not already in the OPEN or CLOSED lists). They are: (4, 1), (4, 2), (4, 3), (3, 3), (2, 3)

Of these, (4,1) and (2,3) increase the heuristic, so since I'm being lazy I'll say we can ignore (even though in an actual implementation you'd churn through and compute their costs, of course). I'll look at those remaining:

(4,2)
P = 1+sqrt(2) = 2.414
T = 1
H = 2.236
=> C = 5.65

(4,3)
P = 2.414 (as before)
T = 1.414
H = 2
=> C = 5.83

(3,3)
P = 2.414
T = 1
H = 3
=> C = 6.41

Of these, (4, 2) is the best. We do not continue on the diagonal when we better-approximate a straight line by moving along the axis!

Now, we have,
OPEN: (4,2), followed by (4,1), (4,3), (3,3), (2,3), (3,1), (2,2), (1,2) in no particular order.
CLOSED: (1,1), (2,1), (3,2)

Now consider the neighbors of (4,2): (5,1) is clearly going the wrong way. That just leaves (5,2) and (5,3).

(5,2)
P = 2+sqrt(2)
T = 1
H = sqrt(2)
=> C = 3+2*sqrt(2)

(5,3)
P = 2+sqrt(2)
T = sqrt(2)
H = 1
=> C = 3+2*sqrt(2)

We have a tie! But notice that if you only consider the part of the path that is remaining, either option leads to an equally-good approximation to the line: It's the difference between these two paths:

 __   \  vs.  \__

I have an intuition that this only happens for these very short paths.

I figure that little anomaly isn't too aesthetically annoying -- but if it bothers you, it can definitely be solved by adjusting your heuristic for paths of length <= 3, by choosing the path which results in the best r^2 fit of the last 4 points to a line.

With that exception, it does seem to reduce to line-drawing!

What about my understanding differs from yours, Kylotan?

Emergent
Using only knowledge of the current position and the goal position you won't be able to do a line-drawing heuristic, since it does matter what the starting position was!

Your heuristic does make the path more line-like, but for cases where distance w << h or w >> h it won't make a straight line.

You heuristic will trigger a diagonal step when:
sqrt((x-1)^2 + y^2) - sqrt((x-1)^2 + (y-1)^2) > sqrt(2) - 1

But what if, in the given example, the goal was placed in (100,3)?

Well still the heuristic wouldn't trigger a diagonal step until it is (4,2) fields away from the goal, since generally for:
sqrt(x^2 + y^2) and
sqrt(x^2 + (y-1)^2)
an large x will only decrease the difference between these two.

It would therefore move from (1,1) to (96,1) and only then it would begin to move diagonally.

Hope that made any sense, else feel free to ask for clarification.

Quote:Original post by Zredna
Emergent
Using only knowledge of the current position and the goal position you won't be able to do a line-drawing heuristic, since it does matter what the starting position was!
[...]
Hope that made any sense, else feel free to ask for clarification.

Yes, that makes sense.

Summarizing: You take a diagonal step when doing so improves your heuristic (vs. the lower-cost axial move) more than it costs extra.

Now if I'd only thought of things in those terms from the beginning!

You might still be able to pose line-drawing in terms of A*, though , with a heuristic that takes the global knowledge into account: Perhaps a linear combination of the perpendicular distance from the point in consideration to the ideal line, with the pythagorean distance to the goal (weighted so the first dominates, and the second serves only to keep things going in the "right direction.") The problem with this is that it would not particularly useful, as it assumed a straight-line path exists -- and if one did you'd just use something like Bresenham instead of bothering with A*.

I recall, vaguely, that you can do pathfinding in a world defined by convex polygons by pathing among obstacle vertices, and drawing straight lines in-between. It seems you could do that here -- in which case you'd be doing A* on a graph somewhat different from a grid.

Quote:Original post by Emergent
Summarizing: You take a diagonal step when doing so improves your heuristic (vs. the lower-cost axial move) more than it costs extra.

This is driven by the basic principles of heuristic search. We require that the cost function is monotonic and that the heuristic never over-estimates the true cost, which means that any two nodes will have a traversal cost between them greater than or equal to the difference between their respective heuristic costs to the goal. If the traversal cost equals the heuristic difference, the heuristic is an optimal assessor of cost.

In addition to this, if using the SLD heuristic, there is very little discriminatory power far from the goal for two neighbouring nodes on a grid. Hence the heuristic lends little weight to the ordering process of the nodes on the open list. This means you'll tend to favour taking the action with the lower local path cost, until such time as the heuristic dictates a different solution.