Jump to content
  • Advertisement
Sign in to follow this  

ironing out crinkles in an A*

This topic is 2354 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

I recently made my own A* algorythm.. It works great with an exception that there are some weird mini paths on big grids...

% = wall


I'm kinda confident with my code, maybe this is a glitch in my execution.. but I don't know..
here's my code, feel free to use it if you want to, but as shown by this picture, atm it aint 100% functional


[font=sans-serif]I ran some tests, here they are:[/font]


thanks, it's really boggling me
(btw, the file numbers on the test run print outs is the Heuristic multiplier (increases likely hood to go towards goal)
testb is the more important of the two as it is a mock up of the map I am using

like maybe is there some way I could crush the number of points so that it says,
start = 1,1
next = 10, 50
next = 70, 50
end = 90, 5

edit 2:
one solution I can think of is add another propert called divide amount..
this will split the original path up into x divide amounts, it will then go from start, to end of first divide, then start of first divide to end... until it gets to secondlast divide end to last divide end.. this would work as a stronger Heuristic would automatically make the path push towards the more correct direction, say in testb, if I split into two it would head up strait away instead of down, making it so that the most optimal directions don't all verge down causing the path to have to crinkcle over spots

this good or bad idea? Edited by falconmick

Share this post

Link to post
Share on other sites

anyone looking for a solution, splitting up the A star into multiple mini astars once you are done is more efficent

this is splitting it once.

Share this post

Link to post
Share on other sites
when I have time I will show splitting it into 3, 4, 5, 6, 7 and how much it effects performance, i can also upload a visual studio solution file if it will help anyone who is still learning

Share this post

Link to post
Share on other sites
I don't have the time to check the code, but the "crinkle" is definitely a bug. You can tell that at that point the cost + the estimated cost should be greater than going the direct way. My suspicions would be:
1. Not using an admissible estimate heuristic, e.g. it somehow views that way as potentially shorter than going directly, so it gets explored first.
2. Incorrectly following the path from the goal back to the start once the search has terminated.
3. Not closing a node properly once explored, e.g assigning it a new greater cost than the initial cost that was assigned.

Share this post

Link to post
Share on other sites
If you're really worried about performance with A*, you should look into A* Jump Point Search before you go ballistic and divide the pathfinding into multiple sub-parts. But that's for later, right now you should focus on fixing your bug.

I didn't download your code, mainly because a) I don't like dealing with file hosting sites and b) if it's a whole project it probably isn't a short, self contained, correct example (which means there's a lot of stuff to wade through).

Like jefferytitan said, the "crinkle" is probably a bug. If you're using a heuristic that's greater than the actual cost, it's possible to for a non-optimal path to be found (although I think it'd have to be a pretty terrible heuristic to get a "crinkle" like that, so I'm leaning towards it being a bug; usually even the non-optimal path is pretty smooth/consistent). Try a) running the program in your debugger and perform an A* search by hand (where you're not just following your code) to see if you can find where the two deviate from each other and b) printing out more useful/readable information in your "map" (i.e. show scores, parents, etc) (you can change it to show parents one time, run it, then change it to show heuristic scores, run it, then change it to show actual scores, run it, etc to see how it's behaving) (be sure to run it in a step by step manner so you can watch it working, don't just run it and look at the final results).

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!