Flash flood fill implementation

June 6, 2008 • Actionscript 2, Flash, Game design, Tutorials by Emanuele Feronato • 17 Comments

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:

fill_map = new Array();
fill_map[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
fill_map[1] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[2] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[3] = [1, 0, 0, 1, 0, 0, 0, 0, 1];
fill_map[4] = [1, 1, 1, 0, 0, 0, 1, 1, 1];
fill_map[5] = [1, 0, 0, 0, 0, 1, 0, 0, 1];
fill_map[6] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[7] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
for (y=0; y<9; y++) {
	for (x=0; x<9; x++) {
		tile = _root.attachMovie("tile", "tile_"+(y+x*9), _root.getNextHighestDepth(), {_x:y*50, _y:x*50});
		tile.gotoAndStop(1+fill_map[x][y]);
	}
}
_root.attachMovie("cursor", "cursor", _root.getNextHighestDepth());
cursor.onEnterFrame = function() {
	this._x = 50*Math.floor(_root._xmouse/50);
	this._y = 50*Math.floor(_root._ymouse/50);
};
_root.onMouseDown = function() {
	pos_x = Math.floor(_root._xmouse/50);
	pos_y = Math.floor(_root._ymouse/50);
	flood_fill(pos_x, pos_y);
};
function flood_fill(x, y) {
	pos = x+y*9;
	if (fill_map[y][x] == 0) {
		fill_map[y][x] = 2;
		_root["tile_"+(x+y*9)].gotoAndStop(3);
		flood_fill(x+1,y);
		flood_fill(x-1,y);
		flood_fill(x,y+1);
		flood_fill(x,y-1);
	}
}

fill_map = new Array();

fill_map[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];

fill_map[1] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[2] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[3] = [1, 0, 0, 1, 0, 0, 0, 0, 1];

fill_map[4] = [1, 1, 1, 0, 0, 0, 1, 1, 1];

fill_map[5] = [1, 0, 0, 0, 0, 1, 0, 0, 1];

fill_map[6] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[7] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];

for (y=0; y<9; y++) {

for (x=0; x<9; x++) {

tile = _root.attachMovie("tile", "tile_"+(y+x*9), _root.getNextHighestDepth(), {_x:y*50, _y:x*50});

tile.gotoAndStop(1+fill_map[x][y]);

}

_root.attachMovie("cursor", "cursor", _root.getNextHighestDepth());

cursor.onEnterFrame = function() {

this._x = 50*Math.floor(_root._xmouse/50);

this._y = 50*Math.floor(_root._ymouse/50);

};

_root.onMouseDown = function() {

pos_x = Math.floor(_root._xmouse/50);

pos_y = Math.floor(_root._ymouse/50);

flood_fill(pos_x, pos_y);

};

function flood_fill(x, y) {

pos = x+y*9;

if (fill_map[y][x] == 0) {

fill_map[y][x] = 2;

_root["tile_"+(x+y*9)].gotoAndStop(3);

flood_fill(x+1,y);

flood_fill(x-1,y);

flood_fill(x,y+1);

flood_fill(x,y-1);

}

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:

fill_map = new Array();
fill_map[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
fill_map[1] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[2] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[3] = [1, 0, 0, 1, 0, 0, 0, 0, 1];
fill_map[4] = [1, 1, 1, 0, 0, 0, 1, 1, 1];
fill_map[5] = [1, 0, 0, 0, 0, 1, 0, 0, 1];
fill_map[6] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[7] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
fill_map[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
for (y=0; y<9; y++) {
	for (x=0; x<9; x++) {
		tile = _root.attachMovie("tile", "tile_"+(y+x*9), _root.getNextHighestDepth(), {_x:y*50, _y:x*50});
		tile.gotoAndStop(1+fill_map[x][y]);
	}
}
_root.attachMovie("cursor", "cursor", _root.getNextHighestDepth());
cursor.onEnterFrame = function() {
	this._x = 50*Math.floor(_root._xmouse/50);
	this._y = 50*Math.floor(_root._ymouse/50);
};
_root.onMouseDown = function() {
	pos_x = Math.floor(_root._xmouse/50);
	pos_y = Math.floor(_root._ymouse/50);
	flood_fill(pos_x, pos_y);
};
function flood_fill(x, y) {
	pos = x+y*9;
	if (fill_map[y][x] == 0) {
		fill_map[y][x] = 2;
		_root["tile_"+(x+y*9)].gotoAndStop(3);
		flood_fill(x+1,y);
		flood_fill(x+1,y+1);
		flood_fill(x+1,y-1);
		flood_fill(x-1,y);
		flood_fill(x-1,y+1);
		flood_fill(x-1,y-1);
		flood_fill(x,y+1);
		flood_fill(x,y-1);
	}
}

fill_map = new Array();

fill_map[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];

fill_map[1] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[2] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[3] = [1, 0, 0, 1, 0, 0, 0, 0, 1];

fill_map[4] = [1, 1, 1, 0, 0, 0, 1, 1, 1];

fill_map[5] = [1, 0, 0, 0, 0, 1, 0, 0, 1];

fill_map[6] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[7] = [1, 0, 0, 0, 1, 0, 0, 0, 1];

fill_map[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];

for (y=0; y<9; y++) {

for (x=0; x<9; x++) {

tile = _root.attachMovie("tile", "tile_"+(y+x*9), _root.getNextHighestDepth(), {_x:y*50, _y:x*50});

tile.gotoAndStop(1+fill_map[x][y]);

}

_root.attachMovie("cursor", "cursor", _root.getNextHighestDepth());

cursor.onEnterFrame = function() {

this._x = 50*Math.floor(_root._xmouse/50);

this._y = 50*Math.floor(_root._ymouse/50);

};

_root.onMouseDown = function() {

pos_x = Math.floor(_root._xmouse/50);

pos_y = Math.floor(_root._ymouse/50);

flood_fill(pos_x, pos_y);

};

function flood_fill(x, y) {

pos = x+y*9;

if (fill_map[y][x] == 0) {

fill_map[y][x] = 2;

_root["tile_"+(x+y*9)].gotoAndStop(3);

flood_fill(x+1,y);

flood_fill(x+1,y+1);

flood_fill(x+1,y-1);

flood_fill(x-1,y);

flood_fill(x-1,y+1);

flood_fill(x-1,y-1);

flood_fill(x,y+1);

flood_fill(x,y-1);

}

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

Rate this post: 1 Star

(6 votes, average: 4.17 out of 5)

Loading ...

Flash Templates provided by Template Monster are pre-made web design products developed using Flash technology.
They can be easily customized to meet the unique requirements of your project.

Be my fan on Facebook and follow me on Twitter! Exclusive content for my Facebook fans and Twitter followers

This post has 17 comments

David

on June 6, 2008 at 6:50 pm

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
EagleVision

on June 6, 2008 at 7:49 pm

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. :)
Mike

on June 6, 2008 at 7:56 pm

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.
Jack Hopkins

on June 6, 2008 at 10:51 pm

Awesome!
This is quite advanced I feel,
I think I can use this!

:D
Cory Mathews

on June 7, 2008 at 12:31 am

Excellent article. I see many uses for this.
Junxron

on June 7, 2008 at 4:01 am

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..
Chuck Arellano

on June 7, 2008 at 8:06 pm

Hi Emanuele,

Another game that uses flood fill is JezzBall! I wrote a version of the 4 directions flood fill you mentioned above with my newest game, Trappit ( http://www.scriptedfun.com/games/trappit/ ), but I implemented it non-recursively.

Great tutorial as always! Thank you! :D
Adam Owen

on June 9, 2008 at 2:27 pm

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!
Adarsh Sinha

on June 10, 2008 at 4:10 pm

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 :)
canberk

on December 5, 2008 at 12:39 pm

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…
koby

on July 2, 2009 at 2:02 pm

I made it on AS3 today.
this is a great tut.
Frederik

on January 5, 2010 at 5:33 pm

Kudos for a nice and intuitive implementation. How would you handle flash’s recursion threshold (max 256 recursions) for grids of larger sizes?
sydd

on February 17, 2010 at 9:57 pm

@koby AS3 has a build-on flood fill, look for BitmapData.floodFill()
Emanuele Feronato - italian geek and PROgrammer

on May 7, 2010 at 1:34 pm

[...] Why you must be able to make it: You will get familiar with arrays with multiple values, and there is an interesting implementation of the flood fill algorithm [...]
Floodfill | ?????

on August 7, 2011 at 4:31 pm

[...] Flash flood fill implementation, by Emanuele Feronato. [...]
nevkatz

on February 27, 2012 at 3:26 pm

Great job! I just migrated this to AS3 using the Event.ENTER_FRAME listener and addChild() method. It worked perfectly!
Tax

on November 23, 2012 at 11:36 am

Hi Emanuele,

Nice tutorial, tried converting this to AS3 but i’m stuck in a infinite loop (stack overflow). I wonder why T_T

Tax.

italian geek and PROgrammer

This post has 17 comments

David

Mike

Jack Hopkins

koby

sydd

Tax