#ggj12

How cool is it that our country has 2 sites this year? The two lovely sites were UP ITTC & DLSU CSB. I signed up for UP ITTC of course, since I love that location, but there were more participants from CSB. Mostly I think they were CSB students.

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.

Dynamic Flood Fill

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.

I’ll put my Global Game Jam-related musings under the Read More cut since it is long and it’s about time I wrote about this.

Wow. This game looks absolutely beautiful and I wish I weren't at work right now so that I could play it. It's available for both Mac and PC.

I have work Tumblr. I have lots of things to do. Why must you have so many interesting things all the time?! I can sit here and reblog shit all fucking day.

Anyway... I didn't get to liveblog the GGJ. Turns out I was too busy trying to be a productive noob game artist lol. I totally sucked but IT WAS SO MUCH FUN.

Maybe I'll post photos here soon. Because I can. And because this blog is like a big random blob of everything. I'll be posting my "art" here soon too. (You didn't see it, but the word 'art' came with air-quotes ala-Castiel.) I do this thing where I exercise my fingers by drawing at least one thing everyday. I have to be even just partially satisfied with whatever it is too so unfortunately I can't post stick people. (Awww.)

So 2012 is Code Year right? So yeah, I'm going to study Java, C# & more AS3. I'm not going to take up 3D ATM since the available facilities are not optimal for such hardware-intensive activities. I'll get to that when I get an upgrade when I get to save enough moohlah.

It was even featured by http://www.athinkingape.com/ for it's awesomeness! Please excuse all the bugs and lack of explanations, we were all pretty darn tired by the end of it :I