• 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.

4 replies to this topic

### #1falconmick  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:
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

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

### #2Antheus  Members   -  Reputation: 2409

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.

### #3ApochPiQ  Moderators   -  Reputation: 19913

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 :-)
Wielder of the Sacred Wands

### #4frob  Moderators   -  Reputation: 38046

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 book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I occasionally write about assorted stuff.

### #5ApochPiQ  Moderators   -  Reputation: 19913

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.
Wielder of the Sacred Wands

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