Sign in to follow this  
jezham

Is my A* search considering too many nodes?

Recommended Posts

jezham    204
I've not really needed a search function before. Recently though, I've been reading about the navigation mesh (http://www.ai-blog.net/archives/000152.html), and I've suddenly found huge interest in path finding. To help me fully understand the concept, I've based the code on the readings in this tutorial http://www.policyalmanac.org/games/aStarTutorial.htm. Though I haven't looked at the sample code there as their nodes are spread out, and I think v1 should be as simple as possible. Well I finally got it to work, based on stopping the search when the first score-based path is found. But here's the thing, is my code considering too many nodes? In the screenshot below, the path is 16 nodes, and 61 nodes are considered...this number increases quick...but not as quickly as when I forgot to check if a node was already closed as well as checking if it was already open - lol! Does this look kinda' normal to you? (apart from the random textures of course!) Thanks for your help. =)

Share this post


Link to post
Share on other sites
alexjc    457
No, it looks normal. You could hack your heuristic to make it a little better in this case, but it might become worse generally.

Share this post


Link to post
Share on other sites
nullsquared    126
Looks fine.

It can't do any better because your heuristic will lead it straight to the wall, at which point it needs to backtrack and try alternate routes. Notice that once it escapes the small area behind the wall it doesn't explore any unnecessary nodes at all.

Share this post


Link to post
Share on other sites
ID Merlin    119
I've had good experience reducing the searched nodes by adding a tiny adjustment to the "h" function that considers the straight line distance from the ideal path to the heuristic.

Not enough to make it inadmissible, something like 0.01 * straight_line_distance. It forces the search to consider nodes closer to straight-line before nodes in the opposite direction.

Share this post


Link to post
Share on other sites
jezham    204
ID Merlin, when I write the navigation mesh version, I will probably drop the Manhattan distance completely - and use distance squared as there won't be many polygons to deal with.

Thanks Narf, I do read through related posts they tend to spark off ideas or just help me decide that I'm on the right path ;-)

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