1

I have a Sprite class:

public class Sprite {
    public static ArrayList<Sprite> sprites = null;
    private Texture texture = null;

    public Sprite(Texture texture) {
        sprites.add(this);
        this.texture = texture;
    }

    public void render(SpriteBatch batch) {
        batch.draw(texture);
    }

    public void dispose() {
        sprites.remove(this);
    }
}

Before I create any sprites, I make sure that the Sprite class has a reference to the pool of sprites that are going to be rendered:

public class Main extends ApplicationAdapter {
    private static ArrayList<Sprite> sprites = new ArrayList<Sprite>();

    public Main() {
        Sprite.sprites = sprites;

        new Sprite("texture.png");
    }

    @Override
    public void render(SpriteBatch batch) {
        for (int i = 0; i < sprites.size(); i++)
            sprites.get(i).render(batch);
    }
}

So now when I create a new sprite, it will automatically render without me having to manually add it into the ArrayList.

The problem is that sprites can be disposed during the time that for loop is running, and thus some sprites won't be rendered for that specific frame.

I do not wish to loop through the items backwards such as:

for (int i = sprites.size() - 1; i >= 0; i--)
    sprites.get(i).render(batch);

Because this will render my sprites out of order (sprites that should be on top will be covered).

My only solution so far has been to have another ArrayList that keeps track of which objects to dispose, as such:

public class Sprite {
    public static ArrayList<Sprite> sprites = null, garbage = null;

    //everything else the same

    public void dispose() {
        garbage.add(this);
    }
}

And then during render, I first remove all the garbage from sprites, then render sprites:

for (int i = 0; i < garbage.size(); i++)
    sprites.remove(garbage.get(i));
garbage.clear();

for (int i = 0; i < sprites.size(); i++)
            sprites.get(i).render(batch);

This method works, but I feel it is inefficient. (Having two arraylists? Then doing two for loops?)

Is there any way I can loop through Sprites without it skipping a Sprite when a Sprite is disposed? I don't want to loop through Sprites backwards though because it will mess up the order.

I've now tested this with a synchronized list, but I am unable to get this working properly.

Testable code, (with java.util.ConcurrentModificationException)

import java.util.*;

class Ideone {

    public static class Sprite {
        public static List<Sprite> sprites = null;
        public int age = 0;

        public Sprite() {
            synchronized(sprites) {
                sprites.add(this);
            }
        }

        public void render() {
            age++;
            if (age > 30)
                dispose();
        }

        public void dispose() {
            synchronized(sprites) {
                sprites.remove(this);
            }
        }
    }

    private static List<Sprite> sprites = Collections.synchronizedList(new ArrayList<Sprite>());

    public static void main(String[] args) {
        Sprite.sprites = sprites;

        new Sprite();
        new Sprite();

        for (int i = 0; i < 60; i++)
            render();

    }

    public static void render() {
        synchronized(sprites) {
            Iterator<Sprite> iterator = sprites.iterator();
            while (iterator.hasNext())
                iterator.next().render();
        }
    }
}
Dave Chen
  • 10,887
  • 8
  • 39
  • 67
  • You could `synchronize` access to the `List` so that it cannot be modified whilst rendering, but this isn't ideal whilst rendering if the UI thread gets locked out. Alternatively, could queue a 'request' to modify the thread and handle this queue before rendering each frame. – Mapsy May 27 '15 at 16:41

3 Answers3

2

If you just have to take care of remove, then use Iterator like

Iterator<Sprite> itr = sprites.iterator();
while (itr.hasNext()) {
  // do something with itr.next()
  // call itr.remove() to remove the current element in the loop
}

Iterator provide remove method to remove any item from the list but make sure you don't add any new item to the list otherwise it will throw ConcurrentModificationException.

Arjit
  • 3,290
  • 1
  • 17
  • 18
  • I like this idea, but how will Sprite.dispose() run itr.remove()? Note that the only place sprites will change is from dispose(). In other words, I'm not removing any sprites within the loop, it's happening somewhere else but at the same time the loop is running. – Dave Chen May 27 '15 at 16:43
  • This link can help you out in that case:- http://stackoverflow.com/questions/5849154/can-we-write-our-own-iterator-in-java – Arjit May 27 '15 at 16:49
  • I can't use an Iterator either because new items will be added to the ArrayList too. – Dave Chen May 27 '15 at 16:50
  • then you can use ListIterator - which provides you to add new element to the list – Arjit May 27 '15 at 16:51
  • I'm still getting a `ConcurrentModificationException`, I'm not using `itr.remove()` because I'm not removing the sprites within the while/forloop. The ArrayList is being modified from dispose(), which happens outside of the loop, but happens at the same time as the loop. I've done `synchronized (sprites)` with an Iterator and a ListIterator, and both throw the same exception. – Dave Chen May 27 '15 at 16:59
  • you have to override the iterator method implementation - to call your dispose method – Arjit May 27 '15 at 17:06
  • Sorry I'm still not understanding. The dispose method on my sprites are being called from another thread entirely, so there's no way for me to know which Sprite is going to be removed when I'm looping. – Dave Chen May 27 '15 at 17:09
2

First of all if sprites list is accessed from multiple threads you need to synchronize access to it or use thread safe data structure (e.g. CopyOnWriteArrayList or CopyOnWriteArraySet).

Sprite.dispose can directly remove itself from sprites in this case.

kostya
  • 9,221
  • 1
  • 29
  • 36
  • I just tried `List sprites = Collections.synchronizedList(new ArrayList();` and `synchronized (sprites)` + and iterator, but I got a `ConcurrentModificationException` because Sprites also gets new items during the loop too. I also took a peak at CopyOnWriteArrayList, and this seems more inefficient than my two ArrayLists (because you're copying the entire array, as opposed to only referencing the ones to delete). – Dave Chen May 27 '15 at 16:54
  • If you use `Collections.synchronizedList` you still need to synchronize access while iterating: http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#synchronizedList(java.util.List) – kostya May 28 '15 at 01:00
  • Are you talking about a synchronized block? I am using one while iterating. – Dave Chen May 28 '15 at 01:02
  • If you use synchronized properly there is no way it can happen, because calling sprites.remove or add will wait until `synchronized (sprites)` block is completed. Are you sure that you are iterating in the `synchronized (sprites)` block too? – kostya May 28 '15 at 01:23
  • Actually, the synchronized block only guarantees that if you are using `iterator.add/remove`. If you're using `add/remove` from the list directly, you'll still hit the exception. And of course, using the iterator just to add or remove stuff would be way more inefficient than just keeping another list. – Dave Chen May 28 '15 at 05:53
  • 1. There is no iterator.add(), 2. Can you please post the code that uses synchronizedList and still leads to ConcurrentModificationException? I believe you are not synchronizing correctly. 3. The performance needs to be measured before you can say for sure. E.g. removing an element from a LinkedList is O(1) operation. – kostya May 28 '15 at 05:57
  • Sure, I've edited it into my question. Thank you for your continued support. I'm thinking that `sprites.remove(this)` is the issue, but I'm not sure how to use an iterator to remove it within dispose. – Dave Chen May 28 '15 at 06:25
  • The way you use synchronized is correct (though there is no need to add explicit synchronized blocks around add and remove methods, synchronizedList does it for you). The reason you are getting `ConcurrentModificationException` is because you are iterating and modifying the list at the same time (in a single thread). You should modify your code to call `it.remove()` as suggested in the @Arjit's answer. – kostya May 28 '15 at 06:36
  • I think I've got it. Essentially, when the sprite should be removed, simply return false on render, and if the render is false, then remove via the iterator. I'm accepting your answer (also +1) because of the explanations in the comments. – Dave Chen May 28 '15 at 06:51
0

Here's what worked for me clicky:

import java.util.*;

class Ideone {

    public static class Sprite {
        public static ArrayList<Sprite> sprites = null;
        public int age = 0;

        private boolean removed = false;

        public Sprite() {
            sprites.add(this);
        }

        public boolean render() {
            if (removed)
                return false;
            age++;
            if (age > 30)
                dispose();
            return true;
        }

        public void dispose() {
            removed = true;
        }
    }

    private static ArrayList<Sprite> sprites = new ArrayList<Sprite>();

    public static void main(String[] args) {
        Sprite.sprites = sprites;

        new Sprite();
        new Sprite();

        for (int i = 0; i < 60; i++)
            render();

    }

    public static void render() {
        Iterator<Sprite> iterator = sprites.iterator();
        while (iterator.hasNext())
            if (!iterator.next().render())
                iterator.remove();
    }
}

So, when a sprite should be removed, I set a quick bool that tells the main render loop to remove it with the iterator. I'll have to adapt this to use a sync'd list (so that adding items doesn't throw an exception).

Dave Chen
  • 10,887
  • 8
  • 39
  • 67