Sign in to follow this  

ironing out crinkles in an A*

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

[img]http://img85.imageshack.us/img85/7729/crinkcle.png[/img]

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
[left][url="http://www.filefactory.com/file/2cediqtrsepx/n/astarhelp_zip"]http://www.filefacto...n/astarhelp_zip[/url][/left]

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


[url="http://www.filefactory.com/file/256b56xyajyv/n/testb_zip"]http://www.filefacto...jyv/n/testb_zip[/url]
[url="http://www.filefactory.com/file/6kcbde0f4407/n/testa_zip"]http://www.filefacto...407/n/testa_zip[/url]

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

edit:
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
[img]http://img26.imageshack.us/img26/3305/smoothq.png[/img]

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 [url="http://harablog.wordpress.com/2011/09/07/jump-point-search/"]A* Jump Point Search[/url] 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 [url="http://sscce.org/"]short, self contained, correct example[/url] (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

This topic is 2044 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.

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