Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Ok, so i have created my first "game" and it uses a lot of java's collections. for example, i have a bunch of monsters in a HashSet which sometimes gives me the fabled java.util.ConcurrentModificationException when i try to modify the HashSet.

Basically im getting these exceptions when im within a for loop and then some other part of the system find it suitable to add or remove an element to/from the collection.

My options as far as i know is:

1) Use a Thread Safe collection or use Collections.asSynchronizedCollection().

2) Only work on copies of the collection when looping through it.

My question thus becomes. Is there any other methods more widely deployed solutions in the gamedevelopment world that handle's these issues?

As an example, i thought ive read somewhere that queues are more heavily used instead of collections and that work is done on input and output queues. <-- any elaboration on this would also be appreciated!

Thanks for your time!

share|improve this question
    
Are you using any of the classes in the java.util.concurrent package? I've found that they work efficiently and reliably in multi-threaded scenarios. –  Randolf Richardson Aug 25 '11 at 2:48
    
The first question has to be "Are you using multi-threading?" –  Peter Taylor Aug 26 '11 at 6:05
    
@Peter yes i am. Basically i have a MoveEngine and a RenderEngine which is in its own threads. And then im using the observer pattern on data models where certain event's can occur. Upon these event's i might modify the collections im looping through in MoveEngine or RenderEngine. –  netbrain Aug 26 '11 at 10:01

4 Answers 4

The root of your trouble lies in the necessity to add or remove elements while iterating over collection. You should keep these things to a minimum, but sometimes it just can't be avoided.

Making copies every time you want to iterate a collection is often not an option due to performance reasons.

Now there are two possibilities: your loop and your adds|removals are either on the different threads or on the same thread.

If it's the multithreaded case, Tyn gave you pointers on what to do. One simple solution would be to synchronize all access to the collection, using some object as the monitor. It may be slow if your collection is large, because threads wanting to add or remove something will be blocked while waiting for iteration to complete:

// For loop
synchronized (lockObject) 
{  
    for (...) // Iterations here
}

//Now when other thread wants to add or remove something, 
// it needs to synchronize too:

// Somewhere on the other thread
synchronized (lockObject) 
{  
    gameObjects.add(...);
}

You can use ConcurrentHashMap, but be prepared to face the consequences. I can remember only that its iterators sometimes reflect adds or removals occured since the iterator construction and sometimes they don't, but there should be plenty of other subtle things, maybe like "get" operation placing a memory barrier. So if you add and remove things very rarely, it may be better to use a "copy on write" approach.

Funny thing is, unless your threaded operations with objects on the loop are slow as hell (and usually they shouldn't be), it may actually be faster to keep them single-threaded. I deduced that if there is a bunch of monsters with some petty Update() functions, and you want to process their little functions on different threads, you're in for a trouble :) So keep in mind that multithreading just for the sake of it eats up your CPU with context swaps and supply you with livelocks and starvation issues here and there.

If it's the single thread case, then removal of the elements in the collection being iterated won't work, so there are two another options:

  1. The most usable option: add a queue of objects to add|remove, and process them out of your loop.
  2. If you only need to remove a current object of an iteration phase, it is possible to use an indexed collection with a for loop, and then remove current element while adjusting loop counter. Or just loop backwards.

Just for clarity, example for the first approach:

while ((objectToRemove = objectsToRemove.Pop()) != null)
{
    allGameObjects.Remove(objectToRemove);
}

foreach(var gameObject in allGameObjects)
{
   // process your objects here as always, but if you need to
   // add or remove an object, push it to the appropriate queue. 
}

And example for the second approach:

for (int i = 0; i < allGameObjects.Count; i++)
{                
   // to remove an object, do something like
   allGameObjects.RemoveAt(i--);
}
share|improve this answer
1  
I assume @netbrain issue was coming from a modification of the hashmap from another thread, not from what's inside the loop itself. In this case, neither option you're suggesting will fix the issue. –  Tyn Aug 24 '11 at 14:09
1  
Thanks, after re-reading question several times this morning I've started to sense a certain multithreaded feeling, especially if by "input and output queues" poster meant Consumer-Producer scenario or something. I guess I'll edit my answer a bit. –  Vigil Aug 25 '11 at 7:42
    
In the single thread case when you want to remove the current object, you can just call Iterator.remove(); –  msell Aug 17 '12 at 5:50

There is a few concepts that might help you in Java:

  1. Synchronized methods. A method can be made synchronous by adding the synchronized statement to its definition. This has two effects: it is not possible that two calls on the same method of the same object instance to interleave anymore, and it guarantees that any further call will benefit of the changes made during the previous call.

    More on that here: Synchronized Methods

  2. Synchronized statements. A statement block that makes a particular object synchronous. Could be useful in your case, by synchronizing your HashMap.

    More on that here: Intrinsic Locks and Synchronization

  3. Concurrent collections. The java.util.concurrent package defines collections with atomic operations (i.e. operations that are guaranteed to be executed fully before giving time to another thread). That might help you avoiding the need of synchronization.

    More on that here: Concurrent Collections

  4. There's more. There is a lot of tools to help you dealing with concurrency issues in Java. Specialized thread wrappers like Executors, Lock objects, Atomic variables, a thread-safe PRNG, and more. All of those are described in the Java lesson on Concurrency.

In general, the Java lesson on concurrency cover all you need to know about threading and synchronization. It can be found here. It is a must-read to start dealing efficiently with this difficult problem. You'll also understand more deeply what are the issues that can come with synchronization, like deadlocks and starvation, as well as to avoid it.

I hope this helped!

share|improve this answer
1  
Making a method synchronous doesn't give any guarantees about further calls seeing changes made unless the fields affected are volatile. (Besides which, the problem is likely to have nothing to do with threading). –  Peter Taylor Aug 24 '11 at 21:05

Option 1 is only relevant if the problem relates to threading, and the majority of ConcurrentModificationExceptions don't. Vigil gives some useful options; there's one which he hasn't mentioned, and that's to mark objects as deleted.

In other words, you give the object a field isDeleted; you ignore deleted objects in calculations; and on one of your loops you use the remove() method of the Iterator when it returns a deleted object.

share|improve this answer
    
+1 for the isDeleted (although I use the isAlive). Plus you get to reuse dead game entities with an Entity Pool ;) –  pek Aug 25 '11 at 23:56

If you find yourself iterating over the set a lot more than you mutate it, there's a cool class called CopyOnWriteArraySet or CopyOnWriteArrayList that will make your life easier. It basically basically captures a 'snapshot' of the set when you start iterating, and performs any mutations (adds/removes) after iterating is complete.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.