Hi!
I will need to implement a better AI for TUER in some months and I would like to find an API that would provide some path finding features. I found dANN, CritterAI and this rudimentary implementation of Dijkstra Moore:
http://renaud.waldura.com/doc/java/dijkstra/
I don’t plan to handle more than 20 enemies at the same time. CritterAI works well on multi-core microprocessors but I need something that do not rely on multi-threading. Do you have a suggestion?
Why not just roll your own A*?
I don’t want to rely on heuristics, that is why I prefer Dijkstra-Moore. If the APIs that I found are too much complicated, I will use only the simple implementation of this algorithm.
Heuristics!? Just use manathan. Simple. Good enough.
A* with the proper properties on the distance heuristic is optimal in the sense that its worse case equivalent to Dijkstra-Moore. In that it will visit less nodes on average and will always find the optimal path if it exists. Any A* can be turned into a Dijkstra method by setting the distance heuristic to always return the upper bound.
What is Manathan??
Actually, I studied Dijkstra-Moore at the university, I feel more comfortable with it. As I understand this algorithm, I can debug easily a Java implementation of it.
Manhattan (noun):
I use A* for Revenge of the Titans with this heuristic, which has won a lot of praise from players talking about the “brilliant AI” of the gidrahs (haha, it is of course completely emergent behaviour):
public int getCost(int from, int to) {
if (from == to) {
return 0;
}
// Bias gidrahs away from turrets
int sx = getX(from);
int sy = getY(from);
int tx = getX(to);
int ty = getY(to);
GidrahFeature gidrahFeature = movement.getGidrah().getFeature();
boolean wraith = gidrahFeature.isWraith();
boolean angry = gidrahFeature.isAngry();
WormGameState gameState = Worm.getGameState();
GameMap map = gameState.getMap();
float bias = (wraith || !gameState.isLevelActive() ? 0.0f : (map.getDanger(tx, ty) - gidrahFeature.getArmour() * 2)) * gidrahFeature.getBrain().getAvoidanceFactor() * (angry ? 0.5f : 1.0f);
int cost = wraith ? NORMAL_COST : map.getCost(tx, ty);
int steps = Math.abs(tx - sx) + Math.abs(ty - sy);
if (diagonal) {
if (steps == 2) {
// Diagonal
return FPMath.fpValue(bias) + cost;
} else {
assert steps == 1;
return (((int) (cost * 1.4142135623730950488016887242097f)) + FPMath.fpValue(1.4142135623730950488016887242097f * bias) * 5);
}
} else {
if (steps == 1) {
return FPMath.fpValue(bias) + cost;
} else {
assert steps == 2;
// Diagonal
return ((int) (cost * 1.4142135623730950488016887242097f)) + FPMath.fpValue(1.4142135623730950488016887242097f * bias);
}
}
}
Cas 
Forgive me if I’m wrong, but isn’t A* just a refining of the Dijksra algorithm? As far as I understood A* at its worst case (with a horrible heuristic) will be the same speed as Dijksra.
This wouldn’t work if the upper bound is infinity though - it would end up as a breadth-first search. As defined, Dijkstra is A* with zero heuristic, but in practice using any (non-infinite) constant should give the same result.
For Tuer, since there isn’t grid-based movement, Euclidean distance is preferable to Manhattan. Manhattan distance won’t guarantee the shortest path since it isn’t admissible (it can over-estimate the distance to the goal). Also, if you are searching for line-of-sight where your weapon has range r, then the heuristic needs to be max(0,distance-r). Obviously if r is large, then you are back at Dijkstra’s (since any direction would be as good as any other when looking for a place to shoot from).
One last thought. If you are going Dijkstra route and you don’t have variable terrain costs, then this is just breadth-first search. Then you can ditch the priority queue for a regular queue and get a significant speed-up.
Ok Jono, I plan to use BFS. However, I’m planning to test the first outdoor environment in some weeks…
http://www.jgrapht.org/ for DFS, BFS etc. Also has a Fibonacci heap implementation if you want to build a fast A*.
Thanks
Any chance to avoid the allocation in FibonacciHeap#consolidate?
There was a post here advertising a java API for 3D pathfinding a while back:
I know that API but it is neither free of charge nor open source. For free you can use only its very limited version:
http://www.jkilavuz.com/pricing.html
[quote]Any chance to avoid the allocation in FibonacciHeap#consolidate?
[/quote]
consolidate is protected and not recursive (I think). So maybe you could subclass it and use a dynamically resized cached array instead of allocating a new one every time. I would have thought the main allocation blues would be the creation and destruction of FibbonacciHeapNodes though whenever things are put in or pulled out. Again, I am sure there is a cached way out, but its not a use case the creators of that package probably deal with. The maintainers of that library are pretty open with source contributions, I have submitted stuff for it without much hassle.
Tom
Here’s a CPP pathfinding OSS project:
http://code.google.com/p/recastnavigation/
consolidate is protected and not recursive (I think). So maybe you could subclass it and use a dynamically resized cached array instead of allocating a new one every time. I would have thought the main allocation blues would be the creation and destruction of FibbonacciHeapNodes though whenever things are put in or pulled out. Again, I am sure there is a cached way out, but its not a use case the creators of that package probably deal with. The maintainers of that library are pretty open with source contributions, I have submitted stuff for it without much hassle.
[/quote]
For the nodes, I can pool them externally. I might play with using the FibonacciHeap in place of a binary heap for A*. To hijack slightly, does anyone care to explain any differences I might see between the two?
It should be quicker, it sorts lazily. You will only notice the difference if your searches created big heaps. It does not make an intractable search tractable, it just lops off one level of node expansions worth. Searches are generally exponential in nature. Using a lazy heap like FH is like the difference between one city in a travelling salesman problem i.e. it can be a significant difference, but it does not fundamentally change the complexity.
Interesting, I went exploring about Fibonacci heaps and found a stackoverflow thread.
One of the commenters said that BinaryHeap is faster for small heap sizes. Also, the binary heap makes no garbage whereas the impementation of FibonacciHeap in JGraphT makes a Node object for every item which isn’t so good.
There’s a link to a C version of the fibonacci heap in that thread here:
http://svn.boost.org/svn/boost/trunk/boost/pending/fibonacci_heap.hpp