Jump to content

  • Log In with Google      Sign In   
  • Create Account

How fast should my A Star run?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 falconmick   Members   -  Reputation: 80

Like
0Likes
Like

Posted 21 May 2012 - 10:34 AM

Currently my A star can run 500 tests every second on this map:
is this good or bad?
if I lower the Heuristic weighing it takes about 1.5 -> 2 seconds, although due to the simplicity of the map I am making for my game I can afford a high Heuristic
Posted Image

Edited by falconmick, 21 May 2012 - 10:36 AM.


Sponsor:

#2 Antheus   Members   -  Reputation: 2397

Like
0Likes
Like

Posted 21 May 2012 - 03:13 PM

3 GHz CPU = 3e9 cycles
N = number of tiles = 100 x 100 = 10,000

So 3e9 / 10,000 / 500 = 600 cycles per tile.

Assuming one needs to search entire map, reduce N if not. Same for CPU frequency.

One could get as low as 1 cycle per tile, so above solution would be 600 times slower than theoretically possible. Or, it might be possible to run 300,000 tests per second.

#3 ApochPiQ   Moderators   -  Reputation: 15816

Like
0Likes
Like

Posted 22 May 2012 - 10:51 AM

It's not too bad, really; you could probably improve on it, but doing a full search of 10k nodes is going to be slow no matter what. I wouldn't worry about it.

The real question is: how many times per second do you need to do an A* search in the first place? If the answer is less than 500, you're done :-)

#4 frob   Moderators   -  Reputation: 21471

Like
0Likes
Like

Posted 22 May 2012 - 01:22 PM

It seems slow to me, since in A* you are not checking the full 10k nodes. You should only be checking those adjacent to the current best search. In the case of your map example above you should only be doing about 200 node heuristics checks to find the path.

You mention that you have a 'high heuristic' function. How slow? What does your profiler tell you about the function?

Remember that the whole point of A* using a heuristic function is that you don't need to perform the full check. If you need to implement the full test you may as well just replace A* with Dijkstra's algorithm. Usually it is just the simple check for the cost of that single hop and the Cartesian distance from that point to the goal. It should be an extremely fast test.
Check out my personal indie blog at bryanwagstaff.com.

#5 ApochPiQ   Moderators   -  Reputation: 15816

Like
0Likes
Like

Posted 22 May 2012 - 01:26 PM

Derp, I didn't look too closely at the image. I was assuming it was all just an open field, in which case A* with a bad heuristic would expand rather rapidly.

Yeah, there's definitely room for improvement I think.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS