Computer Science Canada

A* Help
Author:  mirhagk [ Mon Apr 25, 2011 7:17 pm ]
Post subject:  A* Help
I've implemented an A* algorithm, and it works pretty well, like it finds an optimal route, but I'm having trouble with finding the most optimal route.

I've done 2 little assumptions, one is that each node stores which node visited it, and the other is instead of calculating distances as the square root of x*x+y*y, I just leave the square root out, meaning every distance is that distance squared (since everything is I thought it wouldn't affect it)

I know have a problem as shown below

Posted Image, might have been reduced in size. Click Image to view fullscreen.

Uploaded with ImageShack.us

It gets a correct solution, but not the best, are one of my assumptions incorrect?
Author:  Tony [ Mon Apr 25, 2011 7:39 pm ]
Post subject:  RE:A* Help
http://en.wikipedia.org/wiki/A*_search_algorithm
Quote:

A* achieves better performance (with respect to time) by using heuristics.

A* is optimal only in some special cases; you can read about that under #properties
Author:  mirhagk [ Mon Apr 25, 2011 7:44 pm ]
Post subject:  RE:A* Help
Okay so my algorithm is probably correct? And my assumptions are fine (hopefully the 2nd is, as it saves a LOT of CPU)
Author:  Tony [ Mon Apr 25, 2011 7:48 pm ]
Post subject:  RE:A* Help
A* is fast, easy to implement, and the results are often "good enough". If those are acceptable trade-offs, then go for it.
Author:  mirhagk [ Mon Apr 25, 2011 7:53 pm ]
Post subject:  RE:A* Help
I seem to fix the problem just by removing the H(x). Yes it will be slower, since it expands every node, but for complex maps it will likely need to expand them alot of them anyways.

I'm sorry, I'm not sure, but is changing this one fact make it find the best path?

I'm switching to a weighted A*, that way it can change based on how good the path needs to be compared to how fast the algorithm needs to be.
Author:  mirhagk [ Mon Apr 25, 2011 8:16 pm ]
Post subject:  RE:A* Help
Just realized something stupid lol, if either g(x) or h(x) is reallly big, a tiny difference in that is much more difference in f(x) than a large difference in the other, if used with the squared versions I use.

It saves a lot of time, but it meant that the algorithm didn't branch out alot at the beginning, but then did alot at the end, kinda opposite to normal, I changed it, and it still gets the path that is not 100% optimal, but it looks smarter now, and can get the perfect path with a weighting factor of like 0.3, which doesn't expand too many nodes.

Yay, I'm happy now.
Author:  mirhagk [ Sat May 07, 2011 10:42 pm ]
Post subject:  RE:A* Help
Not that it really matters, but I took the square root each time I grabbed the number instead of whenever I added to it (and this changed it dramatically)

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy