# 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.

## 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 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 on other sites
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 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 on other sites
What kind of discretization are you using? (navmesh, visibility graph, regular grid, etc?)

##### Share on other sites
Quote:
 Original post by EmergentWhat 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 on other sites
Quote:
 Original post by mancubitas 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 on other sites
Quote:
 Original post by mancubitthe 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 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 on other sites
Quote:
 Original post by diablos_bladeIf 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.

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

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633701
• Total Posts
3013446
×