Incrementally processing large number of entitites in an entity-component system

Question

LibGDX/Ashley has a class IntervalIteratingSystem that allows you to process all entities in a particular family every X milliseconds. But if you have a lot of entities to process, it might be a bad idea to do all that at once. For example, if you want to process 10,000 entities once every 10 seconds, you might not actually want to wait 10 seconds, and then process all the entities -- you'd want to "spread it out" over many frames. Perhaps every 100ms you process 100 entities, cycling through them all.

To rephrase: I'd like to process a large number of entities but spread out across multiple frames, preferably:

1. providing a reasonable guarantee that all entities will processed at least once every X seconds,
2. enabling you to keep track of how much time has passed since that entity was last processed,
3. with a random entity order,
4. all entities are processed an equal number of times.

Here are my ideas so far...(some bad, some good)

1. Every time an entity is added to the Engine, add a Group1, Group2, or GroupN component (either randomly or sequentially), and then in my EntitySystem I cycle through the various families based on their Group#.
2. Every 10 seconds, add all 10,000 entities to a list, and then every 100ms, drain and process 100 from that list. (Memory-intensive, and might fall behind)
3. Every 100ms, iterate over all 10,000 entities, but skip 99% of them randomly (either using a PRNG or by checking their hashcode mod prime).
4. Maintain a list (a copy, really) of all relevant entities inside an EntitySystem using Engine#addEntityListener() and then process 1% of the list every 100ms by sequentially stepping through it, and wrapping around when reaching the end. (Uses LibGDX's unordered Array so removals are cheap).
5. Same as 4., but rely on Engine#getEntitiesFor and just let Ashley handle ordering and tracking entities instead of keeping a separate list.

At the moment, #1 and #5 seem most promising. #1 seems to meet all my requirements, but is a bit pervasive (creating and adding a bunch of components), #5 is less pervasive, but doesn't meet the requirements quite as well (#2 and #3 mostly).

Thoughts? Is there something better than these?

Answer 1

I ended up implementing #4 above (in Kotlin). Seems to work alright.

---

import com.badlogic.ashley.core.Engine
import com.badlogic.ashley.core.Entity
import com.badlogic.ashley.core.EntityListener
import com.badlogic.ashley.core.Family
import com.badlogic.ashley.systems.IntervalIteratingSystem
import com.badlogic.gdx.utils.Array as GdxArray

/**
 * Partition all applicable entities into [bucketCount] separate "buckets", and then process these incrementally over
 * the full timespan of [interval].
 *
 * How to determine what to set [bucketCount] to? Each bucket should probably not contain more than, oh, around 100
 * elements. So take your expected number of entities, divide by 100, and that's approximately how much buckets you
 * should have.
 *
 * Considerations:
 * 1. This implementation is somewhat memory intensive -- it scales linearly with the number of entities in the provided
 *    family.
 * 2. Deletions (i.e. removing entities from the engine) are moderately expensive -- it has to scan through an array of
 *    average size entities/[bucketCount] to find the entity before removing it.
 * 3. Entities are stored unordered.
 * 4. Every time entities are processed, *approximately* entities/[bucketCount] are processed each time. Only
 *    approximately, though.
 * 5. Each entity is guaranteed to be processed exactly once every [interval] seconds.
 * 6. A reasonable implementation of #hashcode() is assumed for the Entities.
 *
 * Ex. If you have 10,000 entities, an interval of 10 seconds, and a bucket count of 100, then every 100 ms 100 entities
 * will be processed. (One bucket every 10/100 ms, where each bucket contains roughly 100 entities).
 *
 * @param interval the interval (in seconds) during which all entities will have been processed once.
 * @param priority The priority to execute this system with (lower means higher priority). Default 0.
 * @param bucketCount Number of internal buckets to partition all entities into.
 */
abstract class IntervalIteratingSystemBuckets(family: Family, interval: Float, priority: Int, private val bucketCount: Int) :
        IntervalIteratingSystem(family, interval / bucketCount, priority) {
    private val buckets = Array<GdxArray<Entity>>(bucketCount, { GdxArray(false, 8) })
    private val entityListener = MyEntityListener()
    private var currentBucketIdx = 0

    override fun addedToEngine(engine: Engine) {
        super.addedToEngine(engine)
        engine.addEntityListener(family, entityListener)
    }

    override fun removedFromEngine(engine: Engine) {
        super.removedFromEngine(engine)
        engine.removeEntityListener(entityListener)
    }

    override fun updateInterval() {
        buckets[currentBucketIdx].forEach { processEntity(it) }

        incrementBucketCount()
    }

    private fun incrementBucketCount() {
        currentBucketIdx++
        if (currentBucketIdx >= buckets.size) {
            currentBucketIdx = 0
        }
    }

    private inner class MyEntityListener : EntityListener {
        override fun entityAdded(entity: Entity) {
            buckets[entity.bucketIdx].add(entity)
        }

        override fun entityRemoved(entity: Entity) {
            // Moderately expensive; this is why you should favor more buckets
            buckets[entity.bucketIdx].removeValue(entity, true)
        }

        private val Entity.bucketIdx: Int
            get() = hashCode() % bucketCount
    }
}

Answer 2

NOTE: This is not libgdx specific and is a more general answer.

You could have two variables attached to update (or any specific) components you wish to process: - frequency - phase

Frequency decides after how many frames this component should be processed. Example, if you have a frequency of 7, then the component gets updated every 7 frames.

Phase determines how the update should be interleaved. You need to set this value incrementally to every component created, and it determines how many items in a batch will get processed each frame.

E.g.: If you want to process 1000 entities every 50 frames, but need to limit processing to 100 entities at a time, you follow the following steps

• Initialize a phase variable to 0, this should be static/global (maybe part of you component builder class/system)
• Then, for each component c you create
  • c.frequency = 50
  • c.phase = phase
  • phase = (phase + 1) % 100 100 because you want to limit to 100 items max

With frequency and phase variables in place, you could implement a simple update system like so:

class UpdateSystem : System {

    let scheduler = FrequencyScheduler()

    override func update(_ dt: CGFloat) {
        scheduler.update(world, world.manager.updateables)
    }

}


class FrequencyScheduler {
    var frame:Int = 0

    func update(world:GameWorld, updateables: Array<UpdateComponent>) {

        frame += 1

        for updateable in updateables {

            if (frame + updateable.phase) % updateable.frequency == 0 {
                updateable.update(world)
            }
        }
    }
}

This approach can be extended to consider time intervals instead of frame intervals.

Answer 3

Gdx-ai has frequency based schedulers https://github.com/libgdx/gdx-ai/wiki/Scheduling