Gdx Util Collections Iteration

The Gdx Util Collections:

A guide to GDX Collections iterators, their pitfalls, and what you can do.

by Henry Batt

---

This documentation is on Collections in the GDX framework, specifically the Array, and specifically their iterators, however it will cover the whole suite of collections.

Whilst it is written primarily with the focus on arrays this documentation will cover the core foundation, which is applicable to all Gdx Util Collections.

The official Gdx documentation is here and will be referenced amongst other things.

Note: The import of this data type is import com.badlogic.gdx.utils.Array;

So what is it

The Array is LibGDX's approach to a traditional resizable array of objects (as one might expect). It also provides additional features such as bag functionality or backing array access (Further outlined in the documentation here).

Now whilst this is nice, a major issue is highlighted in the direct next section and is directly caused by LibGDX's approach to memory management in game engines and their philosophy of fine-grained control of resources and their lifetimes (Further outlined here if interested).

What is wrong then?

Once again this all sounds very nice and helpful, however, there is a major caveat on this, and that is iterators. The following section from the official collections documentaion outlines this in what I feel is a clear and concise manner so I shall simply provide it below.
The iterator returned by iterator() is always the same instance, allowing the Array to be used with the enhanced for-each (for( : )) syntax without creating garbage. Note however that this differs from most iterable collections! It cannot be used in nested loops, else it will cause hard to find bugs.

Instantly there arises an issue. Nested iterators are now no longer implementable, sure they can be done however they won't work as intended. Not every usage will cause a crash but it is very common and either way there will be unintended consequences for it.

If one is not careful to read the documentation correctly, or appropriately understand what they are doing, or how their code could be used it is easy to fall into this trap. In fact, the base game code given for CSSE3200 makes this very mistake.

What can we do?

Now of course not all hope is lost, there are multiple ways to prevent this three of which are outlined below.

Just don't use iterators

This one is pretty self-explanatory, whilst iterators might be nice they aren't required (usually) so its simply smart to avoid all potential errors and just not use them. The easiest way is to use use an index and lookup for each entry.

An example of this is below, implemented in the EntityService class.

Note: That Entity.earlyUpdate() also uses an iterator, causing this nesting error, the code snippet is also provided below for completion.

Entity Class:

  public void earlyUpdate() {
    if (!enabled) {
      return;
    }
    for (Component component : createdComponents) {
      component.triggerEarlyUpdate();
    }
  }

Existing EntityService code: BAD!

  public void update() {
    for (Entity entity : entities) {
      entity.earlyUpdate();
      entity.update();
    }
  }

Updated EntityService code:

    for (int i = 0; i < entities.size; i++) {
      entities.get(i).earlyUpdate();
      entities.get(i).update();
    }

With this simple change to calling operations on entries in an array, this problem can be entirely avoided, and we no longer need to consider if our code will be used inside an iterator too.

Use something that supports iterators.

Another option is to simply use a different data type that supports nested iteration natively.

The most obvious of these is Java Util ArrayList as it provides nested iterators in a similar framework. Of course, whilst it is not a direct translation due to slight differences in their implementation and usage, most cases can be ported over directly, or another base data type can be used.

Once again an example of using a Java Util ArrayList instead of a Gdx Utils Array inside the EntityService is provided below.

Gdx Array:

  private final Array<Entity> entities = new Array<>(false, INITIAL_CAPACITY);

  public void update() {
    for (Entity entity : entities) {
      entity.earlyUpdate();
      entity.update();
    }
  }

Or better yet

  public void update() {
    for (int i = 0; i < entities.size; i++) {
      entities.get(i).earlyUpdate();
      entities.get(i).update();
    }
  }

 public void unregister(Entity entity) {
    entities.removeValue(entity, true);
  }

Java Util ArrayList:

  private final ArrayList<Entity> entities = new ArrayList<>(INITIAL_CAPACITY);

  public void update() {
    for (Entity entity : entities) {
      entity.earlyUpdate();
      entity.update();
    }
  }

Note: Using an iterator for the Gdx Array and Java ArrayList is identical

  public void update() {
    for (int i = 0; i < entities.size(); i++) {
      entities.get(i).earlyUpdate();
      entities.get(i).update();
    }
  }

 public void unregister(Entity entity) {
    entities.remove(entity);
  }

Whilst this is not always viable it is still a simple port over, or could entirely be avoided by never using the Gdx Array and instead using the ArrayList from the beginning (or other data types).

Just disable the iterator sharing

The final option is to just turn off this feature, and make it so that when you make an iterator, it is a new instance and does not share memory.
I must say this feature was hidden in the codebase (unless I missed it), however, it is a simple and easy solution to implement.

The collections class has a single boolean attribute that enables iterator allocation. The official class code is as below:

package com.badlogic.gdx.utils;

public class Collections {

	/** When true, {@link Iterable#iterator()} for {@link Array}, {@link ObjectMap}, and other collections will allocate a new
	 * iterator for each invocation. When false, the iterator is reused and nested use will throw an exception. Default is
	 * false. */
	public static boolean allocateIterators;

}

As such simply setting allocateIterators to true we can get new iterators on each call, and thus get our nested iterators functionality back and is probably the simplest solution as it only requires one line of code.

The Future

All of these solutions are viable to prevent this in the future so it is simply a matter of determining which approach one wishes to use.

I will say however that depending on which solution is used, it should be clearly documented for students to understand in the future to ensure this does not reoccur.

Regardless, this bug should definitely be fixed in the base game engine used for this course as it is just a disaster waiting to happen either by using the LibGDX array as intended, regardless of how silly it might be, using a different array-based data structure, or circumventing the feature using the allocateIterators.

If the approach taken is one of the first 2, it should be explicitly outlined in the provided course documentation about this feature because the likelihood of students reading the LibGDX documentation themselves is low. This is especially important if the Array is still used and its implementation is just fixed, as they potentially will not realise that this standard operation of most iterables is forbidden in LibGDX. Of course, circumventing this feature will prevent this issue entirely, with the trade-off of changing the default behaviour of LibGDX.