![]() |
![]() |
Internal
External
Affiliates
- CSForge
- Free Information Society
- Neil Bittner [Dot] Com
- Esoteric Press
- Paul Harvey The Game
- Inman's Total Electronics
- Become an Affilate...
Quick Links
Search Google
Back to Articles
Flood-Fill Algorithm in Flash ActionScript
The flood-fill algorithm is used to determine the area connected to a given node in a multi-dimensional array. This algorithm is used in the game Clicken Gold to determine which is used to find out what blocks should be cleared. It is also used in paint programs for filling in contiguous areas.
Pseudo Code
traverse(node){
if(node.color == clickedColor){
node.color = newColor;
traverse(grid[node.row-1][col]);
traverse(grid[node.row+1][col]);
traverse(grid[node.row][col-1]);
traverse(grid[node.row][col+1]);
}
}
if(node.color == clickedColor){
node.color = newColor;
traverse(grid[node.row-1][col]);
traverse(grid[node.row+1][col]);
traverse(grid[node.row][col-1]);
traverse(grid[node.row][col+1]);
}
}
Example
To find the entire area you check the all of sides of the Node in no particular order. Then you continue checking recursively from that point. In the example on the left when Node 1 is checked the Nodes around it will be checked before continuing to Node 2.
Implementation
I implemented the Flood-Fill algorithm in Flash ActionScript. I created a class called Node that handles the drawing and coloring of the Node. I implemented the Algorithm with animation so you can see how the algorithm executes.
Click on any of the colored areas to fill them with red using the Flood-Fill algorithm.
Code
The Node Class
class Node{
// The color of the node
private var nodeColor:Number;
// The square node movie clip
private var mc:MovieClip;
// The row and column number
private var row:Number;
private var col:Number;
// Visibility of the circle
private var circleVisible:Boolean = false;
/* The constructor creates the main movie clip */
function Node(param_color:Number,param_col:Number,param_row:Number){
this.nodeColor = param_color;
var depth = _root.getNextHighestDepth();
this.row = param_row;
this.col = param_col;
// Create the new movie clip
mc = _root.createEmptyMovieClip("node"+depth,depth);
// Set the location
mc._x = 40+(param_col*20);
mc._y = 40+(param_row*20);
// Set up both of the movie clips
setupMovieClips();
setupListener();
}
/* Set the visibility of the circle movie clip */
function setCircleVisible(param_vis:Boolean):Void{
circleVisible = param_vis;
mc.circle_mc._visible = param_vis;
}
/* Return this Nodes row number */
function getRow():Number{
return row;
}
/* Return this Nodes column number */
function getCol():Number{
return col;
}
/* Returns the color of this Node */
function getColor():Number{
return nodeColor;
}
/* Set the color of this Node. The movie clips
* will be redrawn. */
function setColor(param_color:Number):Void{
// Save the position
var oldX = mc._x;
var oldY = mc._y;
// Remove old clip
_root.removeMovieClip(mc);
this.nodeColor = param_color;
var depth = _root.getNextHighestDepth();
// Create new movie clip
mc = _root.createEmptyMovieClip("node"+depth,depth);
mc._x = oldX;
mc._y = oldY;
// Set up movie clips and listeners
setupMovieClips();
setupListener();
}
/* Set up the mouse listener on the main movie clip */
private function setupListener():Void{
mc.onRelease = function(){
_root.ff(_xmouse,_ymouse);
};
mc.useHandCursor = false;
}
/* This function sets up all of the movie clips */
private function setupMovieClips():Void{
mc.beginFill(this.nodeColor);
mc.moveTo(0, 0);
mc.lineTo(0, 20);
mc.lineTo(20, 20);
mc.lineTo(20, 0);
mc.lineTo(0, 0);
mc.endFill();
// Create the circle movie clip inside the main clip
mc.createEmptyMovieClip("circle_mc", 1);
mc.circle_mc.beginFill(0x000000);
mc.circle_mc.moveTo(5, 10);
mc.circle_mc.curveTo(9,9,10,5);
mc.circle_mc.curveTo(11,9,15,10);
mc.circle_mc.curveTo(11,11,10,15);
mc.circle_mc.curveTo(9,11,5,10);
mc.circle_mc.endFill();
// Set the visibility
mc.circle_mc._visible = circleVisible;
}
}
The Algorithm
// The color of the node
private var nodeColor:Number;
// The square node movie clip
private var mc:MovieClip;
// The row and column number
private var row:Number;
private var col:Number;
// Visibility of the circle
private var circleVisible:Boolean = false;
/* The constructor creates the main movie clip */
function Node(param_color:Number,param_col:Number,param_row:Number){
this.nodeColor = param_color;
var depth = _root.getNextHighestDepth();
this.row = param_row;
this.col = param_col;
// Create the new movie clip
mc = _root.createEmptyMovieClip("node"+depth,depth);
// Set the location
mc._x = 40+(param_col*20);
mc._y = 40+(param_row*20);
// Set up both of the movie clips
setupMovieClips();
setupListener();
}
/* Set the visibility of the circle movie clip */
function setCircleVisible(param_vis:Boolean):Void{
circleVisible = param_vis;
mc.circle_mc._visible = param_vis;
}
/* Return this Nodes row number */
function getRow():Number{
return row;
}
/* Return this Nodes column number */
function getCol():Number{
return col;
}
/* Returns the color of this Node */
function getColor():Number{
return nodeColor;
}
/* Set the color of this Node. The movie clips
* will be redrawn. */
function setColor(param_color:Number):Void{
// Save the position
var oldX = mc._x;
var oldY = mc._y;
// Remove old clip
_root.removeMovieClip(mc);
this.nodeColor = param_color;
var depth = _root.getNextHighestDepth();
// Create new movie clip
mc = _root.createEmptyMovieClip("node"+depth,depth);
mc._x = oldX;
mc._y = oldY;
// Set up movie clips and listeners
setupMovieClips();
setupListener();
}
/* Set up the mouse listener on the main movie clip */
private function setupListener():Void{
mc.onRelease = function(){
_root.ff(_xmouse,_ymouse);
};
mc.useHandCursor = false;
}
/* This function sets up all of the movie clips */
private function setupMovieClips():Void{
mc.beginFill(this.nodeColor);
mc.moveTo(0, 0);
mc.lineTo(0, 20);
mc.lineTo(20, 20);
mc.lineTo(20, 0);
mc.lineTo(0, 0);
mc.endFill();
// Create the circle movie clip inside the main clip
mc.createEmptyMovieClip("circle_mc", 1);
mc.circle_mc.beginFill(0x000000);
mc.circle_mc.moveTo(5, 10);
mc.circle_mc.curveTo(9,9,10,5);
mc.circle_mc.curveTo(11,9,15,10);
mc.circle_mc.curveTo(11,11,10,15);
mc.circle_mc.curveTo(9,11,5,10);
mc.circle_mc.endFill();
// Set the visibility
mc.circle_mc._visible = circleVisible;
}
}
function traverse(param_node:Node){
if(param_node != undefined){
if(param_node.getColor() == _root.clickedColor){
param_node.setColor(0xFF0000);
var row = param_node.getRow();
var col = param_node.getCol();
traverse(_root["myNode_"+(row-1)+"_"+(col)]);
traverse(_root["myNode_"+(row+1)+"_"+(col)]);
traverse(_root["myNode_"+(row)+"_"+(col-1)]);
traverse(_root["myNode_"+(row)+"_"+(col+1)]);
}
}
updateAfterEvent();
}
Download the Flood-Fill Algorithm Flash Sourceif(param_node != undefined){
if(param_node.getColor() == _root.clickedColor){
param_node.setColor(0xFF0000);
var row = param_node.getRow();
var col = param_node.getCol();
traverse(_root["myNode_"+(row-1)+"_"+(col)]);
traverse(_root["myNode_"+(row+1)+"_"+(col)]);
traverse(_root["myNode_"+(row)+"_"+(col-1)]);
traverse(_root["myNode_"+(row)+"_"+(col+1)]);
}
}
updateAfterEvent();
}


To find the entire area you check the all of sides of the Node in no
particular order. Then you continue checking recursively from that point.
In the example on the left when Node 1 is checked the Nodes around it
will be checked before continuing to Node 2.
123456
Posted on 04-10-2007 7:24am
great