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

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?

• One option would be to add an IsDirty boolean property to the objects. Run through and "clean" the objects as you've processed them. Once the list is empty, mark them all dirty and cycle again. The benefit I see in this is that your processing entity could take n per cycle, process them and mark them as clean without having to track the order they are in the list. You could also set a priority and a max time value. Higher priority objects are processed first (can be ordered anywhere in the list), and after your max time, all objects are set dirty again in case the timing is off. – Jesse Williams Sep 21 '16 at 15:59
• Possibly, if max time is hit, all dirty objects increase in priority before being marked as (or really left as) dirty to ensure they are hit the next time around. – Jesse Williams Sep 21 '16 at 15:59
• Hmm, only problem is presumably you'd want to pick up where you left off on the previous cycle, right? But what if entities were added or removed during that time? – Max Sep 22 '16 at 4:39
• Using the Gdx-ai extention you can do this quite easily in a native-gdx way. I'll se if I have time to answer this later otherwise just look up Gdx AI for yourself. – Charanor Apr 25 '17 at 15:59
• I think all those approaches are reasonable, but your specific scenario will determine which make more sense- that is, will entities be constantly added and removed, if there's few enough entities should all of them be processed each frame, etc. The specifics of your scenario will really affect the algorithm choice. – Danny Yaroslavski Jun 2 '17 at 16:34

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

import com.badlogic.ashley.core.Engine

/**
* 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 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 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
}
}


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.

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