Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (476)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (532)
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  
  A*  (Read 5842 times)
0 Members and 1 Guest are viewing this topic.
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


A*
« Posted 2010-01-24 01:38:54 »

Bugger, now my naive A* implementation isn't fast enough Sad

Who can make me a fast one with the appropriately quick datastructures backing it? I've got upwards of 300 entities wandering around a fairly simple grid topology of around 256x256 in size. It's got to be very fast indeed.

Cas Smiley

Offline kappa
« League of Dukes »

JGO Kernel


Medals: 74
Projects: 15


★★★★★


« Reply #1 - Posted 2010-01-24 01:53:11 »

how is your A* working atm, do you calculate an A* path for every entity movement?
is it grid based pathfinding or mesh nodes?

you could do something like have a simple line check, straight to an entities destination, if nothings is in the way then you can skip the A* altogether and just move the entity there directly.

Another option, which would be much lighter on cpu would be to not use A* at all and go for something like steering behavior, this is very light on cpu and good for avoiding simple obstacles.

Flow Fields could also work pretty well for a tower defence game, again faster and cheaper then A*.
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 74
Projects: 15


★★★★★


« Reply #2 - Posted 2010-01-24 02:08:17 »

Grid based is gonna be really expensive for that many units anyway, you really need to use some sort of nav mesh instead, this will be massively faster.

if you must use grid based, you should looking into implementing something like HPA* (or MM Abstraction) instead of pure A*, it'll be much quicker then A* especially for long paths.

Basically its tiered path finding where you have a high level grid (large squares) then a low level grid (smaller and finer detail), paths are calculated using the high level grid and then units move along it using the low level grid. Much faster then A* but uses slightly more memory.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #3 - Posted 2010-01-24 02:53:02 »

If you're still using the same AStar class from ages back, I got a decent speed up by switching the closed list to a HashMap mapping nodes of the same location onto themselves. You should be able to replace the open list with a TreeMap as well to remove even more linear list scans.

If that's not enough I'd be tempted to go with flow fields + steering behaviours for the smaller droids, and only use A* for the bigger enemies. Or since your map is quite small you could go with 'smell' based pathfinding like some roguelikes use.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline pjt33
« Reply #4 - Posted 2010-01-24 08:45:37 »

Bugger, now my naive A* implementation isn't fast enough Sad

Who can make me a fast one with the appropriately quick datastructures backing it? I've got upwards of 300 entities wandering around a fairly simple grid topology of around 256x256 in size. It's got to be very fast indeed.

Cas Smiley
In addition to the previous question about your graph, what heap are you currently using, and what heuristic? Also, are the costs special-cased in any way (e.g. boolean)?
Offline Alan_W

JGO Knight


Medals: 8
Projects: 3


Java tames rock!


« Reply #5 - Posted 2010-01-24 08:56:33 »

Probably teaching my grandmother to suck eggs here, but ...

I had similar issues with this years Assassins4k entry and solved it by:
i) When the player leaves a room (in this case grid square) I calculate A* from the player to every location in the map, storing a 'NSEW' direction 'to the player' on each room in the first location in an array of direction indicators.
ii) The rest of the array of direction indicators is filled with precalculated A* searches for random locations.

Each entity follows one of the A* paths and when it reaches the end selects another path.  Entities in attack mode alternate between following path 0 (which always leads to the player) and a random pre-calculated path.

This does mean that enemies attacking the player dynamically change direction as the player moves, and take no account of line-of sight visibility - the player cannot run round the corner and hide. On Assassins4k I ignored this.

On my StormTheCastle engine, I solved this by copying the current best route to the player onto the entity as a list, whenever the current A* ran out (provided the player was line-of-sight visible).  If the player isn't visible, the entity drops out of attack mode. Really one should do the copy whenever the player is visible, but this costs more and in practice the difference isn't noticeable. The copy operation is cheaper than the full A* search.

The precalculated routes do make the entities go anywhere.  If they have to stay local to a particular location, then they need to be grouped into areas, or you need to calculate a set per entity on the fly, whenever the entity goes into patrol mode.  Two routes might be sufficient.  On my StormTheCastle engine, all routes are converted to a set of velocity/time pairs, so patrol routes are independent of location and can be precalculated.  If the entity hits something, it marches in place, until the next velocity/time pair is scheduled.  Not perfect, but saves on A* searches.

Conclusion
If you have a lot of entities attacking the player, then this comes out cheaper than recalculating A* every time an entity finishes their current path.  If the entities are attacking other entities, then this doesn't provide much of a saving.

Edit: You can see the StormTheCastle A* implementation in action.  This is a really old version and doesn't work well on the Mac (low frame rate due to poor choice of image format causing endless conversions).  The enemies are a bit too persistent too.  Fixed on later unpublished version.
http://homepage.ntlworld.com/alan.d.waddington/demo/GameEngineDemo.html

Edit2: Just realised that I don't limit max depth on my A* search, which I should for large maps.  Added to my to-do list Smiley
Edit3: Found that I do limit on the cost function, which is distance: Deleted from to-do list.

Time flies like a bird. Fruit flies like a banana.
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #6 - Posted 2010-01-25 14:06:35 »

Sorry for tardy reply - busy etc.

So: here's where I'm at.

The grid size is at most 256x256, which covers a map more than 10 screens wide. This isn't an entirely unreasonable grid size I think. I'd like to have been able to use hierarchical grids but due to the nature of the grid's contents and the way the game plays, proper A* is really the only way to go here. The turrets, when placed down, subtly alter the cost of traversing nearby squares, and these subtle costs overlap, etc, meaning we get a quite complicated difficulty map. The way the player places turrets is significant as it essentially corrals the gidrahs into certain pathways, and it's essential for strategy. I don't think it'd work very well if I tried the low-res grid on top approach.

There's no player as such; each gidrah can have one of many, many possible destinations, depending on its own personal strategy. The destinations are chosen very simply, and then A* finds out how to get there. The gidrah will simply ignore any buildings en route with the exception that certain buildings influence the difficulty of grid squares nearby as outlined above. Anything they collide with, they attack. At any rate, this means I can't do a nice simple pre-calc of all possible paths on the map from every location because the destinations are dynamic and change over time, and additonally the map topology changes over time too, and different gidrahs have different ideas about what sort of difficulties they can cross (basically: stupid gidrahs will try to run past turrets and get killed unless there are a lot of turrets there; clever gidrahs will skirt around them).

Now, every gidrah has its own A* pathfinder; however, they all spawn from the same points, and there is a route cache which I store (and age over time and discard after a while). The route cache stores the path between any start point and any end point on the grid (it would be nice to have a data structure which somehow indexed all the points on the path in between too, which would make things even more efficient). If the route is determined to be clear of total obstacles when a gidrah's on the start point, it bypasses A* completely. About 75% of the path finding at the start of a level follows this path as the gidrahs all spawn in the same locations - the first gidrah finds the initial route, and then the next gidrah just picks it up from the cache. It's when they get close to their destination that things start to slow down as they aren't allowed to directly walk through each other, so they start doing lots of frantic pathfinding - fortunately quite close to the target.

The heuristic (from memory, I'm @ work) is a very simple h = distance, which as the gidrahs are allowed to walk in diagonal lines for approx 1.42x the normal cost of a move, gives nice natural direct looking paths over the grid to targets. It's just wibbly enough through chance that it looks more natural.

Now, with 500 gidrahs all attempting to find a path every frame you wouldn't be entirely suprised if the framerate was rather bad, so they're limited to a maximum of just a few steps each frame; so I was looking at maybe 1000 A* steps per frame, which I hadn't thought would be that expensive. I thought wrong Smiley

Orangy - yes, I was using that simple A* class in SPGL. I'm halfway through converting it to use TreeMap for the open list and HashMap for the closed list; last night I got it all to compile but it's just hanging during a search now. My fear was that I was abusing the use of TreeMap: the comparator uses the f value of a node, and therefore node.compareTo(otherNode) == 0 when their f values are the same. However, the node.equals() method compares userState, not f; I wonder if this is causing me problems. It's supposed to work, I think, according to the TreeMap docs.

I expect TreeMap and HashMap are going to massively speed up the A* implementation so I will let you know if it solves my problem. If I can reliably get 500 gidrahs swarming towards the player's buildings at 60fps on my rubbishy laptop I will consider that a success Smiley (and ooh you are really going to enjoy setting up a massive array of defences to mow them down!!)

Cas Smiley




Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #7 - Posted 2010-01-25 14:08:07 »

In addition to the previous question about your graph, what heap are you currently using, and what heuristic? Also, are the costs special-cased in any way (e.g. boolean)?

Costs are either -1 for impassable, or a float value describing the difficulty of the move, based on 1.0 for NSEW movement, and adding certain amounts based on nearby danger. I think by heap you mean the TreeMap I've just put in last night..?

Cas Smiley

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #8 - Posted 2010-01-25 14:15:07 »

My fear was that I was abusing the use of TreeMap: the comparator uses the f value of a node, and therefore node.compareTo(otherNode) == 0 when their f values are the same. However, the node.equals() method compares userState, not f; I wonder if this is causing me problems. It's supposed to work, I think, according to the TreeMap docs.

I find TreeMap a tricky beast, which is a shame because it's damn powerful. IIRC TreeMap expects two nodes that are equal() to also have compareTo()==0, so your compareTo() should check userData first and return 0 if they're identical. At least something very similar to that was tripping me up.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #9 - Posted 2010-01-25 15:06:38 »

It's when they get close to their destination that things start to slow down as they aren't allowed to directly walk through each other, so they start doing lots of frantic pathfinding - fortunately quite close to the target.

How's about: a route is planned at spawn, and perhaps whenever the routing conditions substantially change (player deploys a turret on the planned path, etc), and then use steering behaviours to follow the path and take care of the overcrowding drama, like this. Once the gidrah is close enough to the target, I'd imagine that purely using steering behaviours would be sufficient to find a space at the target building.
It'll give you loads of parameters to tweak for different unit types:
  • Follow the path exactly/treat it more as a suggestion
  • Clump up and move as a swarm/ignore other units
  • Only attack the assigned target/get distracted by targets of opportunity on the away

So: A* for the global strategic planning, steering behaviours for the local interactions.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #10 - Posted 2010-01-25 15:40:43 »

I don't know that steering will really solve any problems here - the interactions only really come into play when they're very close to their target usually, so the actual length of time spent searching for a path is much smaller than it might otherwise be anyway.

<edit>Besides I have no idea how to implement steering behaviour Wink

Cas Smiley

Offline pjt33
« Reply #11 - Posted 2010-01-25 15:42:37 »

Costs are either -1 for impassable, or a float value describing the difficulty of the move, based on 1.0 for NSEW movement, and adding certain amounts based on nearby danger.
Ok, so probably no cunning tricks to be played there.

Quote
I think by heap you mean the TreeMap I've just put in last night..?
"Priority queue" is another name for it. I can't work out where in SPGL (assuming the SourceForge CVS at http://spgl.cvs.sourceforge.net/viewvc/spgl/ to be up-to-date) the A* implementation is hiding, so I can't see what the map is from and to, but TreeMap doesn't sound like a great solution to me. IIRC it's a self-balancing tree. A simple binary heap should be more efficient.
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #12 - Posted 2010-01-25 16:33:39 »

I'd love a simple binary heap class, but there isn't one in the JDK is there?

Can anyone provide one that just uses ints?

And not forgetting that it needs to sort on f but be able to add and remove based on userState (both f and userstate are ints though so no nasty objects or casting needed).

The SPGL A* is possibly in spgl-extra in the algorithms package. I've already altered it a bit for this game so it has pluggable topology.

Cas Smiley

Offline pjt33
« Reply #13 - Posted 2010-01-25 17:38:52 »

I'd love a simple binary heap class, but there isn't one in the JDK is there?
PriorityQueue. It's not great at arbitrary removal, though.

Quote
Can anyone provide one that just uses ints?
I thought you just said your costs were floats? Or are you looking for a queue whose elements are ints with priorities which are floats?

Quote
And not forgetting that it needs to sort on f but be able to add and remove based on userState (both f and userstate are ints though so no nasty objects or casting needed).
It seems to me that the easy approach here is to make the heap just handle Nodes and make the Map handle the mapping between userState and nodes. The Map can do this with a simple array lookup.
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #14 - Posted 2010-01-25 17:58:34 »

PriorityQueue - bugger.

I can make my costs into ints pretty easily if it makes my life easier Smiley

I'm a bit confused as to how I'd do your last suggestion - the heap is what, again? And how do I synchronize the heap with a map?

Cas Smiley

Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #15 - Posted 2010-01-25 18:35:49 »

I don't know that steering will really solve any problems here - the interactions only really come into play when they're very close to their target usually, so the actual length of time spent searching for a path is much smaller than it might otherwise be anyway.

<edit>Besides I have no idea how to implement steering behaviour Wink

Cas Smiley
It should handle your crowding problem. I imagine a gidrah's thought process currently goes something like
  • plan route
  • follow route
  • find that route is blocked by another gidrah
  • repeat
So you're spending time planning routes that are invalidated pretty quickly by the movement of other gidrahs. I imagine you also see gidrahs dithering back and forth as they follow these abortive routes.

Implementation is pretty easy, especially as gidrahs don't have momentum - the overall motion arises from the combination of trivially simple behaviours:
  • Path following: find the closest point on the route polyline, calculate the point some distance further along the path, move towards that point
  • Collision avoidance: Move directly away from gidrahs that are too close
  • Swarming: Move towards the average position of nearby gidrahs
Each behaviour results in a desired movement vector: just add them up (weighted appropriately), normalise to the gidrah's movement speed, and add to the position.

I've had a quick go at implementing a simple target-seeking, collision-avoiding behaviour. Results here, code here. Some interesting behaviour (fast gidrahs barging through crowds of their slower peers, making room for late arrivals at the target point, etc) from simple rules of motion.
Offline pjt33
« Reply #16 - Posted 2010-01-26 00:35:43 »

I'm a bit confused as to how I'd do your last suggestion - the heap is what, again? And how do I synchronize the heap with a map?

I'll give you the public signatures before the full code:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
public class BinaryHeap<E>
{
   public Node<E> insert(E userData, float cost);
   public Node<E> peek();
   public Node<E> pop();
   public void remove(Node<E> node);
   public void changeCost(Node<E> node, float newCost);
   public int size();

   public static class Node<E>
   {
      public E userData;
   }
}

This is a data structure for the open list. You'll probably want to adapt it to replace <E> with the primitive int, but that's a minor detail. The point is that the mapping from user data to the Node is done externally: if you don't want to support removal then you can ignore it, but if you do then it's up to the caller (in this case the A* implementation) to maintain the mapping from user data to Node. I've done it this way specifically to support your use case, because you can use a linearised array to do the mapping.

The code, plus a few unit tests to check that I haven't bodged my parent/child index calculations. The changeCost method isn't currently tested.
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  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
258  
259  
260  
261  
262  
263  
264  
265  
266  
267  
268  
269  
270  
271  
272  
273  
274  
275  
276  
277  
278  
279  
280  
281  
282  
283  
284  
285  
286  
287  
288  
289  
290  
291  
292  
293  
294  
295  
296  
297  
298  
299  
300  
301  
302  
303  
package com.akshor.pjt33.util;

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class BinaryHeap<E>
{
   @SuppressWarnings("unchecked")
   private Node<E>[] heap = new Node[128];

   private int size = 0;

   public Node<E> insert(E userData, float cost)
   {
      Node<E> node = new Node<E>();
      node.userData = userData;
      node.cost = cost;

      // Expand if necessary.
     if (size == heap.length)
      {
         @SuppressWarnings("unchecked")
         Node<E>[] newHeap = new Node[size << 1];
         System.arraycopy(heap, 0, newHeap, 0, size);
         heap = newHeap;
      }

      // Insert at end and bubble up.
     heap[size] = node;
      node.heapIdx = size;
      upHeap(size++);

      return node;
   }

   public Node<E> peek()
   {
      return heap[0];
   }

   public Node<E> pop()
   {
      Node<E> popped = heap[0];
      heap[0] = heap[--size];
      heap[size] = null;
      if (size > 0) downHeap(0);
      return popped;
   }

   public void remove(Node<E> node)
   {
      // This is what node.heapIdx is for.
     heap[node.heapIdx] = heap[--size];
      heap[size] = null;
      if (size > node.heapIdx)
      {
         if (heap[node.heapIdx].cost < node.cost)
         {
            upHeap(node.heapIdx);
         }
         else
         {
            downHeap(node.heapIdx);
         }
      }
      // Just as a precaution: should make stuff blow up if the node is abused.
     node.heapIdx = -1;
   }

   public void changeCost(Node<E> node, float newCost)
   {
      float oldCost = node.cost;
      node.cost = newCost;
      if (newCost < oldCost)
      {
         upHeap(node.heapIdx);
      }
      else
      {
         downHeap(node.heapIdx);
      }
   }

   public int size()
   {
      return size;
   }

   private void upHeap(int idx)
   {
      Node<E> node = heap[idx];
      float cost = node.cost;
      while (idx > 0)
      {
         int parentIdx = (idx - 1) >> 1;
         Node<E> parent = heap[parentIdx];
         if (cost < parent.cost)
         {
            heap[idx] = parent;
            parent.heapIdx = idx;
            idx = parentIdx;
         }
         else break;
      }
      heap[idx] = node;
      node.heapIdx = idx;
   }

   private void downHeap(int idx)
   {
      Node<E> node = heap[idx];
      float cost = node.cost;

      while (true)
      {
         int leftIdx = 1 + (idx << 1);
         int rightIdx = leftIdx + 1;

         if (leftIdx >= size) break;

         // We definitely have a left child.
        Node<E> leftNode = heap[leftIdx];
         float leftCost = leftNode.cost;
         // We may have a right child.
        Node<E> rightNode;
         float rightCost;

         if (rightIdx >= size)
         {
            // Only need to compare with left.
           rightNode = null;
            rightCost = Float.POSITIVE_INFINITY;
         }
         else
         {
            rightNode = heap[rightIdx];
            rightCost = rightNode.cost;
         }

         // Find the smallest of the three costs: the corresponding node
        // should be the parent.
        if (leftCost < rightCost)
         {
            if (leftCost < cost)
            {
               heap[idx] = leftNode;
               leftNode.heapIdx = idx;
               idx = leftIdx;
            }
            else break;
         }
         else
         {
            if (rightCost < cost)
            {
               heap[idx] = rightNode;
               rightNode.heapIdx = idx;
               idx = rightIdx;
            }
            else break;
         }
      }

      heap[idx] = node;
      node.heapIdx = idx;
   }

   /**
    * We assume that the user will be sensible with this! The design is aimed
    * at people who have common sense and want efficiency.
    */

   public static class Node<E>
   {
      /*package*/ float cost;

      /*package*/ int heapIdx;

      public E userData;
   }

   @Test
   public void regressionTestOne()
   {
      BinaryHeap<String> heap = new BinaryHeap<String>();
      heap.insert("A", 0);
      heap.insert("B", 1);
      assertEquals("A", heap.pop().userData);
      heap.insert("D", 3);
      heap.insert("L", 11);
      assertEquals("B", heap.pop().userData);
      heap.insert("K", 10);
      heap.insert("C", 2);
      assertEquals("C", heap.pop().userData);
      heap.insert("E", 4);
      assertEquals("D", heap.pop().userData);
      heap.insert("I", 8);
      heap.insert("H", 7);
      assertEquals("E", heap.pop().userData);
      heap.insert("F", 5);
      assertEquals("F", heap.pop().userData);
      heap.insert("G", 6);
      heap.insert("J", 9);
      assertEquals("G", heap.pop().userData);
      assertEquals("H", heap.pop().userData);
      assertEquals("I", heap.pop().userData);
      assertEquals("J", heap.pop().userData);
      assertEquals("K", heap.pop().userData);
      assertEquals("L", heap.pop().userData);
      assertEquals(0, heap.size());
   }

   @Test
   public void downHeapLeft()
   {
      BinaryHeap<String> heap = new BinaryHeap<String>();
      heap.insert("A", 0);
      heap.insert("B", 1);
      heap.insert("C", 2);
      heap.insert("D", 3);
      assertEquals("A", heap.pop().userData);
      assertEquals("B", heap.pop().userData);
      assertEquals("C", heap.pop().userData);
      assertEquals("D", heap.pop().userData);
      assertEquals(0, heap.size());
   }

   @Test
   public void downHeapRight()
   {
      BinaryHeap<String> heap = new BinaryHeap<String>();
      heap.insert("A", 0);
      heap.insert("C", 2);
      heap.insert("B", 1);
      heap.insert("D", 3);
      assertEquals("A", heap.pop().userData);
      assertEquals("B", heap.pop().userData);
      assertEquals("C", heap.pop().userData);
      assertEquals("D", heap.pop().userData);
      assertEquals(0, heap.size());
   }

   @Test
   public void testRemovalDownheap()
   {
      BinaryHeap<String> heap = new BinaryHeap<String>();
      heap.insert("A", 0);
      Node<String> nodeB = heap.insert("B", 1);
      heap.insert("C", 2);
      heap.insert("D", 3);
      heap.insert("E", 4);
      heap.insert("F", 5);

      heap.remove(nodeB);

      assertEquals("A", heap.pop().userData);
      assertEquals("C", heap.pop().userData);
      assertEquals("D", heap.pop().userData);
      assertEquals("E", heap.pop().userData);
      assertEquals("F", heap.pop().userData);
      assertEquals(0, heap.size());
   }

   @Test
   public void testRemovalUpheap()
   {
      BinaryHeap<String> heap = new BinaryHeap<String>();
      heap.insert("A", 0);
      heap.insert("B", 3);
      heap.insert("C", 1);
      Node<String> nodeD = heap.insert("D", 4);
      heap.insert("E", 5);
      heap.insert("F", 6);
      heap.insert("G", 2);

      // Heap currently looks like
     //              A:0
     //             /   \
     //          B:3     C:1
     //         /   \   /   \
     //       D:4  E:5  F:6  G:2
     //
     // If we delete D, swapping G up, then we get:
     //              A:0
     //             /   \
     //          B:3     C:1
     //         /   \   /
     //       G:2  E:5  F:6
     // Assuming we don't upheap, two pops will remove A and C (swapping and
     // down-heaping F and E) and the third will remove B. If we tried to use
     // the minimum test case (F:2, no G) then although we would have an
     // inconsistent intermediate state we would pop out in the correct
     // order, because popping() C would put F to root and downheap it.
     heap.remove(nodeD);

      assertEquals("A", heap.pop().userData);
      assertEquals("C", heap.pop().userData);
      assertEquals("G", heap.pop().userData);
      assertEquals("B", heap.pop().userData);
      assertEquals("E", heap.pop().userData);
      assertEquals("F", heap.pop().userData);
      assertEquals(0, heap.size());
   }
}
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #17 - Posted 2010-01-26 12:48:42 »

Oooh, that's brilliant, I'll try that at home tonight when I get back from work.

I got the algorithm working with TreeMap in the end but it had issues. Finding the head to pop was easy enough; however, actually removing the head (or doing a contains(), or get(), based on userstate) was very slow, as it required a treeMap.values().contains()... and that seemed to do a copy of the whole TreeMap into another Collection of some sort. So it was generating a meg of garbage every second, and the Comparator used by the TreeMap was costing over 10% of the compiled code time - arrgh. All in all when I got to about 100 gidrahs it was costing 15ms / frame just to do 500 A* iterations!

So I can't wait to try out this extremely lean-looking binary heap class. I'm quite surprised this structure doesn't already exist in the JDK, as it's very well documented all over the internet.

Cas Smiley

Offline Jono
« Reply #18 - Posted 2010-01-26 20:40:27 »

I think the off-the-shelf java.util.PriorityQueue is implemented as a binary heap.
Offline pjt33
« Reply #19 - Posted 2010-01-26 22:18:44 »

I think the off-the-shelf java.util.PriorityQueue is implemented as a binary heap.
It is, but it has O(n) operations to remove an element or reduce its key, which makes it pretty pointless for Dijkstra/A*/C.
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #20 - Posted 2010-01-27 01:04:36 »

Brilliant! With a bit of modification the binary heap worked perfectly.

I added a Map inside the binary heap to map userstates to nodes so that they can be rapidly found and removed, as well.

End result: A* now barely registers on the profiler Smiley

Cas Smiley

Offline Jono
« Reply #21 - Posted 2010-01-27 02:36:46 »

It is, but it has O(n) operations to remove an element or reduce its key, which makes it pretty pointless for Dijkastra/A*/C.
Looking at the API, that seems to be the case (actually there's no reduceKey method, so you'd have to remove and re-insert). It's still usable if you just place the duplicates on the queue instead of reducing keys though.

Anyway, you're point that the stock implementation in the Collections framework isn't so good is definitely spot on.
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #22 - Posted 2010-01-27 10:50:46 »

pjt33, please drop me a line so I can add you into the credits for the game for that bit of code  Kiss

Cas Smiley

Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #23 - Posted 2010-01-27 12:35:10 »

Haven't read through all the text here, but here are my thoughts:

1) Multithreading: Create a few A* threads (2-3 should suffice). Each thread has it's own memory of the grid in order to mark tiles visited etc.
2) Share paths: Objects A,B,C in the same tile going to the same destination would use the same path, and hence no need to run A* 3 times.
3) When building tower you're probably recalculating the path using A*. You only need to do that if a tower was placed in the path the object is traveling. So, just check the path, see if the tiles have changed, and if they are only then do A* again. (Adding a new tower outside of the path doesn't affect the path, because no new route better than the current one was created).
4) Most importantly: Don't select just one data structure for the lists. You can achieve O(1) for all operations (except insert) by using a couple of data structures. PriorityQueue and Map goes a long way.


Try to prevent the game running A* by caching paths, sharing paths, etc. And if you really need to run A*, make it run fast.

Ok Smiley

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline pjt33
« Reply #24 - Posted 2010-01-27 12:49:26 »

(4) Most importantly: Don't select just one data structure for the lists. You can achieve O(1) for all operations (except insert) by using a couple of data structures. PriorityQueue and Map goes a long way.
You can get amortised O(1) for everything using a suitably designed calendar queue, but a) the hidden constant matters; b) the complexity of the code (maintenance cost) matters; c) if it's no longer a bottle-neck, why bother?
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #25 - Posted 2010-01-27 13:12:18 »

Indeed, the A* implementation is now so fast that I don't really need to optimise it further, but I'm still getting 30fps on the crappy laptop when there's 100 gidrahs attacking the base. 20% of the time is now spent rendering sprites and the rest is mostly native, and the pathfinding barely registers, but every little helps at this stage. To my mind we should easily be getting 60fps on a dual 1.6GHz Turion64, even if it does have a very slow graphics card in it.

We are already cacheing paths between two points in a hashmap (and all points in between too). I planned to put in the invalidation optimisations you mentioned already, but I suspect that's not going to give me a huge speed increase any more.

I've considered using another thread to do the pathfinding in as well - but it probably only makes sense where there's more than one physical CPU core. As it is, the OS and GC and OpenGL drivers are already using a fairly decent proportion of the other CPU, so after synchronizing the data between the two threads it might only prove to be a very small speed increase for a lot of extra complexity.

Thanks for all your help, guys Smiley

Cas Smiley

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.

pw (17 views)
2014-07-24 01:59:36

Riven (17 views)
2014-07-23 21:16:32

Riven (14 views)
2014-07-23 21:07:15

Riven (17 views)
2014-07-23 20:56:16

ctomni231 (43 views)
2014-07-18 06:55:21

Zero Volt (40 views)
2014-07-17 23:47:54

danieldean (32 views)
2014-07-17 23:41:23

MustardPeter (36 views)
2014-07-16 23:30:00

Cero (51 views)
2014-07-16 00:42:17

Riven (50 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!