AI APIs?

[gouessej]

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?

[Eli Delventhal]

Why not just roll your own A*?

[gouessej]

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.

Games published by our own members! Check 'em out!

[Gudradain]

Heuristics!? Just use manathan. Simple. Good enough.

[delt0r]

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.

[gouessej]

Heuristics!? Just use manathan. Simple. Good enough.

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.

[Markus_Persson]

What is Manathan??

Manhattan (noun):
1) An island in New York, New York
2) abs(x1-x0)+abs(y1-y0)

[princec]

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):

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37

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

[Eli Delventhal]

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.

[Jono]

Any A* can be turned into a Dijkstra method by setting the distance heuristic to always return the upper bound.

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.

Games published by our own members! Check 'em out!

[gouessej]

Ok Jono, I plan to use BFS. However, I'm planning to test the first outdoor environment in some weeks...

[t_larkworthy]

http://www.jgrapht.org/ for DFS, BFS etc. Also has a Fibonacci heap implementation if you want to build a fast A*.

[gouessej]

http://www.jgrapht.org/ for DFS, BFS etc. Also has a Fibonacci heap implementation if you want to build a fast A*.

Thanks

[Nate]

Also has a Fibonacci heap implementation if you want to build a fast A*.

Any chance to avoid the allocation in FibonacciHeap#consolidate?

[CommanderKeith]

There was a post here advertising a java API for 3D pathfinding a while back:

http://www.jkilavuz.com/

[gouessej]

There was a post here advertising a java API for 3D pathfinding a while back:

http://www.jkilavuz.com/

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

[t_larkworthy]

Any chance to avoid the allocation in FibonacciHeap#consolidate?

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

[Nate]

Here's a CPP pathfinding OSS project:
http://code.google.com/p/recastnavigation/

Any chance to avoid the allocation in FibonacciHeap#consolidate?

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.

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?

[t_larkworthy]

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.

[CommanderKeith]

Interesting, I went exploring about Fibonacci heaps and found a stackoverflow thread.
http://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently

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

[Nate]

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.

[CommanderKeith]

Lol me too. But I would love to have a blazingly fast java fibonacci heap implementation even if it only increases FPS by 1%!

[pjt33]

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.

[t_larkworthy]

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.

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.