Destroying bullets in pool creates rendering order artifacts

[james7132]

Due to the way DanmakuPool and DanmakuRenderer interact, whenever a bullet is destroyed, the rendering order of the most recently fired bullet is altered.

The DanmakuPool is implemented as a class of parallel arrays and a active count. A bullet is identified by it's index along these arrays. If the index is less than the active counter, the bullet is active. Spawning a new bullet simply involves incrementing the active counter. Destroying a bullet involves and swapping the values of the latest spawned bullet with the destroyed bullet then decrementing the active counter. This is effective at creating and destroying bullets as these actions does not allocate or deallocate any memory, nor does it create objects.

The rendering system pulls batches of X (currently 4096) colors and transforms for bullets to render. For performance reasons, this is done sequentially via memcpy. This means that the order of bullets within the pool is also the render order of those bullets. Newer bullets are rendered after older bullets, or at least it should be that way: the bullets swapped by the destruction of other bullets interrupt this ordering, causing random bullets to start appearing out of order as others are destroyed.

Resolution options:

• Sort by spawn order - re-sort the pool by spawn order if and only if bullets were destroyed in a given
  update. Assuming the pool remains almost sorted frame to frame, an insertion sort pass would be an
  effective O(n) average case pass through the pool.

[EricMay256]

If large batches of bullets are spawned at once with the same lifetime, they'll likely all be despawned at once. This might possibly be a difficult edge case for the insertion sort pass normally but if it can be predicted in advance maybe it can have an easier way of dealing with that problem.