El algoritmo de relleno por difusión, también llamado algoritmo de relleno, o -directamente del inglés- floodfill determina el área formada por elementos contiguos en una matriz multidimensional. Se usa en la herramienta bote de pintura de programas de dibujo para determinar qué partes de un mapa de bits se van a rellenar de un color [o una textura], y en juegos como el Buscaminas, Puyo Puyo, Lumines y Magical Drop para determinar qué piezas pueden retirarse o seleccionarse.
Esta versión del algoritmo busca todos los recuadros de color gris claro, que sean adyacentes al recuadro donde se hizo clic, el cual es otro recuadro gris claro, los recuadros negros representarán a las paredes, es decir no las puede atravezar ni cambiar de color; toda esta información será almacenada en una matriz bidimensional.
A continuación se muestra un algoritmo recursivo que funciona de la siguiente manera: si el recuadro donde se hizo clic es gris, este se cambiará a azul, luego será como si se hubiera hecho clic en el recuadro superior y en el recuadro inferior, cambiando de color ambos recuadros, sucederá lo mismo con los recuadros que se encuentren a la derecha e izquierda del recuadro pulsado. Este es el llamado algoritmo de relleno de 4 direcciones, ya que rellena sólo en 4 direcciones: arriba, abajo, izquierda y derecha.
El código es el siguiente:
// Se importa las clases necesarias para usar más adelante
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.events.Event;
// Variable que contiene el mapa del escenario a crear
var tileMap:Array = new Array();
tileMap[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
tileMap[1] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[2] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[3] = [1, 0, 0, 1, 0, 0, 0, 0, 1];
tileMap[4] = [1, 1, 1, 0, 0, 0, 1, 1, 1];
tileMap[5] = [1, 0, 0, 0, 0, 1, 0, 0, 1];
tileMap[6] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[7] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
// Creación del mapa
for(var i:int = 0; i < 9; i++)
{
for(var j:int = 0; j < 9; j++)
{
var tile:Tile = new Tile();
tile.name = "tile" + (i + j * 9);
tile.x = i * 50;
tile.y = j * 50;
tile.gotoAndStop(1 + tileMap[j][i]);
tile.addEventListener(MouseEvent.MOUSE_DOWN, mMouseDownHandler);
addChild(tile);
}
}
// Se agrega el recuadro que sigue al cursor para indicar quien será afectado
var cursor:Sprite = Sprite(addChild(new Cursor()));
cursor.name = "cursor";
// Listener usado para actualizar el indicador [cursor]
addEventListener(Event.ENTER_FRAME, mEnterFrameHandler);
// Función asociada al evento anterior que se encarga de mover el recuadro rojo
function mEnterFrameHandler(e:Event):void
{
cursor.x = 50 * Math.floor(mouseX / 50);
cursor.y = 50 * Math.floor(mouseY / 50);
}
// Función que indica a quien se hizo clic e invoca a la función que se encarga de realizar el relleno
function mMouseDownHandler(e:MouseEvent):void
{
var posX:int = Math.floor(mouseX / 50);
var posY:int = Math.floor(mouseY / 50);
mFloodFill(posX, posY);
}
// Función recursiva encargada de realizar el relleno
function mFloodFill(posX:int, posY:int):void
{
var pos:int = posX + posY * 9;
if(tileMap[posY][posX] == 0)
{
tileMap[posY][posX] = 2;
var actualTile:Tile = Tile(this.getChildByName("tile" + (posX + posY * 9)));
actualTile.gotoAndStop(3);
mFloodFill(posX + 1, posY);
mFloodFill(posX - 1, posY);
mFloodFill(posX, posY + 1);
mFloodFill(posX, posY - 1);
}
}
Y el resultado es el que se muestra a continuación:
Como se ve en el ejemplo, solo se puede pintar un "cuarto" a la vez, debido a que los muros [recuadros negros], bloquean la propagación del relleno para poder pintarlo todo. Ahora, también se puede tomar el algoritmo anterior y modificarlo para realizar un relleno en 8 direcciones, agregando a las cuatro direcciones, las cuatro diagonales.
El código es el siguiente:
// Se importa las clases necesarias para usar más adelante
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.events.Event;
// Variable que contiene el mapa del escenario a crear
var tileMap:Array = new Array();
tileMap[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
tileMap[1] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[2] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[3] = [1, 0, 0, 1, 0, 0, 0, 0, 1];
tileMap[4] = [1, 1, 1, 0, 0, 0, 1, 1, 1];
tileMap[5] = [1, 0, 0, 0, 0, 1, 0, 0, 1];
tileMap[6] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[7] = [1, 0, 0, 0, 1, 0, 0, 0, 1];
tileMap[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
// Creación del mapa
for(var i:int = 0; i < 9; i++)
{
for(var j:int = 0; j < 9; j++)
{
var tile:Tile = new Tile();
tile.name = "tile" + (i + j * 9);
tile.x = i * 50;
tile.y = j * 50;
tile.gotoAndStop(1 + tileMap[j][i]);
tile.addEventListener(MouseEvent.MOUSE_DOWN, mMouseDownHandler);
addChild(tile);
}
}
// Se agrega el recuadro que sigue al cursor para indicar quien será afectado
var cursor:Sprite = Sprite(addChild(new Cursor()));
cursor.name = "cursor";
// Listener usado para actualizar el indicador [cursor]
addEventListener(Event.ENTER_FRAME, mEnterFrameHandler);
// Función asociada al evento anterior que se encarga de mover el recuadro rojo
function mEnterFrameHandler(e:Event):void
{
cursor.x = 50 * Math.floor(mouseX / 50);
cursor.y = 50 * Math.floor(mouseY / 50);
}
// Función que indica a quien se hizo clic e invoca a la función que se encarga de realizar el relleno
function mMouseDownHandler(e:MouseEvent):void
{
var posX:int = Math.floor(mouseX / 50);
var posY:int = Math.floor(mouseY / 50);
mFloodFill(posX, posY);
}
// Función recursiva encargada de realizar el relleno
function mFloodFill(posX:int, posY:int):void
{
var pos:int = posX + posY * 9;
if(tileMap[posY][posX] == 0)
{
tileMap[posY][posX] = 2;
var actualTile:Tile = Tile(this.getChildByName("tile" + (posX + posY * 9)));
actualTile.gotoAndStop(3);
mFloodFill(posX + 1, posY);
mFloodFill(posX + 1, posY + 1);
mFloodFill(posX + 1, posY - 1);
mFloodFill(posX - 1, posY);
mFloodFill(posX - 1, posY + 1);
mFloodFill(posX - 1, posY - 1);
mFloodFill(posX, posY + 1);
mFloodFill(posX, posY - 1);
}
}
Y el resultado es el que se muestra a continuación:
En el último ejemplo como pueden ver se puede pintar todo, usar el algoritmo de 4 direcciones o de 8, solo dependerá de las necesidades de cada caso en particular.
Descargar archivos.
Contraseña: http://qliksec.blogspot.com
Comentarios
Publicar un comentario