gouessej


«
Posted
20100903 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 multicore microprocessors but I need something that do not rely on multithreading. Do you have a suggestion?




Eli Delventhal


«
Reply #1  Posted
20100903 14:43:55 » 

Why not just roll your own A*?




gouessej


«
Reply #2  Posted
20100903 15:27:28 » 

Why not just roll your own A*?
I don't want to rely on heuristics, that is why I prefer DijkstraMoore. 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
20100903 21:42:37 » 

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




delt0r


«
Reply #4  Posted
20100903 21:47:11 » 

A* with the proper properties on the distance heuristic is optimal in the sense that its worse case equivalent to DijkstraMoore. 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
20100903 23:03:50 » 

Heuristics!? Just use manathan. Simple. Good enough.
What is Manathan?? Actually, I studied DijkstraMoore 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
20100904 00:46:32 » 

What is Manathan??
Manhattan (noun): 1) An island in New York, New York 2) abs(x1x0)+abs(y1y0)




princec


«
Reply #7  Posted
20100904 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
20100904 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
20100904 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 breadthfirst search. As defined, Dijkstra is A* with zero heuristic, but in practice using any (noninfinite) constant should give the same result. For Tuer, since there isn't gridbased movement, Euclidean distance is preferable to Manhattan. Manhattan distance won't guarantee the shortest path since it isn't admissible (it can overestimate the distance to the goal). Also, if you are searching for lineofsight where your weapon has range r, then the heuristic needs to be max(0,distancer). 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 breadthfirst search. Then you can ditch the priority queue for a regular queue and get a significant speedup.




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


gouessej


«
Reply #10  Posted
20100904 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
20110109 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
20110109 18:28:09 » 

Thanks




Nate


«
Reply #13  Posted
20110110 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
20110110 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
20110110 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
20110111 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
20110111 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
20110111 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
20110111 09:56:58 » 

Remember that bigO isn't bigtheta. Each decreasekey is O(lg n) time in a binary heap, but I suspect that except with pathological graphs you could amortise the decreasekeys 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
20110111 11:58:55 » 

Remember that bigO isn't bigtheta. Each decreasekey is O(lg n) time in a binary heap, but I suspect that except with pathological graphs you could amortise the decreasekeys 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.



