Mushroom 11 - Dynamic Flood Fill
Mushroom 11 consists of some CPU intensive calculations that significantly drag down performance on mobile devices. One of the the most intensive parts is determining which organism cells should be detached to make a separate instance, while the organism is going through constant change of growth and destruction.
Here's a demo of my new Dynamic Flood Fill algorithm, slowed down and visualized. See full explanation below.
The original approach was to make a complete Flood Fill every few frames after player has destroyed parts of the organism. Even when an optimized approach was used (horizontal loop, vertical recurse), it still yielded some noticeable FPS drops on mobile devices.
The above demo uses a dynamic version of the flood fill, which differ from the original in two major aspects - it triggers the flood fill in a few separate locations (and not necessarily in sync), and it rate-limits the flood fill speed.
Since each location starts a new flood-fill group and the spread is limited to a certain cells-per-frame speed, smaller areas finish faster and get detached immediately. This works perfectly for Mushroom 11 when the smaller batches need to separate fast or it will look like it's hanging in mid-air.
Another advantage of DFF is that since all groups are autonomous, if one batch get detached, the other batches continue normally. This means that many detachments can happen simultaneously in different parts of the organism.
The result of this new algorithm (tested on my iPad1) is instead of 50fps with spikes of down to 20fps, the game runs smoothly on 45-50fps. Here is a basic overview of the algorithm.
When a cell is destroyed, all its cell neighbors (cell-up, cell-left, etc) are triggered as flood-fill origins.
Every origin starts a completely separate fill-group and holds a list of all previously filled cells, and a list (stack) of future cells to fill. It also holds the fill-group neighbors (see below).
Flood-Fill step: Every frame runs a loop of flood-fill steps per each of the fill-groups, in each of the different organisms. A flood-fill step takes one cell from future-list, fills it (and updates filled-list), and adds all its empty cell-neighbors to future-list for the next iteration.
Grouping: If a fill-step leads a cell to a member of another fill-group (touching groups), then: a. if the other fill-group is empty, delete it and continue normally. b. if the other fill-group is not empty, mark the two fill-groups as neighbors.
Detach: If a future-list is exhausted (flood-fill complete for that fill-group), check all if all neighbors are finished (recursively, we need all connected groups). If yes, we have a complete list (or lists) of all painted cells. If that list is smaller than the total number of cells in this organism, then detach these cells to form a new organism instance.
Destroy: if a cell is destroyed, we check if it's already filled. If not, then we don't care, since the fill will never hit it anyway. If it is already filled, we need to invalidate the entire fill-group and all its neighbor fill-groups. And then trigger the cell-neighbors as completely new flood-fill origins.
Growth: when a new cell grows on the organism, we check if it is a neighbor of any fill-group. If so, that cell is placed in the future cells list of that group. Otherwise, the fill algorithm will catch up to it later.
That's it, more or less.
Hope this has been helpful or at least interesting! Let me know if you have any questions, suggestions or improvements.
Check back soon for more updates.
Thanks,
-- Itay