In fine-tuning my Pathery application, I found the need for a faster priority queue. Since this could be useful to others (pathfinding is often a bottleneck for video games), I finally got around to publishing it.
You can find it here; or read the documentation here. Enjoy!
Note: If you found this page hoping to optimize your pathfinder, you may want to check out this post first, which has a few tips on optimizing pathfinders for games.
4 Comments
FYI: I have been building a pathfinder for my HexgridUtilities library, and recently added an ALT (A* with Landmark Triangulation) implementation. This resulted in an 80-fold (yes, eighty!) speed increase, to the point where my most complex test case can no longer be profiled – it completes too quickly. All for 4 seconds at start-up of pre-processing 8 landmarks in parallel. This implementation also includes a HOT-Queue PriorityQueue implementation; BitBucket is done for maintenance just now, so I cannot compare it to your implementation yet. Any comments or suggestions would be welcome.
Hey Pieter – thanks for the response!
ALT is one of many techniques that can be used to speed up A* pathfinding. Some (like ALT) require expensive pre-processing, others require none. They are not all mutually-exclusive, so some can be used together. None of them provide speedups in all cases, but they’re all general enough to work in a wide variety of cases. A very succinct overview of them can be found here (under “Existing Methods For Speeding Up Search”): http://harablog.wordpress.com/2011/08/26/fast-pathfinding-via-symmetry-breaking/
However, the bottleneck for all (most?) of these techniques will still be the priority queue, so having a fast priority queue is still important.
Bitbucket is up now, so you should be able to compare our implementations. I had not heard of Heap-On-Top Priority Queues before, but I am reading the paper now and, if I feel like it could provide a speed-up, will implement it. It may be like fibbonacci heaps, though, in that it has better asymptotic speed, but in practical applications is actually much slower. We shall see 🙂
I saw about 5-10% time reduction using the HOT-queue implementation, which is less tan the 30-50% I anticipated; I may have an inefficiency somewhere in the code.
The preprocessing of my 760×420 map for 8 landmarks takes < 4 seconds, running in parallel on an i7 with 4 hyper-threaded cores. (Using a Dijkstra's of course.) The 80-fold time reduction was amazing. The worst-case path on that map now has a closed set of about 1650 hexagons for a path with about 1250-1300 hexes. I could probably make do with just the 4 corners as landmarks, but the adding the side-midpoints seemed cheap insurance.
Do you have an A* implementation in C# that can use this priority queue? I need A* for a tank game I am working , th elevels are simple, 100×100 units flat 2d surface with walls and obstacles. I have tried steering behaviors but the tanks get stuck at places , especially at the edge of the walls. I want to give A* a try.. any help is appreciated!