4 replies to this topic

[falconmick]

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

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

[Antheus]

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.

[ApochPiQ]

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 :-)

[frob]

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.

[ApochPiQ]

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.