gouessej
|
 |
«
Posted
2010-09-03 14:20:36 » |
|
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
|
 |
«
Reply #1 - Posted
2010-09-03 14:43:55 » |
|
Why not just roll your own A*?
|
|
|
|
gouessej
|
 |
«
Reply #2 - Posted
2010-09-03 15:27:28 » |
|
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
|
 |
«
Reply #3 - Posted
2010-09-03 21:42:37 » |
|
Heuristics!? Just use manathan. Simple. Good enough.
|
|
|
|
delt0r
|
 |
«
Reply #4 - Posted
2010-09-03 21:47:11 » |
|
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.
|
I have no special talents. I am only passionately curious.--Albert Einstein
|
|
|
gouessej
|
 |
«
Reply #5 - Posted
2010-09-03 23:03:50 » |
|
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
|
 |
«
Reply #6 - Posted
2010-09-04 00:46:32 » |
|
What is Manathan??
Manhattan (noun): 1) An island in New York, New York 2) abs(x1-x0)+abs(y1-y0)
|
|
|
|
princec
|
 |
«
Reply #7 - Posted
2010-09-04 01:26:55 » |
|
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; }
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) { 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; return ((int) (cost * 1.4142135623730950488016887242097f)) + FPMath.fpValue(1.4142135623730950488016887242097f * bias); } } } |
Cas 
|
|
|
|
Eli Delventhal
|
 |
«
Reply #8 - Posted
2010-09-04 02:22:03 » |
|
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
|
 |
«
Reply #9 - Posted
2010-09-04 07:05:34 » |
|
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
|
 |
«
Reply #10 - Posted
2010-09-04 09:43:58 » |
|
Ok Jono, I plan to use BFS. However, I'm planning to test the first outdoor environment in some weeks...
|
|
|
|
t_larkworthy
|
 |
«
Reply #11 - Posted
2011-01-09 12:55:22 » |
|
http://www.jgrapht.org/ for DFS, BFS etc. Also has a Fibonacci heap implementation if you want to build a fast A*.
|
Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
|
|
|
gouessej
|
 |
«
Reply #12 - Posted
2011-01-09 18:28:09 » |
|
Thanks 
|
|
|
|
Nate
|
 |
«
Reply #13 - Posted
2011-01-10 02:30:04 » |
|
Also has a Fibonacci heap implementation if you want to build a fast A*.
Any chance to avoid the allocation in FibonacciHeap#consolidate?
|
|
|
|
|
|
t_larkworthy
|
 |
«
Reply #16 - Posted
2011-01-10 12:03:01 » |
|
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
|
Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
|
|
|
Nate
|
 |
«
Reply #17 - Posted
2011-01-10 20:31:07 » |
|
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
|
 |
«
Reply #18 - Posted
2011-01-11 01:50:23 » |
|
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.
|
Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
|
|
|
|
Nate
|
 |
«
Reply #20 - Posted
2011-01-11 08:07:42 » |
|
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
|
 |
«
Reply #21 - Posted
2011-01-11 08:24:23 » |
|
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
|
 |
«
Reply #22 - Posted
2011-01-11 09:56:58 » |
|
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
|
 |
«
Reply #23 - Posted
2011-01-11 11:58:55 » |
|
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.
|
Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
|
|
|
|