A* Help

[mirhagk]

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



Uploaded with ImageShack.us

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

[Tony]

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

[mirhagk]

Okay so my algorithm is probably correct? And my assumptions are fine (hopefully the 2nd is, as it saves a LOT of CPU)

[Tony]

A* is fast, easy to implement, and the results are often "good enough". If those are acceptable trade-offs, then go for it.

[mirhagk]

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]

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]

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)