Advertisement

ironing out crinkles in an A*

Started by May 13, 2012 03:41 PM
4 comments, last by MichaelCrook 12 years, 6 months ago
I recently made my own A* algorythm.. It works great with an exception that there are some weird mini paths on big grids...

% = wall

crinkcle.png

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

http://www.filefacto...n/astarhelp_zip



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




http://www.filefacto...jyv/n/testb_zip
http://www.filefacto...407/n/testa_zip

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?
smoothq.png

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.
Advertisement
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
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.
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).
[size=2][ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]
I'm assuming the glitch is in the cost assignment, ill look through it later

This topic is closed to new replies.

Advertisement