Sign in to follow this  
bobmitch

Help with A* - ugly paths.

Recommended Posts

bobmitch    144
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 don`t 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 can`t 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 this post


Link to post
Share on other sites
Koobazaur    1264
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 this post


Link to post
Share on other sites
bobmitch    144
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
x
x



And I would like it to look more like this:


xxxx
xxx
xxx
xxx
xxx
xxx

Share this post


Link to post
Share on other sites
Erik Rufelt    5901
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 this post


Link to post
Share on other sites
bobmitch    144
Quote:
Original post by Erik Rufelt
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.


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 this post


Link to post
Share on other sites
bobmitch    144
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 this post


Link to post
Share on other sites
CrimsonSun    336
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this