Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (581)
games submitted by our members
Games in WIP (500)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  AI APIs?  (Read 7914 times)
0 Members and 1 Guest are viewing this topic.
Offline gouessej

« In padded room »



TUER


« Posted 2010-09-03 16: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?

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 12


Game Engineer


« Reply #1 - Posted 2010-09-03 16:43:55 »

Why not just roll your own A*?

See my work:
OTC Software
Offline gouessej

« In padded room »



TUER


« Reply #2 - Posted 2010-09-03 17: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!
Legends of Yore - The Casual Retro Roguelike
Offline Gudradain
« Reply #3 - Posted 2010-09-03 23:42:37 »

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

JGO Coder


Medals: 22


Computers can do that?


« Reply #4 - Posted 2010-09-03 23: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
Offline gouessej

« In padded room »



TUER


« Reply #5 - Posted 2010-09-04 01: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.

Offline Markus_Persson

JGO Wizard


Medals: 12
Projects: 19


Mojang Specifications


« Reply #6 - Posted 2010-09-04 02:46:32 »

What is Manathan??

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

Play Minecraft!
Offline princec

JGO Kernel


Medals: 284
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #7 - Posted 2010-09-04 03: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;
      }

      // 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 Smiley

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 12


Game Engineer


« Reply #8 - Posted 2010-09-04 04: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.

See my work:
OTC Software
Offline Jono
« Reply #9 - Posted 2010-09-04 09: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!
Legends of Yore - The Casual Retro Roguelike
Offline gouessej

« In padded room »



TUER


« Reply #10 - Posted 2010-09-04 11:43:58 »

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

Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #11 - Posted 2011-01-09 13: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.
Offline gouessej

« In padded room »



TUER


« Reply #12 - Posted 2011-01-09 19:28:09 »

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

Offline Nate

JGO Kernel


Medals: 129
Projects: 3
Exp: 14 years


Esoteric Software


« Reply #13 - Posted 2011-01-10 03: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?

Offline CommanderKeith
« Reply #14 - Posted 2011-01-10 04:53:11 »

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

http://www.jkilavuz.com/

Offline gouessej

« In padded room »



TUER


« Reply #15 - Posted 2011-01-10 11:46:01 »

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

Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #16 - Posted 2011-01-10 13:03:01 »

Quote
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.
Offline Nate

JGO Kernel


Medals: 129
Projects: 3
Exp: 14 years


Esoteric Software


« Reply #17 - Posted 2011-01-10 21:31:07 »

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

Quote
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?

Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #18 - Posted 2011-01-11 02: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.
Offline CommanderKeith
« Reply #19 - Posted 2011-01-11 07:56:25 »

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

Offline Nate

JGO Kernel


Medals: 129
Projects: 3
Exp: 14 years


Esoteric Software


« Reply #20 - Posted 2011-01-11 09: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. Smiley

Offline CommanderKeith
« Reply #21 - Posted 2011-01-11 09: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%!

Offline pjt33
« Reply #22 - Posted 2011-01-11 10: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.
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #23 - Posted 2011-01-11 12:58:55 »

Quote
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.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (56 views)
2014-04-15 18:08:23

BurntPizza (54 views)
2014-04-15 03:46:01

UprightPath (67 views)
2014-04-14 17:39:50

UprightPath (50 views)
2014-04-14 17:35:47

Porlus (67 views)
2014-04-14 15:48:38

tom_mai78101 (91 views)
2014-04-10 04:04:31

BurntPizza (152 views)
2014-04-08 23:06:04

tom_mai78101 (248 views)
2014-04-05 13:34:39

trollwarrior1 (205 views)
2014-04-04 12:06:45

CJLetsGame (212 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!