he didn't say that WR, I think he said it took an average of 6 seconds to find a path in a graph of 1,000,000 nodes.

First you delete the post now an AP comes for support...

Right.

This thread has lost any interest to me anyway.

Quote: Original post by Zefrieg
Actually, I had that on debug, and had some things running in the background. Also, my cost function includes the sqrt() function and two multiplies, and the start to goal nodes are usually are far apart. Here are some tests on different numbers of nodes

10,000 nodes = 20 ms
100,000 nodes = 100 ms
1,000,000 nodes = 2342 ms

Seems like it grows in time complexity by O(n). There is only one O(log n) function in the main loop, and both a O(log n) and O(1) functions in the inner loop.

Old game programming trick :

If you are comparing distances, you can compare the squared value just as well -- you dont need to do the SquareRoot function and you can simply compare the dX*xX+dY*dY to calculate which distance is shorter.

Quote: Original post by Anonymous Poster
Old game programming trick :

If you are comparing distances, you can compare the squared value just as well -- you dont need to do the SquareRoot function and you can simply compare the dX*xX+dY*dY to calculate which distance is shorter.

If I'm reading this section of this article correctly (I'm not very experienced with A*, but I understand the concepts pretty well), you certainly would not want to do this. I suppose most of the people in this thread already realize this, but in case someone else happens along, this may help avoid an hour or more of frustration.

Quote: Original post by Agony

Quote: Original post by Anonymous Poster
Old game programming trick :

If you are comparing distances, you can compare the squared value just as well -- you dont need to do the SquareRoot function and you can simply compare the dX*xX+dY*dY to calculate which distance is shorter.

If I'm reading this section of this article correctly (I'm not very experienced with A*, but I understand the concepts pretty well), you certainly would not want to do this. I suppose most of the people in this thread already realize this, but in case someone else happens along, this may help avoid an hour or more of frustration.

Right, you can't just square H because then it gets much larger than G.
The formula is F = G + H, where H=sqrt(h), so you have F = G + sqrt(h)
to get rid of the square root, you have to square both sides getting
F^2 = (G + sqrt(h))^2 = G^2 + h + (2 * G * sqrt(h))
You might be able to get away with using F^2 = G^2 + h, but I'm not sure how significant the last term is. Maybe you could use a very crude approximation of sqrt(h) to get a reasonably accurate F^2 and compare them instead of F (I think the crude approximation would effect F more than F^2 but I'm just guessing blindly).