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.
WOW, I have REALLY optimized A*
First you delete the post now an AP comes for support...
Right.
This thread has lost any interest to me anyway.
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 PosterIf 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.
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 AgonyQuote:Original post by Anonymous PosterIf 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.
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.
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement