Question on path generated from AStar
Author
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
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
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
Author
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]
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]
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..
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..
Author
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
Author
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
Author
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
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]
Hope that helps.
[Edited by - diablos_blade on March 7, 2010 2:14:09 AM]
Author
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
