Very interesting post, thanks! That’s good too, now I don’t have an excuse to rip out my binary heap and maybe I’ll make some progress on the actual gameplay. 
Lol me too. But I would love to have a blazingly fast java fibonacci heap implementation even if it only increases FPS by 1%!
Remember that big-O isn’t big-theta. Each decrease-key is O(lg n) time in a binary heap, but I suspect that except with pathological graphs you could amortise the decrease-keys for a given node and get better than that.
Besides, for many applications in game AI each node has degree bounded by a constant, so E = O(V) and O(E lg V) (Dijkstra with binary heap) is no worse than O(V lg V) (Dijkstra with Fibonacci heap) and you’re better off using the one with the smaller hidden constant.
[quote]Remember that big-O isn’t big-theta. Each decrease-key is O(lg n) time in a binary heap, but I suspect that except with pathological graphs you could amortise the decrease-keys for a given node and get better than that.
Besides, for many applications in game AI each node has degree bounded by a constant, so E = O(V) and O(E lg V) (Dijkstra with binary heap) is no worse than O(V lg V) (Dijkstra with Fibonacci heap) and you’re better off using the one with the smaller hidden constant.
[/quote]
It does not matter if the branching is constant or not. At the end of the day if you have taken out 1000 node from the queue and you have 10000 nodes still in the queue, with a binary heap you had to sort all 1000 + 10000, and with a fibbonacci you only sorted the first 1000 took out the list.
FibbonacciHeap does have a slight overhead compared to a good BanaryHeap implementation, so for tiny searches its better. This is the same argument of why bubblesort is better than XYZ sort for small lists. If you need A* (i.e. a guide heuristic), then your searches are probably big enough to feel the gain of a FibonacciHeap. There is a good paper that suggests in practical instantiations a pairing heap is better than a FibbonacciHeap (lower overhead but still lazy), but I can’t find an implementation of that type of heap.