Not to take anything away from the work but I think the title is misleading. A* is an optimal algorithm for graph search so you cannot make it 100x faster. What this does is make path finding faster by changing the structure of the graph.
That being said there's an important gotcha, those techniques require a significant amount of precomputations (especially the bounding box one) so it might not be practical if you have very dynamic maps.
One option would be to look for strategies that "look intelligent", instead of being perfectly optimal paths at every simulation frame.
Run slow pathfinding for an enemy and store the path. Have them follow the path until they hit a player-created obstacle, and only then re-run pathfinding. Besides being faster, this could let the players use the enemy behaviour to their advantage by creating traps or such.
(Anyone who knows better, I'd be delighted to find out I'm wrong—for the sake of my own search runtimes.)
They may not solve all your problems or even any of them (hard to tell knowing nothing about your game, after all), but I was absolutely dumbfounded when I played around with them at how cheaply you can get some rather complex (seeming) behaviors (e.g. put the player and some enemies in a maze, give the players a scent that strongly attracts the enemies, but also give them a slight scent that makes them repulse each other, and they'll automagically split up and surround the player).
At the very least, if you're stuck with what you're doing at the moment, play around with those, and maybe you can at least find a use for them that frees up some processing resources for precise path finding where nothing short of it will do.
[0] Potential fields can't tell you a route is a dead end until you reach the dead end. Then they only tell you you're at a dead end, but don't tell you how to get out and find a viable route. Add-on exit-a-dead-end algorithms I've seen have very inefficient movement.
Algorithms to avoid the dead end in the first place have to look ahead so far that you might as well use Dijkstra/A*.
----
Some papers I've turned up:
Potential fields:
- http://www.gamedev.net/page/resources/_/technical/artificial...
- http://www.heikohoffmann.de/htmlthesis/node56.html
- http://www.researchgate.net/publication/222662144_Solving_th...
- https://randomaccessmaths.wordpress.com/2013/10/27/potential...
Harmonic Potential Functions (related to potential fields, they attempt to solve the local minima/maxima problem)
- http://repository.cmu.edu/cgi/viewcontent.cgi?article=1625&c...
- http://www.itst2007.eurecom.fr/site/var/html/h1053/file1221....
- http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=429591...
- http://ncsu.summon.serialssolutions.com/search?s.cmd=addFace...
I think the main power is that potential fields reduce the complexity of the calculation to the map and the number of goals, with an infinite number of agents being able to use that at little cost, but you pretty much always have to build additional pathfinding on top of it. For example, for some games it might be fine for agents to follow the potential field generally, but every tick one of them gets to use Dijkstra/A*, and if that points the other way it follows that path until coming close to another agent or something. Too much efficiency can be off-putting, but also be too predictable and easy to exploit as a player, that's also worth noting. But of course, I'm kind of rationalizing my lack of deeper knowledge here, I'd love to be able to do it perfectly, and then tone that down for realism/gameplay. Alas :)
All shortest paths are either a straight line, or consist of the straight line from the original location to an outside corner, a series of straight lines between outside corners, and a straight line from an outside corner to the destination. (An outside corner is any 2x2 square with three walkable and one wall tile.)
You can easily find all the outside corners. You can find which pairs of outside corners can be walked between using N^2 ray casts. Once you've done that, you can detect when an outside corner has been removed and drop it from the map, or detect when one has been created and perform N ray casts to add it to your pathing list.
Running A* on the resulting structure is really fast, because it's smaller and more connected than a tile list. The slowest remaining part is finding the corners immediately reachable from your start/end points, which I think could also be sped up but I'd benchmark it before worrying about that.
I would say that you have the causation reversed: we just don't bother doing large matrix multiplications, because they're so expensive (and yet still don't usually cross the intercepts into making the "better" algorithms worth it, due to those algorithms having ridiculous constant coefficients.)
I would love to run Floyd-Warshall on my 40-million point network graph—but it just ain't gonna happen.
Sure, I agree. I'm not a specialist in numerical lin.alg., but I've heard it said that if you're spending a lot of time on large dense matrix multiplications, you're probably approaching the problem in the wrong way.
Jon Bentley had an article on two string reversal algorithms with the same algorithmic complexity. On a very large string, one would finish almost immediately; the other was pessimal for paged virtual memory and wouldn't finish for hours.