A* heuristic to create Bresenham lines

Question

From what I understand about A* heuristics and how the Bresenham algorithm works, this may not be be possible since only the current state and goal state are passed to the heuristic function. But maybe someone has a clever solution to this problem.

I am using A* to plan a path on a grid, and I would like a heuristic that would cause the best path to follow a Bresenham's line when there are free spaces between the current state and the goal or the next turn around an obstacle.

Here are some images to illustrate the problem.

Manhattan distance:

If movements in the world acted like a checkers on a grid, this would be perfectly fine, but I'm eventually going to convert the A* path to motions on a continuously plane, so this does work very well.

Euclidean distance:

Better, but still not perfect. Notice the straight line at the end. The diagonal could have just as easily remained a diagonal, which is what I want.

What I Want:

Bresenham lines are draw to the next turn or goal.

I found a good resource here, http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html that touches on what I am looking for, but only seems to work for drawing Bresenham lines from the start to the goal. What I want are Bresenham lines being draw to the next turn around an obstacle too.

Any ideas for a good approach to this problem?

Answer 1

Can you modify the cost function on the fly so that the cost of going forward increases with the accumulated error?

The idea is, at the start of the algorithm, calculate DX and DY as in standard Bresenham. (Assume for the rest of the example that DX > DY > 0. Modify accordingly for other directions.)

Then for every visited neighbor node, track the Bresnaham error:

if (neighbor.X > this.X) 
   neighbor.err=this.err+DY 
else if (neighbor.Y > this.Y) 
   neighbor.err=this.err-DX

Then modify your cost function to favor increasing X, but add if (err >= DX/2) then cost=cost+FACTOR. In a map where all other costs are equal, this should trace the right line.

The other thing you might need is special handling when the path steps around an obstacle, otherwise you could get strange wall-following paths similar to the "cross-product with obatacles" example in your linked article. You could possibly handle that situation by recalculating DX and DY whenever the neighbor node is not in the +X or +Y direction. (Unfortunately, this likely requires tracking a separate DX, DY, and error for each node, which may be too much overhead)

Disclaimer, I haven't implemented an A* or Bresneham algorithm in years. This whole idea may be unworkable

Answer 2

Have all your move alternatives be the corners visible from your current position (or the goal if it is visible), and once you find the shortest path, draw Bresenham lines between all your stops.