Help with A* - ugly paths.
Author
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?
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.
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.
Author
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:
And I would like it to look more like this:
- 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 xxAnd I would like it to look more like this:
xxxx xxx xxx xxx xxxxxx
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.
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.
Author
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...
Author
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?
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
