maze generation and solution algorithm (complete)
press generate button to generate a random maze.
press solve button to solve the maze.
enter number of columns/rows to the input box. The value must be between 5 and 100 (both inclusive).
the generation algorithm is randomized depth first search.
the solution algorithm is breadth first search.
/**
* Copyright cemevin ( http://wonderfl.net/user/cemevin )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/376A
*/
package {
import flash.text.TextFormatAlign;
import flash.text.TextFieldType;
import flash.text.engine.TextLine;
import flash.text.TextRun;
import flash.text.TextFormat;
import flash.display.AVM1Movie;
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.display.Sprite;
public class FlashTest extends Sprite {
private var grid:Vector.<Object> = new Vector.<Object>();
private var COLS:int = 20; //column count
private var ROWS:int = 20; //row count
private var GSIZE:int = 15; //grid size in terms of pixels
private var btn:Sprite = new Sprite(); //generate button
private var btn2:Sprite = new Sprite(); //solve button
private var cl:TextField = new TextField();
private var colsTextField:TextField = new TextField();
public function FlashTest() {
//the button
drawButtons();
drawInputFields();
//initialize the grid and draw it on the screen
initGrid();
drawGrids();
}
private function drawInputFields():void{
//columns
cl.x = 0;
cl.y = btn.y + 50;
cl.text = "COLS/ROWS:";
cl.setTextFormat(new TextFormat("Comic Sans MS", 16, 0));
cl.width = 120;
cl.height = 33;
stage.addChild(cl);
colsTextField.text = "10";
colsTextField.type = "input";
colsTextField.width = 40;
colsTextField.height = 33;
colsTextField.setTextFormat(new TextFormat("Comic Sans MS", 16, 0));
colsTextField.border = true;
colsTextField.x = 120;
colsTextField.y = btn.y + 50;
stage.addChild(colsTextField);
}
private function drawButtons():void{
//generate a maze button
var tf:TextField = new TextField();
tf.text = "GENERATE A MAZE";
tf.setTextFormat(new TextFormat("Comic Sans MS", 16, 0xffffff,null,null,null,null,null,TextFormatAlign.CENTER));
tf.width = 170;
tf.selectable = false;
btn.addEventListener(MouseEvent.CLICK,function():void{
if(mouseX>=btn.x && mouseX<=(btn.x+btn.width) && mouseY>=btn.y && mouseY<=(btn.y+btn.height)){
//parse col and row size
try{
COLS = int(colsTextField.text);
}
catch(e:*){
COLS = 10;
ROWS = 10;
colsTextField.text = "10";
GSIZE = 30;
}
COLS = Math.min(100,Math.max(5,COLS));
ROWS = COLS;
GSIZE = 300/ROWS;
colsTextField.text = COLS+"";
colsTextField.setTextFormat(new TextFormat("Comic Sans MS", 16, 0));
//hide the col row label and input field
cl.visible = false;
colsTextField.visible = false;
initGrid();
generateMaze();
drawGrids();
drawMaze();
btn2.visible = true;
}
});
addChild(btn);
btn.x = 0;
btn.y = GSIZE * ROWS + 20;
btn.graphics.beginFill(0x0000ff);
btn.graphics.drawRect(0,0,170,33);
btn.graphics.endFill();
btn.addChild(tf);
//solve the maze button
tf= new TextField();
tf.text = "SOLVE THE MAZE";
tf.setTextFormat(new TextFormat("Comic Sans MS", 16, 0xffffff,null,null,null,null,null,TextFormatAlign.CENTER));
tf.width = 170;
tf.selectable = false;
btn2.addEventListener(MouseEvent.CLICK,function():void{
if(mouseX>=btn2.x && mouseX<=(btn2.x+btn2.width) && mouseY>=btn2.y && mouseY<=(btn2.y+btn2.height)){
btn2.visible = false; //hide the solve button
//reveal the col row label and input field
cl.visible = true;
colsTextField.visible = true;
solveMazeBFS();
}
});
addChild(btn2);
btn2.x = 0;
btn2.y = btn.y + 50;
btn2.graphics.beginFill(0x0000ff);
btn2.graphics.drawRect(0,0,170,33);
btn2.graphics.endFill();
btn2.addChild(tf);
btn2.visible = false;
}
private function initGrid():void{
grid = new Vector.<Object>();
for(var i:int = 0;i<ROWS;i++){
for(var j:int = 0;j<COLS;j++){
var gi:Object = new Object();
gi.i = i;
gi.j = j;
gi.up = null;
gi.down = null;
gi.left = null;
gi.right = null;
if(j>0){
gi.left = grid[i*ROWS + j - 1];
gi.left.right = gi;
}
if(i>0){
gi.up = grid[(i-1)*ROWS + j];
gi.up.down = gi;
}
gi.wentleft = false;
gi.wentright = false;
gi.wentup = false;
gi.wentdown = false;
gi.visited = false;
grid.push(gi);
}
}
}
private function drawGrids():void{
this.graphics.clear();
for(var i:int = 0;i<ROWS;i++){
for(var j:int = 0;j<COLS;j++){
var gi:Object = grid[i*ROWS+j];
this.graphics.lineStyle(1,0);
this.graphics.drawRect(j*GSIZE,i*GSIZE,GSIZE,GSIZE);
this.graphics.lineStyle(1,0xffff00);
this.graphics.beginFill(0xffff00);
this.graphics.drawRect(j*GSIZE+1,i*GSIZE+1,GSIZE-2,GSIZE-2);
this.graphics.endFill();
}
}
}
private function drawMaze():void{
this.graphics.lineStyle(1,0xffff00);
for(var i:int = 0;i<ROWS;i++){
for(var j:int = 0;j<COLS;j++){
var gi:Object = grid[i*ROWS+j];
if(gi.wentup==true){
this.graphics.moveTo(j*GSIZE+1,i*GSIZE);
this.graphics.lineTo((j+1)*GSIZE,i*GSIZE);
}
if(gi.wentdown==true){
this.graphics.moveTo(j*GSIZE+1,(i+1)*GSIZE);
this.graphics.lineTo((j+1)*GSIZE,(i+1)*GSIZE);
}
if(gi.wentleft==true){
this.graphics.moveTo(j*GSIZE,i*GSIZE+1);
this.graphics.lineTo(j*GSIZE,(i+1)*GSIZE);
}
if(gi.wentright==true){
this.graphics.moveTo((j+1)*GSIZE,i*GSIZE+1);
this.graphics.lineTo((j+1)*GSIZE,(i+1)*GSIZE);
}
}
}
}
private function shuffle(a:Array):void{
var p:int;
var t:*;
var i:int;
for(i=a.length-1;i>=0;i--){
p = Math.floor(Math.random()*(i+1));
t = a[i];
a[i] = a[p];
a[p] = t;
}
}
private function solveMazeBFS():void{
//solve by breadth first search
var gi:Object = grid[0];
var endgi:Object = grid[ROWS*COLS - 1];
var queue:Vector.<Object> = new Vector.<Object>();
queue.push(gi);
gi.prev = null;
while(gi!=endgi && queue.length>0){
gi = queue.pop();
if(gi.wentleft==true){
gi.left.prev = gi;
queue.push(gi.left);
}
if(gi.wentright==true){
gi.right.prev = gi;
queue.push(gi.right);
}
if(gi.wentup==true){
gi.up.prev = gi;
queue.push(gi.up);
}
if(gi.wentdown==true){
gi.down.prev = gi;
queue.push(gi.down);
}
}
if(gi==endgi){
this.graphics.lineStyle(1,0xcc0000);
while(gi!=null){
this.graphics.moveTo(gi.j*GSIZE + GSIZE/2, gi.i*GSIZE + GSIZE/2);
this.graphics.lineTo(gi.prev.j*GSIZE + GSIZE/2, gi.prev.i*GSIZE + GSIZE/2);
gi = gi.prev;
}
}
}
private function generateMaze():void{
/***algorithm works as follows:
first select a start grid. Then, go to a random child which isn't visited yet.
push the visited grids to the grid. If it arrives to a grid with no available neigbour,
pop a grid from stack to go on from there
(this is called backtracking - check wikipedia for details of maze generation algorithm).
***/
var stack:Vector.<Object> = new Vector.<Object>();
//push first element to the stack and start depth first search thru there
stack.push(grid[0]);
grid[0].visited = true;
var gi:Object = grid[0];
while(stack.length>0){
gi.visited = true;
//put children in an array
var a:Array = new Array();
if(gi.left!=null && gi.left.visited==false)a.push(0);
if(gi.right!=null && gi.right.visited==false)a.push(1);
if(gi.up!=null && gi.up.visited==false)a.push(2);
if(gi.down!=null && gi.down.visited==false)a.push(3);
shuffle(a);
var flag:Boolean = false; //found a neighbour flag
for each(var i:int in a){
if(i==0){
gi.wentleft = true;
stack.push(gi.left);
gi = gi.left;
flag = true;
break;
}
else if(i==1){
gi.wentright = true;
stack.push(gi.right);
gi = gi.right;
flag = true;
break;
}
else if(i==2){
gi.wentup = true;
stack.push(gi.up);
gi = gi.up;
flag = true;
break;
}
else{
gi.wentdown = true;
gi.down.visited = true;
stack.push(gi.down);
gi = gi.down;
flag = true;
break;
}
}
if(flag==false){
if(stack.length>0)
gi = stack.pop();
}
}
}
}
}