Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

Question on path generated from AStar

This topic is 3196 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!