Sign in to follow this  
lucky6969b

Question on path generated from AStar

Recommended Posts

Hi, I've implemented AStar recently, but I found out that it always tried to seek for the path, while it was the shortest, but always "creeping" along the wall, of course, there was heaps of room in the main lobby for example Is it what the astar supposed to be like? Thanks Jack

Share this post


Link to post
Share on other sites
it will depend on your heuristic, but if you use the general Euclidean distance heuristic, then the behavior you have is expected. The basic algorithm has no concept of space and simply tries to find the optimal path (shortest) to the goal location.

you can of course add in constraints to your neighbor function to require that there be a certain amount of space on each side of a node in order to use that node. This would take into account the unit's width and ensure there would be no collision with the wall.

it all comes down to how you define your heuristic and neighbor function.

- me

Share this post


Link to post
Share on other sites
Thanks for the reply.
Actually, why the manhattan or true distance hueristics are better than using
ordinary geometrical measurements? Could you provide any examples, screenshots or links to this? I have another question. When an object confronts with an dynamic obstacle, surely it gets to steer away from it, but my question is how do I steer the object back to the original path after it dodges the obstacle? way-off.

Jack

[Edited by - lucky6969b on March 7, 2010 4:49:03 AM]

Share this post


Link to post
Share on other sites
the most important aspect of a heuristic is that it doesnt overestimate the costs for the path. If that happens the path wont be optimal.
The more accurate the heuristics are the less nodes in the navmesh need to be evaluated. heuristics are a tradeoff between computation costs and accuracy, and it depends which is preferable.

as for dynamic obstacles, you could just plan a path from the displaced position to a position on the original path to get back on "track". But thats just a quick idea..

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
What kind of discretization are you using? (navmesh, visibility graph, regular grid, etc?)


Hi,
I am not sure i'm a pioneer or re-inventing the wheel.
I am using so called dual-map ( I call it ), with a mixture of grid and pixels
Don't know if it can be implemented correctly...
Thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by mancubit

as for dynamic obstacles, you could just plan a path from the displaced position to a position on the original path to get back on "track". But thats just a quick idea..


Hmm... hope the expense of this splice path (partial path replan) won't be too expensive. I have about 20+ mobile agents on the map... let me try ;)
Thanks
Jack

Share this post


Link to post
Share on other sites
Quote:
Original post by mancubit
the most important aspect of a heuristic is that it doesnt overestimate the costs for the path. If that happens the path wont be optimal.
The more accurate the heuristics are the less nodes in the navmesh need to be evaluated. heuristics are a tradeoff between computation costs and accuracy, and it depends which is preferable.


Do you have any good links on this topic? (about different types of heuristics) and how they are implemented.. I have google but then given up because of the messy results...

Thanks



Share this post


Link to post
Share on other sites
If your main issue is that it creeps along a wall, then maybe you should look into the string pulling or funnel algorithm. I've never looked into it properly myself so the only link I can provide you with is this one I'm afraid, but the main point of the algorithm seems to be to remove redundant points in a path. Which should, in your case, return you a path which cuts across the room instead of a path which creeps along the wall.

Hope that helps.

[Edited by - diablos_blade on March 7, 2010 2:14:09 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by diablos_blade
If your main issue is that it creeps along a wall, then maybe you should look into the string pulling or funnel algorithm. I've never looked into it properly myself so the only link I can provide you with is this one I'm afraid, but the main point of the algorithm seems to be to remove redundant points in a path. Which should, in your case, return you a path which cuts across the room instead of a path which creeps along the wall.

Hope that helps.


Hi diablos_blade,
I'd like to upload a snapshot of how good or bad my pathfinding algorithm works?
I am not sure if string pulling would be 100% suitable for my situation...
Is there a way to upload pictures at gamedev?
Thanks
Jack

Share this post


Link to post
Share on other sites
Oh I see your problem now. Technically speaking string pulling could fix your problem. But it would need the more expensive version. e.g. (assuming I've understood it correctly):


output_path
i = 0
while i is not path.length do
outputpath.add( path[i] )
furthest_visible = i
for j = i + 1 to path.length do
if can_see( path[i], path[j] ) then
furthestVisible = j
end
end
i = furthestVisible
end




But you're probably better off with a better hueristic in this case. I can't help you with that one though, I've just stuck to the basic geometric distance myself [grin].

I would also be slightly worried about the "dips" that seem to happen beteen the walls. I'd expect A* to return a straight path there, it depends on how you represent your world though (Hex tiles for example, I would expect this as a result).

Hope that helps.

Share this post


Link to post
Share on other sites
Quote:
Original post by lucky6969b
Quote:
Original post by mancubit

as for dynamic obstacles, you could just plan a path from the displaced position to a position on the original path to get back on "track". But thats just a quick idea..


Hmm... hope the expense of this splice path (partial path replan) won't be too expensive. I have about 20+ mobile agents on the map... let me try ;)
Thanks
Jack


not really - but maybe this helps you

http://theory.stanford.edu/~amitp/GameProgramming/

Share this post


Link to post
Share on other sites
Quote:
Original post by mancubit
Quote:
Original post by lucky6969b
Quote:
Original post by mancubit

as for dynamic obstacles, you could just plan a path from the displaced position to a position on the original path to get back on "track". But thats just a quick idea..


Hmm... hope the expense of this splice path (partial path replan) won't be too expensive. I have about 20+ mobile agents on the map... let me try ;)
Thanks
Jack


not really - but maybe this helps you

http://theory.stanford.edu/~amitp/GameProgramming/


Just a matter of coincidence, I was also taking a look at that page just a few mins ago...
Thanks
Jack

Share this post


Link to post
Share on other sites
Quote:
Original post by inferno82
it will depend on your heuristic, but if you use the general Euclidean distance heuristic, then the behavior you have is expected. The basic algorithm has no concept of space and simply tries to find the optimal path (shortest) to the goal location.

you can of course add in constraints to your neighbor function to require that there be a certain amount of space on each side of a node in order to use that node. This would take into account the unit's width and ensure there would be no collision with the wall.

it all comes down to how you define your heuristic and neighbor function.

- me


Hi Inferno82,
I am actually using the Manhattan Heuristic which looks like

temp->h = abs(dx-sx) + abs(dy-sy);






which results in the path I obtained in the picture I posted above(previous post).I find this is extremely fast but sometimes bumps into narrow gaps and the pathfinder decides to get in there. I am looking into ways to walk the path with certain granularity when I take object width into account, but would that be pathetically slow? The thing that really baffles/worries me is the number of objects that need to path-find and how they might get into each other's way... and have to resolve many times over... which creates a bottleneck in my system.
Any comments?
Thanks
Jack

Share this post


Link to post
Share on other sites
The way I have gone about this in the past to to modify the neighbor function to check to see if a node is indeed passable based on the units width. There are varying ways to do this, a common approach is to use the brushfire algorithm. A good article covering this can be found here.

Basically, you can preprocess the grid offline and determine the distance to the closest object for each cell. Then during your A* search you only consider cells with a distance greater than or equal to the unit's width. This ensures any path generated by A* is indeed okay for the unit to use.

You could also do this online, and for a candidate cell perform a micro search around the cell based on the unit's width and only consider the cell if there are no objects within the unit's width. Obviously, there is an added cost to doing it online.

- me

Share this post


Link to post
Share on other sites
Quote:
Original post by inferno82
The way I have gone about this in the past to to modify the neighbor function to check to see if a node is indeed passable based on the units width. There are varying ways to do this, a common approach is to use the brushfire algorithm. A good article covering this can be found here.

Basically, you can preprocess the grid offline and determine the distance to the closest object for each cell. Then during your A* search you only consider cells with a distance greater than or equal to the unit's width. This ensures any path generated by A* is indeed okay for the unit to use.

You could also do this online, and for a candidate cell perform a micro search around the cell based on the unit's width and only consider the cell if there are no objects within the unit's width. Obviously, there is an added cost to doing it online.

- me


Hi
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?
Thanks
Jack

Share this post


Link to post
Share on other sites
This is kind of unrelated, but the the way your paths tend to follow diagonals there is typically an indication that the "actual" path cost that you're using is incorrect. Remember, if you follow a straight line, add 1 to the actual cost for the path, if you follow a diagonal, add sqrt(2) to the actual cost.

Share this post


Link to post
Share on other sites
Quote:
Original post by Codeka
This is kind of unrelated, but the the way your paths tend to follow diagonals there is typically an indication that the "actual" path cost that you're using is incorrect. Remember, if you follow a straight line, add 1 to the actual cost for the path, if you follow a diagonal, add sqrt(2) to the actual cost.


:) Yeah.... something wrong in the cost function... I made a stub for it and forgot to fill it back later on. So all directions cost only 1.., rather than 1.414
:)
Jack

Share this post


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

Share this post


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



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