Question on path generated from AStar
If you add a small adjustment to the heuristic that adds the straight-line distance from the ideal path, your results will e better in most cases.
Quote:
Original post by lucky6969b
I am wondering if this is the well-known method that expands the obstacles outwards with a few units, so that the pathfinder can take the width of the agent into account?
It works in a similar fashion, but doesn't expand the obstacles outward. The brushfire algorithm works by examining every free node (no obstacle) and determines the distance to the closest obstacle. The node then stores this clearance value. Then when doing your A* search, you first consult the clearance value and determine if you unit can use the node.
The advantage of doing it this way, is that you only have to find the clearance values one time regardless of the unit width. So if you have two units, one with a width of 2 and another with a width of 4, they both can use the same clearance values.
By expanding the obstacles outwards as you mentioned would require a different expansion for each size unit you have. Using the same example as above, you would have to create a map for the unit of width 2 (expanding outwards by 2 units) and a second map for the unit of width 4 (expanding outwards by 4 units).
- me
Quote:Original post by lucky6969bQuote:Original post by diablos_blade
Not that I know of, but Imageshack will be willing to help [grin].
here it comes,
Link
Thanks
Jack
The pattern where it prefers to do the diagonals and lead to a non-optimal path
is one of the things that makes Astar by itself no usually good enough.
In you picture you see that big dodge at the start in that large open area and another is the small one 3/4 of the way thru where it dodges only a little diagonally but then has to dodge back diagonally in a fairly small area.
An optimal path would have more direct paths (like alternating diagonals and straights to get a better bee-line path when it can.
The problem is that the Open set does not get new nodes outside of the immediate neighbors to each cell and since the path is unobstructed it goes sailing on towards the target using the local 'best' node and never gets to reevaluate better options behind it.
Maybe a periodic attempt to populate the Open list using a Bresenham line algorithm to quickly traverse open areas (which WOULD make a bee-line path
towards the target AND could computationally be cheaper).
I would need to think if that would disrupt the Astar's mechanism -- you probably would populate with the adjacents to the actual line and then it would be pretty much what Astar would do thru open space EXCEPT that the line would be truer.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
