15

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.

The shortest path from red to green using the Manhattan distance heuristic

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.

The shortest path from red to green using the Euclidian distance heuristic

What I Want:

Bresenham lines are draw to the next turn or goal.

The best path I actually want, which uses Bresenham lines to get to the 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?

3
  • Did you ever end up implementing something for this?
    – AShelly
    Commented Jun 16, 2011 at 19:14
  • 1
    @AShelly I tried weighting the hueritic based on the path of a straight line from the previously visited cell among other things, but nothing seemed to do exactly what I wanted. I think you would need to drastically change A* or use a different algorithm altogether in order to solve this problem.
    – peskal
    Commented Jun 21, 2011 at 0:38
  • Did you tried to use Brasenham line distance how heuristic ? Commented Jul 28, 2014 at 20:12

4 Answers 4

4

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

1
  • This sounds interesting. Could you go into more detail?
    – Null Set
    Commented Apr 24, 2011 at 17:35
1

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.

0

As described in the breaking ties section of the article you linked to, maybe you could add a factor to the heuristic that is how close does this node lie on a line between its parent and the goal. That way it would prefer staying on a straight line path when possible.

0

Can you use a collision detection with the Bresenham algorithm, perhaps an adaptive Bresenham, for example with a space-filling-curve?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.