-----------------------------------

mirhagk

Mon Apr 25, 2011 7:17 pm


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

http://img683.imageshack.us/img683/5073/proofoffailure.png

Uploaded with [URL=http://imageshack.us]ImageShack.us

It gets a correct solution, but not the best, are one of my assumptions incorrect?


-----------------------------------

Tony

Mon Apr 25, 2011 7:39 pm


RE:A* Help

-----------------------------------

http://en.wikipedia.org/wiki/A*_search_algorithm

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


-----------------------------------

mirhagk

Mon Apr 25, 2011 7:44 pm


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)


-----------------------------------

Tony

Mon Apr 25, 2011 7:48 pm


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.


-----------------------------------

mirhagk

Mon Apr 25, 2011 7:53 pm


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.


-----------------------------------

mirhagk

Mon Apr 25, 2011 8:16 pm


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.


-----------------------------------

mirhagk

Sat May 07, 2011 10:42 pm


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)