Jump to content

  • Log In with Google      Sign In   
  • Create Account


ironing out crinkles in an A*


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 falconmick   Members   -  Reputation: 80

Like
0Likes
Like

Posted 13 May 2012 - 09:41 AM

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

% = wall

Posted Image

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


I ran some tests, here they are:



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?

Edited by falconmick, 13 May 2012 - 09:52 AM.


Sponsor:

#2 falconmick   Members   -  Reputation: 80

Like
0Likes
Like

Posted 13 May 2012 - 04:14 PM

Posted Image

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.

#3 falconmick   Members   -  Reputation: 80

Like
0Likes
Like

Posted 13 May 2012 - 04:20 PM

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

#4 jefferytitan   Members   -  Reputation: 1688

Like
0Likes
Like

Posted 13 May 2012 - 05:12 PM

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.

#5 Cornstalks   Crossbones+   -  Reputation: 6966

Like
0Likes
Like

Posted 13 May 2012 - 08:16 PM

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).
[ 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 ]

#6 falconmick   Members   -  Reputation: 80

Like
0Likes
Like

Posted 14 May 2012 - 12:32 AM

I'm assuming the glitch is in the cost assignment, ill look through it later




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS