Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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  
  Locking-List, a new Data Structure designed for video games.  (Read 7208 times)
0 Members and 1 Guest are viewing this topic.
Offline CodeBunny

Senior Member


Medals: 4
Projects: 3



« Posted 2011-09-05 14:50:49 »

A bit of warning - this is going to get a bit involved and very technical.



When I was in the middle stages of designing the Java Rabbit Engine (http://jrabbit.minds-eye-games.com/), I began considering how I would manage groups of active game objects. There are a number of stipulations for a rigorous game engine:

Necessary:
  • Hold as many objects as needed (basically, no max limit).
  • Dynamically resize to hold new objects.
  • Dynamically remove objects when they are no longer needed.
  • Iterate through the current objects in the list, performing operations wherever needed.

These would be nice:
  • Maintain order of addition.
  • Not allow duplicate objects.
  • Allow random access.
  • Allow for fast checking of whether or not an object is present in the list.
  • When an iteration is started, iterate over the same objects that were initially in the list, even if some of them are removed or new ones are added during iteration (basically, cache removals and additions until iteration is over). (Remember this as Point X, it's potentially incredibly useful and I decided I wanted to have it.)

And, obviously, all of these need to be as fast as possible, and not increase as more objects are added to the list. Basically, they need to be O(1) instead of O(n) in operation time, if possible.

So, these ideal points in mind, I started looking at existing methods. From what I found, JME and Slick both seemed to use ArrayList fairly often. It makes sense. Once the objects are on the list, it's basically array-fast to iterate through them.

However, how dynamic are they? ArrayList in particular seems a particularly bad choice, because when you need to add more objects than its max limit, it spazzes out and needs to allocate and reseed an entire new array. Also, when you want to remove objects, it has to search through the entire thing to find it, and then it needs to move objects around to fill the gap! The larger the list gets, the longer these adjustments will take. Therefore, though it doesn't have a technical limit, it has a practical one.

The concept I would use for this is: For an iteration-based data structure to allow for "unlimited objects," the maximum number of objects it can iterate through and maintain a viable operation speed should be effectively the same as the number of objects it can have while performing dynamic operations (additions and removals) and keep that viable operation speed.

So ArrayList, the common choice, seems to be non-optimal. What other choices are there?

Let's look at a few:

LinkedList:
Good:
  • Not quite as fast as an Array or ArrayList, but still quite competitive.
  • Adding new objects is a breeze, being O(1) and totally independent of the number of other entries in the list.
  • Can append an entirely different LinkedList to its end without any increase in operation time.
Bad:
  • Removing objects is O(n).
  • Allows for duplicate entries.
  • Does not allow Point X.

LinkedHashMap:
Good:
  • About LinkedList fast.
  • By Keying objects to themselves, adding and removing objects can approach constant time.
  • Does not allow for duplicate entries.
  • Checking if an object is contained in the list is essentially O(1).
Bad:
  • Cumbersome API.
  • Does not allow Point X.

In all seriousness, lobotomizing a LinkedHashMap seemed like the most feature-complete option. However, I felt I could do better than that, so I made my own data structure.

The result is something I call LockingList (and yes, it has been designed to accommodate Point X).

Here is the code, including documentation:

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  
304  
305  
306  
307  
308  
309  
310  
311  
312  
313  
314  
315  
316  
317  
318  
319  
320  
321  
322  
323  
324  
325  
326  
327  
328  
329  
330  
331  
332  
333  
334  
335  
336  
337  
338  
339  
340  
341  
342  
343  
344  
345  
346  
347  
348  
349  
350  
351  
352  
353  
354  
355  
356  
357  
358  
359  
360  
361  
362  
363  
364  
365  
366  
367  
368  
369  
370  
371  
372  
373  
374  
375  
376  
377  
378  
379  
380  
381  
382  
383  
384  
385  
386  
387  
388  
389  
390  
391  
392  
393  
394  
395  
396  
397  
398  
399  
400  
401  
402  
403  
404  
405  
406  
407  
408  
409  
410  
411  
412  
413  
414  
415  
416  
417  
418  
419  
420  
421  
422  
423  
424  
425  
426  
427  
428  
429  
430  
431  
432  
433  
434  
435  
436  
437  
438  
439  
440  
441  
442  
443  
444  
445  
446  
447  
448  
449  
450  
451  
452  
453  
454  
455  
456  
457  
458  
459  
460  
461  
462  
463  
464  
465  
466  
467  
468  
469  
470  
471  
472  
473  
474  
475  
476  
477  
478  
479  
480  
481  
482  
483  
484  
485  
486  
487  
488  
489  
490  
491  
492  
493  
494  
495  
496  
497  
498  
499  
500  
501  
502  
503  
504  
505  
506  
507  
508  
509  
510  
511  
512  
513  
514  
515  
516  
517  
518  
519  
520  
521  
522  
523  
524  
525  
526  
527  
528  
529  
530  
531  
532  
533  
534  
535  
536  
537  
538  
539  
540  
541  
542  
543  
544  
545  
546  
547  
548  
549  
550  
551  
552  
553  
554  
555  
556  
557  
558  
559  
560  
561  
562  
563  
564  
565  
566  
567  
568  
569  
570  
571  
572  
573  
574  
575  
576  
577  
578  
579  
580  
581  
582  
583  
584  
585  
586  
587  
588  
589  
590  
591  
592  
593  
594  
595  
596  
597  
598  
599  
600  
601  
602  
603  
604  
605  
606  
607  
608  
609  
610  
611  
612  
613  
614  
615  
616  
617  
618  
619  
620  
621  
622  
623  
624  
625  
626  
627  
628  
629  
630  
631  
632  
633  
634  
635  
636  
637  
import java.util.HashMap;
import java.util.Iterator;

import org.jrabbit.base.data.structures.base.Container;

/*****************************************************************************
 * This class is supposed to handle large, dynamic amounts of objects and be
 * able to iterate through them very quickly without being disturbed by changes
 * to its structure. Duplicate entries are not supported. Random access is also
 * not supported.
 *
 * At its heart, LockingList is a LinkedList. However, the weakness in Linked
 * Lists is that removal operations are inefficient when compared to add methods
 * - it has to iterate through the entire list, checking each node. To attempt
 * to combat this, when objects are added to the list, a HashMap keys the object
 * reference to the node that contains it. Thereafter, when remove() is called,
 * it finds the node from the HashMap and does a quick and easy cull.
 *
 * It's a little extreme to make a custom data structure for a single purpose,
 * but all the common "fast" data structures I know of have some flaws in a
 * gaming environment (especially since I wanted to remember order of addition).
 * ArrayList is fast, but it takes time to resize. LinkedLists are fast and
 * highly dynamic when adding, but removal requires a search through the list.
 * LinkedHashMaps have some O(1) operations, but have needless overhead. Adding
 * to the mix is the fact that I needed something that could be modified during
 * iteration without causing errors. Ultimately, I decided to marry a HashMap
 * and a LinkedList. The result is a very stripped down data structure that,
 * nevertheless, performs very well. When no changes are occurring, it performs
 * at LinkedList speed (which is quite fast), and even when the list is being
 * rapidly changed, its operations tend towards O(1) complexity (and are fairly
 * fast at that).
 *
 * @author Chris Molini
 *
 * @param <T>
 *            The type of object to hold in the list.
 *****************************************************************************/

public class LockingList<T> implements Container<T>
{
   /**
    * The currently active list of items. Because iteration runs through the
    * actual list of objects, we cannot safely allow this list to change while
    * we are going through it. Therefore, we need to cache changes and apply
    * them after the list is safe again.
    **/

   protected UList main;

   /**
    * A list to cache addition operations. When the list is "locked," all add()
    * operations are applied to this.
    **/

   protected UList addCache;

   /**
    * Likewise, this caches removal operations.
    *
    * NOTE: When we are unlocked, we want to simply remove objects from the
    * main list, but when we lock the list we need to add them to a storage
    * structure. So, we modify this list on instantiation to provide that
    * functionality.
    **/

   protected UList removalCache;

   /**
    * This reference is meant to switch between main and toAdd. When locked,
    * the list automatically (without unnecessary checks) delegates addition
    * operations.
    **/

   protected UList adding;

   /**
    * Similarly, this reference handles directing removal operations.
    **/

   protected UList removing;

   /**
    * When the list is locked, if a clear() is demanded, we cannot destroy the
    * list immediately - we need to remember it until we unlock the list (and
    * immediately clear the list on release).
    **/

   protected boolean clear;

   /*************************************************************************
    * Creates a default, unlocked, empty list.
    *************************************************************************/

   public LockingList()
   {
      main = new UList();
      addCache = new UList();

      // We need to define toRemove to have its remove operations cache the
     // objects instead of the default operations.
     removalCache = new UList()
      {
         protected boolean remove(T object)
         {
            super.add(object);
            return false;
         }

         protected void remove(UList list)
         {
            super.add(list);
         }
      };

      adding = main;
      removing = main;
   }

   /*************************************************************************
    * Adds an object or caches the operation.
    *
    * @param object
    *            The object to add.
    *            
    * @return True if the add succeeded, false if not.
    ***************************************************************/
@Override
   public boolean add(T object)
   {
      return adding.add(object);
   }
   
   /*************************************************************************
    * Attempts to add every supplied object.
    *
    * @param objects
    *            The objects to add.
    ***************************************************************/
@Override
   public void add(T... objects)
   {
      for(T object : objects)
         add(object);
   }

   /*************************************************************************
    * Handles adding an entire list of objects of the same generic type.
    *
    * if the other list is locked, only the main list is applied. Pending
    * additions and removals do not factor in.
    *
    * @param list
    *            the list of objects to add.
    *************************************************************************/

   public void add(LockingList<T> list)
   {
      adding.add(list.main);
   }

   /*************************************************************************
    * Removes an object or caches the operation.
    *
    * @param object
    *            The object to remove.
    *
    * @return If locked, automatically returns false. If unlocked, returns
    *         whether or not the removal was successful.
    ***************************************************************/
@Override
   public boolean remove(T object)
   {
      return removing.remove(object);
   }
     
   /*************************************************************************
    * Attempts to remove the supplied list of objects.
    *
    * @param objects
    *            The objects to remove.
    ***************************************************************/
@Override
   public void remove(T... objects)
   {
      for(T object : objects)
         remove(object);
   }

   /*************************************************************************
    * Handles removing an entire list of objects of the same type.
    *
    * If the other list is locked, only the active list is applied. Pending
    * additions and removals do not factor in.
    *
    * @param list
    *            The list of objects we wish to remove.
    *************************************************************************/

   public void remove(LockingList<T> list)
   {
      removing.remove(list.main);
   }

   /*************************************************************************
    * Checks if an object is on the list.
    *
    * @param object
    *            The object to check for.
    *
    * @return If the object is on the list.
    ***************************************************************/
@Override
   public boolean contains(T object)
   {
      return main.contains(object) || addCache.contains(object);
   }

   /*************************************************************************
    * Clears the list if unlocked. If locked, it clears the current state of
    * toAdd and toRemove, and remembers that it should clear the main list on
    * release().
    *************************************************************************/

   public void clear()
   {
      if (locked())
      {
         clear = true;
         addCache.clear();
         removalCache.clear();
      }
      else
         main.clear();
   }

   /*************************************************************************
    * Returns the size of the main list. If the list is locked, there is no
    * concession to pending adds and removals.
    *
    * @return How many elements are in the active list.
    ***************************************************************/
@Override
   public int size()
   {
      return main.size;
   }

   /*************************************************************************
    * Returns the predicted size of the list. If the list is not locked, this
    * returns the same value of size(), but if it is, it returns the estimated
    * final size after pending operations have been resolved.
    *
    * NOTE: This list can be inaccurate. It assumes that all pending add and
    * remove operations will be successful, which may not be the case
    * (depending on whether the objects involved in the operations are on the
    * list or not).
    *
    * @return The estimate for list size when it is unlocked.
    *************************************************************************/

   public int predictedSize()
   {
      return main.size + addCache.size - removalCache.size;
   }

   /*************************************************************************
    * Returns whether or not the active list is empty. Possibly inaccurate if
    * the list is locked.
    *
    * @return If the active list has elements.
    *************************************************************************/

   public boolean isEmpty()
   {
      return main.size > 0;
   }

   /*************************************************************************
    * Redirects removal and addition operations, causing the active list to
    * become unchangeable through normal methods.
    *************************************************************************/

   public void lock()
   {
      adding = addCache;
      removing = removalCache;
   }

   /*************************************************************************
    * If locked, redirects removal and addition to the main list, and causes
    * any cached operations to be applied to the main list.
    *************************************************************************/

   public void unlock()
   {
      if (locked())
      {
         adding = main;
         removing = main;

         if (clear)
         {
            clear();
            clear = false;
         }

         main.add(addCache);
         addCache.clear();

         main.remove(removalCache);
         removalCache.clear();
      }
   }

   /*************************************************************************
    * Checks to see if the list is caching changes.
    *
    * @return Whether or not operations apply to the main list.
    **************************************************************************/

   public boolean locked()
   {
      return adding != main;
   }

   /*************************************************************************
    * Allows iteration through the LockingList in the usual manner. Auto-locks
    * the list.
    *
    * @return The iterator through the main list.
    ***************************************************************/
@Override
   public Iterator<T> iterator()
   {
      lock();
      return main.iterator();
   }

   /* ********************************************************************* *
    * ************************** Internal Classes ************************* *
    * ********************************************************************* */


   /*************************************************************************
    * Provides a singly-linked list implementation to dynamically store a large
    * list of objects for quick iteration.
    *
    * @author Chris Molini
    *************************************************************************/

   protected class UList implements Iterable<T>
   {
      /**
       * How many elements the list has.
       **/

      private int size;

      /**
       * The first node in the list.
       **/

      private UListNode first;

      /**
       * The last node in the list.
       **/

      private UListNode last;

      /**
       * This keys object references with their positions on the list, making
       * removal operations much faster. Without this, we would need to
       * iterate through the entire list to search for each removal.
       **/

      private HashMap<T, UListNode> removalMap;

      /*********************************************************************
       * Creates an empty list.
       *********************************************************************/

      protected UList()
      {
         removalMap = new HashMap<T, UListNode>();
         clear();
      }

      /*********************************************************************
       * Returns whether or not the specified object is on the list.
       *
       * @param obj
       *            The object to check for.
       *
       * @return If the object is on the list.
       *********************************************************************/

      protected boolean contains(T obj)
      {
         return removalMap.containsKey(obj);
      }

      /*********************************************************************
       * Clears the list.
       *********************************************************************/

      protected void clear()
      {
         first = last = null;
         removalMap.clear();
         size = 0;
      }

      /*********************************************************************
       * Adds an object to the end of the list if it is not already on it.
       *
       * @param object
       *            The object to add.
       * @return
       *********************************************************************/

      protected boolean add(T object)
      {
         if (size == 0)
         {
            first = last = new UListNode(object);
            removalMap.put(object, first);
            size++;
            return true;
         } else if (!removalMap.containsKey(object))
         {
            last = last.setNext(object);
            removalMap.put(object, last);
            size++;
            return true;
         }
         return false;
      }

      /*********************************************************************
       * Adds another list to this one.
       *
       * Instead of appending the entire list in one fell swoop, we iterate
       * through the list and call add() for every object on it. This helps us
       * preserve entry uniqueness.
       *
       * @param uL
       *            the list to add.
       *********************************************************************/

      protected void add(UList uL)
      {
         UListNode toAdd = uL.first;
         while (toAdd != null)
         {
            add(toAdd.obj);
            toAdd = toAdd.next;
         }
      }

      /*********************************************************************
       * Attempts to remove an object from the list.
       *
       * Ordinarily, removal from a LinkedList requires searching through the
       * entire thing, removing an object once and if it is found. To try to
       * speed up the process, we use a HashMap to store the locations of
       * objects on the list, and use that for quickly finding which node to
       * remove.
       *
       * @param object
       *            The object to remove.
       *
       * @return True if the object was found and removed, false otherwise.
       *********************************************************************/

      protected boolean remove(T object)
      {
         UListNode toRemove = removalMap.remove(object);

         // If toRemove is null, the object was not on the list.
        if (toRemove != null)
         {
            if (toRemove == first)
            {
               first = first.next;
               if (first != null)
                  first.last = null;
            }
            else if (toRemove == last)
            {
               last = last.last;
               last.next = null;
            }
            else
            {
               toRemove.last.next = toRemove.next;
               toRemove.next.last = toRemove.last;
            }
            size--;
            return true;
         }
         return false;
      }

      /*********************************************************************
       * Attempts to remove from this list every element in another.
       *
       * @param list
       *            The list of objects to attempt to remove.
       *********************************************************************/

      protected void remove(UList list)
      {
         UListNode toRemove = list.first;
         while (toRemove != null)
         {
            remove(toRemove.obj);
            toRemove = toRemove.next;
         }
      }

      /*********************************************************************
       * Returns a String representation of the list.
       *
       * @return A list of every entry in the list. Elements are divided by
       *         line breaks.
       ***********************************************************/
@Override
      public String toString()
      {
         String results = "List: \n";
         if (size > 0)
            for (T obj : this)
               results += "\n" + obj;
         else
            results += "(empty)";
         return results;
      }

      /*********************************************************************
       * Returns the iterator. It's inadvisable to change the list contents
       * while an iterator is working.
       *
       * @return The iterator for perusing the list.
       ***********************************************************/
@Override
      public Iterator<T> iterator()
      {
         return new UListIterator(first);
      }

      /*********************************************************************
       * A node in our doubly-linked list.
       *
       * @author Chris Molini
       *********************************************************************/

      private class UListNode
      {
         /**
          * The data the node stores.
          **/

         private T obj;

         /**
          * The reference to the next node in the list.
          **/

         private UListNode next;

         /**
          * The reference to the last node in the list.
          **/

         private UListNode last;

         /*****************************************************************
          * Creates an empty node containing the specified object.
          *****************************************************************/

         private UListNode(T object)
         {
            obj = object;
         }

         /*****************************************************************
          * Used to efficiently append items to the end of the list.
          *
          * @param object
          *            The object to add.
          *
          * @return The reference to the next node in the list. Simplifies
          *         appending.
          *****************************************************************/

         private UListNode setNext(T object)
         {
            next = new UListNode(object);
            next.last = this;
            return next;
         }

         /*****************************************************************
          * Returns a string representation of the node.
          *
          * @return A string that describes the object the node contains and
          *         whether or not the list has references to a node before
          *         and after it.
          *******************************************************/
@Override
         public String toString()
         {
            return "Object: " + obj + "\nLast: " + (last != null)
                  + "\nNext: " + (next != null);
         }
      }

      /*********************************************************************
       * Defines an iterator through our list.
       *
       * To get the best possible speed, there are no checks to throw
       * ConcurrentModificationException, though editing the list while
       * iterating can potentially throw a bug. It will manifest in a
       * NullPointerException and immediately crash the program.
       *
       * This would ordinarily be a severe problem, but the entire list as a
       * whole is designed to not cause those problems during execution, and
       * so operations should remain steady if the developer uses the
       * available methods.
       *
       * @author Chris Molini
       *********************************************************************/

      private class UListIterator implements Iterator<T>
      {
         /**
          * The node used to iterate.
          **/

         private UListNode node;

         /*****************************************************************
          * Creates an empty iterator. Whenever a UList calls iterator(), it
          * automatically sets the node to reference the beginning of the
          * list.
          *****************************************************************/

         private UListIterator(UListNode n)
         {
            node = new UListNode(null);
            node.next = n;
         }

         /*****************************************************************
          * Returns whether or not there are more elements in the iterator.
          *
          * @return If the next element will be null.
          *******************************************************/
@Override
         public boolean hasNext()
         {
            return node.next != null;
         }

         /*****************************************************************
          * Returns the next object and advances iteration.
          *
          * @return The next object in the iteration.
          *******************************************************/
@Override
         public T next()
         {
            node = node.next;
            return node.obj;
         }

         /*****************************************************************
          * The iterator does not support modifying the list.
          *******************************************************/
@Override
         public void remove()
         {
            throw new UnsupportedOperationException();
         }
      }
   }
}


So, what do you guys think? Is the above an improved method? Or is vanilla ArrayList better, and there are advantages/disadvantages in the different methods I'm not aware of?
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #1 - Posted 2011-09-05 15:09:06 »

    • When an iteration is started, iterate over the same objects that were initially in the list, even if some of them are removed or new ones are added during iteration (basically, cache removals and additions until iteration is over). (Remember this as Point X, it's potentially incredibly useful and I decided I wanted to have it.)

    Sounds like you just reinvented the ConcurrentHashMap/etc. in java.util.concurrent. Also, I have never found ArrayList (or any sensibly chosen collection) to be a bottleneck in a game - have you actually profiled this? Do you have a valid use case where this kind of collection makes a noticeable difference in frame rate?[/list]

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

    Senior Member


    Medals: 4
    Projects: 3



    « Reply #2 - Posted 2011-09-05 16:07:29 »

    I ran a few tests, constantly adding objects (it was a stress test), and I noticed some stutters as the number of objects got very high. Granted, the stutters only happened once each jump, but I still felt that they shouldn't be there.

    Additionally, the removal time is what really concerns me.
    Games published by our own members! Check 'em out!
    Legends of Yore - The Casual Retro Roguelike
    Offline theagentd
    « Reply #3 - Posted 2011-09-05 16:25:16 »

      • When an iteration is started, iterate over the same objects that were initially in the list, even if some of them are removed or new ones are added during iteration (basically, cache removals and additions until iteration is over). (Remember this as Point X, it's potentially incredibly useful and I decided I wanted to have it.)

      Sounds like you just reinvented the ConcurrentHashMap/etc. in java.util.concurrent. Also, I have never found ArrayList (or any sensibly chosen collection) to be a bottleneck in a game - have you actually profiled this? Do you have a valid use case where this kind of collection makes a noticeable difference in frame rate?[/list]
      I have. It's a huge problem in particle systems, especially if you want them sorted.

      Myomyomyo.
      Offline Riven
      « League of Dukes »

      JGO Overlord


      Medals: 793
      Projects: 4
      Exp: 16 years


      Hand over your head.


      « Reply #4 - Posted 2011-09-05 16:59:48 »

      There is an inherent flaw in your design. You are tracking added and removed objects in different lists. If you add and remove the same object a certain number of times, you can't be sure what you end up with after you 'unlock' your datastructure. It depends on the order in which you process the lists holding the added/removed items, not the order in which you added/removed your items.

      You should have a single list holding 'events': the item and whether it is currently in an added or removed state. Map<Object, Boolean> modifications or List<Pair<Object, Boolean>> for example. Once you unlock it you can iterate over the map, adding and deleting the elements to/from your 'main' collection.

      Hi, appreciate more people! Σ ♥ = ¾
      Learn how to award medals... and work your way up the social rankings
      Offline Orangy Tang

      JGO Kernel


      Medals: 56
      Projects: 11


      Monkey for a head


      « Reply #5 - Posted 2011-09-05 17:18:20 »

        • When an iteration is started, iterate over the same objects that were initially in the list, even if some of them are removed or new ones are added during iteration (basically, cache removals and additions until iteration is over). (Remember this as Point X, it's potentially incredibly useful and I decided I wanted to have it.)

        Sounds like you just reinvented the ConcurrentHashMap/etc. in java.util.concurrent. Also, I have never found ArrayList (or any sensibly chosen collection) to be a bottleneck in a game - have you actually profiled this? Do you have a valid use case where this kind of collection makes a noticeable difference in frame rate?[/list]
        I have. It's a huge problem in particle systems, especially if you want them sorted.

        Big particle systems should be statically allocated, IMHO. They're specialised enough to require their own data structure, and I certainly wouldn't use this LockingList for them.

        [ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
        Offline theagentd
        « Reply #6 - Posted 2011-09-05 17:20:19 »

        Hehe, I guess that's true...

        Myomyomyo.
        Offline CodeBunny

        Senior Member


        Medals: 4
        Projects: 3



        « Reply #7 - Posted 2011-09-05 17:49:56 »

        There is an inherent flaw in your design. You are tracking added and removed objects in different lists. If you add and remove the same object a certain number of times, you can't be sure what you end up with after you 'unlock' your datastructure. It depends on the order in which you process the lists holding the added/removed items, not the order in which you added/removed your items.

        You should have a single list holding 'events': the item and whether it is currently in an added or removed state. Map<Object, Boolean> modifications or List<Pair<Object, Boolean>> for example. Once you unlock it you can iterate over the map, adding and deleting the elements to/from your 'main' collection.

        Hmm. I never thought of that. That's a good idea.

          • When an iteration is started, iterate over the same objects that were initially in the list, even if some of them are removed or new ones are added during iteration (basically, cache removals and additions until iteration is over). (Remember this as Point X, it's potentially incredibly useful and I decided I wanted to have it.)

          Sounds like you just reinvented the ConcurrentHashMap/etc. in java.util.concurrent. Also, I have never found ArrayList (or any sensibly chosen collection) to be a bottleneck in a game - have you actually profiled this? Do you have a valid use case where this kind of collection makes a noticeable difference in frame rate?[/list]
          I have. It's a huge problem in particle systems, especially if you want them sorted.

          Big particle systems should be statically allocated, IMHO. They're specialised enough to require their own data structure, and I certainly wouldn't use this LockingList for them.

          Personally, I don't like statically allocated data structures for potentially dynamic lists. The only thing you get out of using an Array(List) vs. a LinkedList is a modicum of speed, and it locks you into a static-size mindset. I particularly feel this way about particle systems, actually.

          To give you an example of why I like dynamic particles: consider Micron, the game I released alongside the engine this is included in. When a lot of the things die, they give off a burst of particles. All of those particles are part of a single system. I simply add new particles at wherever is required. Because it is a dynamic list, I don't have to worry about running out of space, and I can just dump more in whenever I need to.
          Offline Cero
          « Reply #8 - Posted 2011-09-05 18:01:23 »

          Guess I'm old school in this regard.
          I only use bare arrays.
          I use Lists in special cases when you never have to search for one element / dont need random access. -> particle systems

          In my latest minigame, I used a combination of ArrayLists and LinkedLists to try something else; for what its worth, it worked, but I personally wouldn't trust it in a very big game. Not sure.

          Also, my main point here is: You never need "unlimited" space, because you can never use an infinite amount of objects anyway.
          All arrays have limits, and I just set them accordingly.

          Best example is of course a given particle system in which you set the maxParticles parameter.

          Offline CodeBunny

          Senior Member


          Medals: 4
          Projects: 3



          « Reply #9 - Posted 2011-09-05 18:25:43 »

          I know what you mean, but IMHO I don't agree. And yes, you never can handle an infinite amount of objects, but the finite limit that you can reach is impacted by the setup that you use, so attempts to push that limit are to be encouraged, right? Smiley

          But in all honesty, I would never, ever use an Array to handle game objects because of removal time. Having to search for an object so that you can remove it can become a big deal when many objects are active at once, especially if you want to remove more than one at a time. If the object list is not dynamic, then an Array is the most perfect data structure imaginable. However, I have been trying to design for situations where it is not.
          Games published by our own members! Check 'em out!
          Legends of Yore - The Casual Retro Roguelike
          Offline Cero
          « Reply #10 - Posted 2011-09-05 18:52:06 »

          But in all honesty, I would never, ever use an Array to handle game objects because of removal time. Having to search for an object so that you can remove it can become a big deal when many objects are active at once, especially if you want to remove more than one at a time. If the object list is not dynamic, then an Array is the most perfect data structure imaginable. However, I have been trying to design for situations where it is not.

          Well I'm only concerned with data structures in action packed arrays so to speak; for example the inventory item data structure could be whatever - not important.
          And in these action packed arrays, a given object shall only be removed when a certain event happens; meaning we have straight causality.

          My point is, there is no removal time, because you never search.
          For example some logic results in an enemy dying, the next line of code is a check if he's dead, and then, null that object.
          I don't have to iterate separately to remove it; I remove it when I'm already iterating, to update this object.
          item = null;    obviously is isn't as easy with arraylist, because you cannot remove an object while iterating the collection.

          Quote
          but the finite limit that you can reach is impacted by the setup that you use, so attempts to push that limit are to be encouraged, right?
          I don't know, at some point, practically speaking, things will get so convoluted... Depends on the game I guess, but there is always a limit...
          In super mario there would never be more than like 30 enemies on one screen, at one time I guess. Multiply this by the length of one map and you have your limit. Maps have similar lengths by game design...
          I just see limits everywhere internally
          if the whole screen is full of stuff, doesnt really make such sense to add double that... maybe for benchmarking

          I doubt practical usefulness, is what I'm saying.

          Though interesting technically.

          Offline CodeBunny

          Senior Member


          Medals: 4
          Projects: 3



          « Reply #11 - Posted 2011-09-05 19:20:25 »

          Hmm. That's interesting, but it strikes me as a bit implementation-dependent. It wouldn't work for a randomly generated game, for example, where there are no limits.

          Plus, when you add capabilities for things like projectiles, where entities can spin off other entities at will, you're either forced to limit the number of active projectiles per character (a limitation I feel is very artificial and have always disliked) or allow for some form of overflow. Maybe you simply double the maximum number of entries in the array, but it seems more rigorous to me to simply use a dynamic list.

          Regardless, this is getting off topic. I didn't mean to say that I feel static-sized lists are bad; if they work for you then they work, and the end product is all that matters. My intention in starting this topic was to offer a different look at a dynamic list-type data structure. I added it to my engine and I got better and more flexible performance, IMHO. I put up this topic as a discussion of my method. I'm still going to use it, because it's been working very well for me so far, and I thought others may be interested. Also, if other people have any optimization advice, I would be glad to see how it works when implemented.
          Offline counterp

          Senior Member


          Medals: 11



          « Reply #12 - Posted 2011-09-08 03:20:39 »

          it's not that fast and the stuff under your 'necessary' list can all be fulfilled by collections that already exist?
          Offline CodeBunny

          Senior Member


          Medals: 4
          Projects: 3



          « Reply #13 - Posted 2011-09-08 11:45:02 »

          What Collection should I use, then? I would really like to use the best data structure possible, but I haven't had much experience in the various types.
          Offline counterp

          Senior Member


          Medals: 11



          « Reply #14 - Posted 2011-09-08 15:13:55 »

          depends on your specific uses

          ArrayList has very fast adding, but very slow removing, is ordered, and iterating over it is quick (plus you can use indexes to remove objects semi-quickly if you know the index). the contains method is slow.

          HashSet (it actually is just using a HashMap in the background, you can write a faster implementation of this by yourself or I can give you one) has decent adding, very fast removing (tops out arraylist if you are adding as often as removing) is unordered, and does not iterate as quickly. the contains method is fast.

          those are just 2 popular collections.

          usually when I'm going for speed I use my own HashSet implementation.
          Offline CodeBunny

          Senior Member


          Medals: 4
          Projects: 3



          « Reply #15 - Posted 2011-09-08 17:42:30 »

          Wouldn't LinkedHashSet be better in terms of iteration time?
          Offline concerto49

          Junior Member





          « Reply #16 - Posted 2011-09-08 22:52:05 »

          Wouldn't LinkedHashSet be better in terms of iteration time?

          No. Not unless you have a high % of collisions (which would ruin a hash anyway). Iterating over an array is a lot faster than a linked set of references, so even if it's a larger array with possible nulls, in general it'd be faster. Unless of course the array is very large with very few elements - which is a different problem. You can make it reduce size the array after a certain number of elements have been removed.

          High performance, fast network, affordable price VPS - Cloud Shards
          Available in Texas, New York & Los Angeles
          Need a VPS Upgrade?
          Online pitbuller
          « Reply #17 - Posted 2011-09-14 08:20:18 »

          I don't have to iterate separately to remove it; I remove it when I'm already iterating, to update this object.
          item = null;    obviously is isn't as easy with arraylist, because you cannot remove an object while iterating the collection.

          You can remove object when iterating from Array List. I did lot of benchmarks and conclusion was that for-each loop is not good for Array List. Instead I ask size and then make normal for loop. If you need to remove something you need to update size and index.
          Just size-- and index--. Its not maybe that clean but it work and can save hefty amount time.
          Offline Cero
          « Reply #18 - Posted 2011-09-14 11:57:43 »

          I don't have to iterate separately to remove it; I remove it when I'm already iterating, to update this object.
          item = null;    obviously is isn't as easy with arraylist, because you cannot remove an object while iterating the collection.

          You can remove object when iterating from Array List. I did lot of benchmarks and conclusion was that for-each loop is not good for Array List. Instead I ask size and then make normal for loop. If you need to remove something you need to update size and index.
          Just size-- and index--. Its not maybe that clean but it work and can save hefty amount time.

          Well I prefer bare arrays anyway. But using this, I would always fear that something would get screwed up, like removing the wrong, or whatever; and such a behavior is then hard to spot - like what really happened - which was removed which shouldn't be removed

          I just like the control and accessibility of an array so much.

          Online pitbuller
          « Reply #19 - Posted 2011-09-14 16:06:34 »

          I don't have to iterate separately to remove it; I remove it when I'm already iterating, to update this object.
          item = null;    obviously is isn't as easy with arraylist, because you cannot remove an object while iterating the collection.

          You can remove object when iterating from Array List. I did lot of benchmarks and conclusion was that for-each loop is not good for Array List. Instead I ask size and then make normal for loop. If you need to remove something you need to update size and index.
          Just size-- and index--. Its not maybe that clean but it work and can save hefty amount time.

          Well I prefer bare arrays anyway. But using this, I would always fear that something would get screwed up, like removing the wrong, or whatever; and such a behavior is then hard to spot - like what really happened - which was removed which shouldn't be removed

          I just like the control and accessibility of an array so much.

          Index removing with arrayList is as simple as with array. I prefer Libgdx Array with any objects and with things like coordinates I just set up many normal single dimensional float[] with circleBuffering.
          Offline Eli Delventhal

          JGO Kernel


          Medals: 42
          Projects: 11
          Exp: 10 years


          Game Engineer


          « Reply #20 - Posted 2011-10-05 23:00:35 »

          I usually just use a HashMap and an ArrayList of its keys.

          See my work:
          OTC Software
          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.

          Dwinin (21 views)
          2014-09-12 09:08:26

          Norakomi (55 views)
          2014-09-10 13:57:51

          TehJavaDev (66 views)
          2014-09-10 06:39:09

          Tekkerue (33 views)
          2014-09-09 02:24:56

          mitcheeb (54 views)
          2014-09-08 06:06:29

          BurntPizza (38 views)
          2014-09-07 01:13:42

          Longarmx (24 views)
          2014-09-07 01:12:14

          Longarmx (30 views)
          2014-09-07 01:11:22

          Longarmx (28 views)
          2014-09-07 01:10:19

          mitcheeb (37 views)
          2014-09-04 23:08:59
          List of Learning Resources
          by Longor1996
          2014-08-16 10:40:00

          List of Learning Resources
          by SilverTiger
          2014-08-05 19:33:27

          Resources for WIP games
          by CogWheelz
          2014-08-01 16:20:17

          Resources for WIP games
          by CogWheelz
          2014-08-01 16:19:50

          List of Learning Resources
          by SilverTiger
          2014-07-31 16:29:50

          List of Learning Resources
          by SilverTiger
          2014-07-31 16:26:06

          List of Learning Resources
          by SilverTiger
          2014-07-31 11:54:12

          HotSpot Options
          by dleskov
          2014-07-08 01:59:08
          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!