Have fun and help me to get to 1,000,000 downloads!

Flash flood fill implementation

Emanuele Feronato Actionscript 2, Flash, Game design, Tutorials

Do you know what is the flood fill algorithm?

From Wikipedia: Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the “bucket” fill tool of paint programs to determine which parts of a bitmap to fill with color, and in puzzle games such as Minesweeper, Puyo Puyo, Lumines, and Magical Drop for determining which pieces are cleared.

So now you know there is an algorithm to manage some issues in “click somewhere and…” games.

Let’s make it!

My version of the algorithm looks for all light grey tiles (two-dimensional array elements) which are connected to the starting light grey tile (the one we click) by a path of same tiles, and changes them to pink.

It’s a ricorsive algorithm acting this way: if the clicked tile is grey, then turn it into pink, then act as we clicked the tile at the top of the clicked tile, the one at the bottom, the one at the left and the one and the right. This is called 4-directions flood fill, because we extend the flooding to four directions (up, down, left, right).

You can also perform a 8-directions flood fill, extending the flooding to the original four directions plus the four diagonals

Look at this actionscript:

The 4-directions flood function goes from line 27 to line 37 and allows me to paint grey areas this way:

As you can see, you can paint only one “room” at time because the diagonal “walls” does not allow the four direction flood to paint everywhere.

Look at the 8-directions flood:

Now you can paint everywhere

What’s better? The one that fits your needs, of course?

What kind of game can we make out of that? I don’t know (lie! lie!), it’s up to you

Download the source code and start flooding

From null to full HTML5 cross platform game

I will take you by hand from the bare bones of JavaScript programming through the creation of a full cross platform HTML5 game, with detailed explainations and source code.

If you don't know where to start, then From null to full HTML5 cross platform game is the book for you.

Comments 20

  1. David

    interesting post
    i might use it
    when are you going to do the next part of the creation of a ragdoll with flash tutorial?

    nice tutorial though

  2. EagleVision

    Its very nice, but at first I didn’t know what it was… If you ask me, no Ideas. :)

    Yeah, thats a problem with me blogging, too. I forget about the old post that I was suppose to continue, but didn’t.

    I’ll probably need some encouragement on that. :)

  3. Mike

    It’s simple, but has to be optimized a lot. In 1st example if I click big center area, algorithm invokes “flood_fill” function 93 times. It’s way too much to fill up 23 tiles.

  4. Junxron

    OMG.. Last night I was thinking about how 2 do “snap to grid” kind of games.. And this morning i wake up i see this post.. LOL.. Thanks..

  5. Adam Owen

    Last year I was making a bomb game where I had to recursively check 4-way tiles to see if they themselves had bombs.

    I have to say, my method was extremely sloppy and this article would have saved me a lot of headache.

    Great article Emanuele, and an interesting topic!

  6. Adarsh Sinha

    Hello Emanuele Feronato, I have been following your blog for quite some time now, And i was wondering if you could make a tutorial for a small online game, more or less with a goal to show how to make a small, simple mmo/online game in flash.
    Thanks :)

  7. canberk

    it is reaally a perfect code. but i couldn’t decide whether recursion is used in that code segment. If someone could answer, i’ll be thankful…
    Thanks for sharing of that nice code…

  8. Pingback: Emanuele Feronato - italian geek and PROgrammer

  9. Pingback: Floodfill | ?????

  10. George Femic

    Never knew it was called the Flood algorithm, but makes sense now.
    I’ve used similar things countless times for games and just now found out what it’s called =P…

  11. Pingback: The basics behind Diamond Digger Saga: flood fill algorithm - Emanuele Feronato

  12. Ahmad

    that’s a great tutorial,
    i was wondering if u can make a simple tutorial to find the longest chain for a 2d tile matrix ?
    the chain had the sane color or type of tile
    i really tried too hard to this,but with no good solution.
    i had tried to work on the A* algorithm but i failed
    would u please show us how to do it


Leave a Reply

Your email address will not be published. Required fields are marked *