How fast should A* run?

Game Mechanics Artificial Intelligence
#1

I’m wondering, I have a grid of 50x50… and A* takes about 1.4 ms going from bottom left to top right, and there are no obstacles.
My implementation is using diagonal heuristics and PriorityQueue for both open and closed lists, although using a LinkedList for closed set doesn’t matter much.

I have tried AIJ (https://aij.dev.java.net/) … and it runs 0.8 ms (same setup, 50x50 grid and going from bottom-left to top-right). Although the first few attempts run anywhere between 1-8 ms, but after those it constantly runs at under 0.8 ms.

Clearly, mine is taking nearly twice as long, just wondering what could be the problem :slight_smile:

(Of course this is also relative to the computer being run on.)

Any general ideas? If anyone that knows A* in and out is interested in checking out my code, please let me know… I’ll PM you a link.

#2

i remember that ve used min heap for implementation…tho it was long time ago…must do a refresher course :slight_smile:

#3

What does does your graph/map look like? If there are lots of walls and obstacles, then using the current heuristic may not be the best choice and using something like a cluster heuristic would better suit that. What does your fill pattern look like currently?

Alternatively, you could look at a different data structure, but if switching to a linked list has no effect, then switching to something better will also have little effect since that doesn’t appear to be the bottleneck. I would say though that priority queue isn’t optimal. You might want to try a heap as the poster above suggests or a bucketed priority queue instead.

#4

I’ve read amits a* page, it has nice info on heuristics for A*. Are there any other sources, different types of heuristics that I should explore?

I’m googling for the “cluster heuristic” now…don’t seem to find any source explaining it.

#5

You are still getting that time? Your demo is many times faster, if you remember to warm it up a few times first.

#6

Yes, I managed to speed it up a lot :slight_smile: I’m happy with the speed now.

I’m wondering about heuristics, I currently have 5 heuristics:

  • Manhattan
  • Euclidean
  • Diagonal
  • Diagonal with tie-breaker
  • Diagonal with tie-breaker cross-product

But I’m interested in other heuristics, but they are hard to find.

#7

i read somwhere about a mipmaped one, where the mipmaps are based upon the passibilty of the more refined level.

#8

I guess heuristics are largely dependent on what kind of search space you have. I can imagine that some heuristics fit squarebased searchspaces more, while others fit for example hexagonal searchspaces more.

#9

There are some articles about A* optimisation in Game Programming Gems or AI Programming Books.

Some use tricky sorting algorithms to the open or closed list to optimize. I dont have the details in mind.

-JAW