feat: Use a Free List Strategy on BatchItem indexes within SpriteBatch and return index from .add()

[gnarhard]

Description

This PR adds functionality to make it easier to manage BatchItems within a SpriteBatch. .add() and .addTransform() now return the generated index for tracking the BatchItem. This now uses a Free List Strategy to avoid concurrent modifications and allow manipulations on the BatchItems from different components in the same frame.

Originally, this PR added an ID for BatchItem management, but that was replaced with index management using the Free List Strategy.

Checklist

• [x] I have followed the Contributor Guide when preparing my PR.
• [x] I have updated/added tests for ALL new/updated/fixed functionality.
• [x] I have updated/added relevant documentation in docs and added dartdoc comments with ///.
• [x] I have updated/added relevant examples in examples or docs.

Breaking Change?

• [ ] Yes, this PR is a breaking change.
• [x] No, this PR is not a breaking change.

Related Issues

[spydon]

Can you explain your use-case a bit further? I'm not sure I understand why this is needed to do animations based on sprite batches, and whether that is even anything that the sprite batch should be aware of. It seems to me like one would want all the sprites related to an animation within the atlas, not replace the entries.

[gnarhard]

In my use case, I often spawn hundreds of orbs that contain health. Sprite batching significantly improves performance here. Each orb has four states: materialize, idle, dissipate, and collect. • Materialize plays once and transitions to idle, which loops 4 times. • Then it switches to dissipate, unless a collision occurs. • On collision, the current animation is interrupted and replaced with collect.

All animations are texture-packed into a single image. I’m generating BatchItems dynamically for the materialize animation, then replacing and eventually removing them.

Currently, SpriteBatch management is index-based. While I could store and track indices in my orb model, it’s unreliable—especially when animations change rapidly. More importantly, there’s no built-in way to remove a BatchItem by index, which is what inspired this PR.

You wouldn’t manage database indexes outside the database—likewise, managing BatchItems by a unique ID makes CRUD operations more reliable and intuitive. This approach ensures I always target the correct item, even as orb states change.

Regarding your comment about animation sprites needing to be within the atlas: to use drawAtlas() efficiently for hundreds of animated orbs, I need to create and replace BatchItems on every frame. Unless there’s a better methodology I’ve missed, that’s currently the only way to animate with sprite batching.

[gnarhard]

@spydon A problem I'm running into currently with this implementation is race conditions if you're mutating the index from separate components. I've implemented a Free List Strategy to account for this and it's working perfectly in my game. Here's an overview of my changes:

Error safety improvements

• Fixes race conditions caused by mutating indexes from multiple different sources
  • By not shifting indices or compacting arrays during mutation, render/update logic stays consistent.
  • Prevents bugs caused by index mismatches or invalid lookups during concurrent access within a single frame.
• Enables Safe Deferred Mutation
  • Works perfectly with a “schedule and flush” mutation model (e.g. deferred removeById()), which avoids unsafe access during the render loop.

BONUS! Performance improvements

• No shifting of indices
  • removeAt() is O(1), no map updates
• Reuse of index slots
  • Reduces memory churn, avoids growth
• Sparse batch safety
  • Works even when many items are removed
• Fast add and remove
  • Constant time for typical operations

[spydon]

@gnarhard can you have a look at why the tests are failing? I updated the PR to align with Flutter 3.35, so remember to pull first.

[gnarhard]

@spydon I need your help on fixing these tests. These tests were passing before the move to Flutter 3.35 and other changes to main. I'm wondering if the precision issues are related to Matrix4 returning a Float32List instead of a Float64List. I combed through the file and compared it to main, but I can't figure out why the goldens are different and I don't see a reason for that to happen from my updates.

[spydon]

@spydon I need your help on fixing these tests. These tests were passing before the move to Flutter 3.35 and other changes to main. I'm wondering if the precision issues are related to Matrix4 returning a Float32List instead of a Float64List. I combed through the file and compared it to main, but I can't figure out why the goldens are different and I don't see a reason for that to happen from my updates.

I squashed all the commits in this PR so that it can easily cherry-picked into an older version of Flame and try the tests there. I don't think this is related to any precision issues, because as you can see in the image diffs that I linked, some tiles are just completely gone.

[spydon]

@gnarhard I cherry-picked this PR onto Flame v1.29.0 and used Flutter 3.27.1 to run the tests, and the same goldens still fail, so I'm pretty certain the bug is within this PR and not external.

[gnarhard]

Okay, thanks for doing that. I'll look into it again.

[gnarhard]

@spydon I’ve taken several 1-2 hour bite-sized chunks of time trying to figure out why those flame_tiled tests are failing and I’m still puzzled. Now that I’m home from tour I have a bit more resources and time to look into this. Just wanted to give you an update.