# Help with A* - ugly paths.

## Recommended Posts

I have implemented the A* algorithm as presented by Patrick Lester here. The article and code were immensely helpful in getting me started with a* - however, the paths it produces over open terrain just dont seem right to me. Instead of following a bresenham line algorithm type path to the goal, they tend heavily towards diagonals early in the path then a straight line to the goal. I use a waypointing system, and when the waypoints are far apart, this heavy use of diagonals results in a path that is just incredibly inefficient unless the waypoints happend to be either diagonally apart or straight up or across from each other. I cant seem to find the right balance of costings and heuristics to give me the kind of straight line paths I would like. Can anybody help?

##### Share on other sites
Can't you use the distance between waypoints as cost and, for the heurestic, the distance from current waypoint to your target node? If your A* is implemented correctly, this guarantees the shortest path possible. If you're not getting the shortest path, then you screwed up your code somewhere.

Also, your diagonal vs straight line may be merely a byproduct of your waypoint placement. They may be zig-zaggy in the beginning and then more straight towards your final goal. Since the search returns a list of waypoints, that's the only kind of a path it is capable of generating.

Lastly, looking into path smoothing. You can take your zigzaggy path and just smooth it out by removing waypoints from it, provided the new connection does not have any obstacles in the way.

##### Share on other sites

What are you using for the costs and heuristic?

##### Share on other sites
At the moment I am calculating a 'best' path using:

- Manhattan heuristic
- Cost per diagonal move = 14, cost per other move = 10 (to approx square root of 2).

My way points are then created using visibility culling on this path at various points.

In open terrain the path looks like this:

     xxxxxxxxxxxxxxx    x   x  x xx

And I would like it to look more like this:

               xxxx            xxx         xxx      xxx   xxxxxx

##### Share on other sites
Since the optimal path with that setup will be some number of diagonal moves, and some number of horizontal/vertical moves. The order in which they are chosen doesn't matter. The diagonal move will always make the remaining path the shortest since it removes 14 cost, instead of 10. Therefore the diagonal will always be chosen first.
You could add something to your cost, like the actual distance (not in tiles, but straight line distance) from your destination to the tile in question. To get the next tile chosen depending on which move brings you closer to the destination, not further along the cost-path.

##### Share on other sites
Quote:
 Original post by Erik RufeltSince the optimal path with that setup will be some number of diagonal moves, and some number of horizontal/vertical moves. The order in which they are chosen doesn't matter. The diagonal move will always make the remaining path the shortest since it removes 14 cost, instead of 10. Therefore the diagonal will always be chosen first.You could add something to your cost, like the actual distance (not in tiles, but straight line distance) from your destination to the tile in question. To get the next tile chosen depending on which move brings you closer to the destination, not further along the cost-path.

Ah, I see that now. So I should use a hybrid heuristic, maybe manhattan with a touch of non-sqrt euclidian distance to alter the cost...

##### Share on other sites
From Amit Patel's pathfinding website:

This uses a heuristic like this:

h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))

Assuming each diag or straight move costs the same D.

Any help out there?

Even when I try the same heuristic / cost as this, the path comes out very different. He mentions something about "tie-breaking" - by scaling the H cost - but does not make it very clear where in the algorithm this scaling should occur, but this seems to only speed up the algorithm by discarding similarly costed routes, and doesn`t seem to change the shape of the final path.

Anybody else have this problem?

##### Share on other sites
You want the path to closely as possible follow a straight line from the origin to the destination. So define a line that goes through the origin and destination tiles. Add the distance from the tile to the line to your base heuristic.

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627651
• Total Posts
2978397

• 10
• 12
• 22
• 13
• 33