In case Flash no longer exists; a copy of this site is included in the Flashpoint archive's "ultimate" collection.

DFS+BFS maze solver

```1) make maze with DFS
2) solve maze with BFS
Java code from Algorithms Fourth Edition - Princeton University```
by greentec 08 Oct 2013

Tags

Embed
```/**
* Copyright greentec ( http://wonderfl.net/user/greentec )
*/

package {
import com.bit101.components.Label;
import com.bit101.components.NumericStepper;
import com.bit101.components.PushButton;
import com.bit101.components.Style;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Sprite;
import flash.events.Event;
import flash.geom.Rectangle;
import flash.display.Sprite;

[SWF(width=465, height=465, backgroundColor=0x292929, frameRate=60)]

public class FlashTest extends Sprite {

public var mazeData:Vector.<Vector.<Vector.<Boolean>>>;
public var mazeWidth:int = 100;
public var mazeHeight:int = 100;
public var mazeCellWidth:int = 4;
public var mazeCellHeight:int = 4;
public var mazeFullWidth:int = 400;
public var mazeFullHeight:int = 400;
public var marked:Vector.<Boolean>;
public var pathData:Array = [];
//public var pathNum:int = 0;

public var mazeBitmapData:BitmapData;
public var mazeBitmap:Bitmap;
public var mazeSprite:Sprite;

public var randomDoProb:Number = 0.05;

public var startCell:int;
public var endCell:int;
public var startCellColor:uint = 0xffff0080;
public var endCellColor:uint = 0xff00ffff;
public var cellIndent:int = mazeCellWidth / 10;
public var roadCellIndent:int = mazeCellWidth / 5;

public var pathBitmapData:BitmapData;
public var pathBitmap:Bitmap;
public var pathGraph:Graph;
public var pathVector:Vector.<int>;
public var cycle:uint = 0;
public var pathSprite:Sprite;

public var initMazeButton:PushButton;
public var initPathButton:PushButton;
public var showPathButton:PushButton;

public var mazeWidthLabel:Label;
public var mazeWidthNumericStepper:NumericStepper;
public var mazeHeightLabel:Label;
public var mazeHeightNumericStepper:NumericStepper;

public function FlashTest() {
// write as3 code here..
stage.scaleMode = "noScale";
//Style.setStyle(Style.DARK);

mazeBitmapData = new BitmapData(465, 465, true, 0x00ffffff);
mazeBitmap = new Bitmap(mazeBitmapData);
mazeBitmap.x = 10;
mazeBitmap.y = 10;

pathBitmapData = new BitmapData(465, 465, true, 0x00ffffff);
pathBitmap = new Bitmap(pathBitmapData);
pathBitmap.x = 10;
pathBitmap.y = 10;

mazeSprite = new Sprite();

initMazeButton = new PushButton(this, 10, mazeHeight * mazeCellHeight + mazeBitmap.y + 10, "Init Maze", initMaze);
initPathButton = new PushButton(this, initMazeButton.x + initMazeButton.width, initMazeButton.y, "Init Path", initPath);
initPathButton.enabled = false;
showPathButton = new PushButton(this, initPathButton.x + initPathButton.width, initPathButton.y, "Show Path", showPath);
showPathButton.enabled = false;

mazeWidthLabel = new Label(this, 10, initMazeButton.y + initMazeButton.height + 5, "mazeWidth");
mazeWidthNumericStepper = new NumericStepper(this, mazeWidthLabel.x + mazeWidthLabel.width + 10, mazeWidthLabel.y, null);
mazeWidthNumericStepper.value = mazeWidth;
mazeWidthNumericStepper.minimum = 5;
mazeWidthNumericStepper.maximum = 100;
mazeHeightLabel = new Label(this, mazeWidthNumericStepper.x + mazeWidthNumericStepper.width + 10, mazeWidthNumericStepper.y, "mazeHeight");
mazeHeightNumericStepper = new NumericStepper(this, mazeHeightLabel.x + mazeHeightLabel.width + 10, mazeHeightLabel.y, null);
mazeHeightNumericStepper.value = mazeHeight;
mazeHeightNumericStepper.minimum = 5;
mazeHeightNumericStepper.maximum = 100;

pathSprite = new Sprite();

}

private function showPath(e:Event):void
{
findPath();

showPathButton.enabled = false;
}

private function onLoop(e:Event):void
{

pathSprite.graphics.clear();
pathSprite.graphics.moveTo((pathVector[cycle] % mazeWidth) * mazeCellWidth + mazeCellWidth / 2, int(pathVector[cycle] / mazeWidth) * mazeCellHeight + mazeCellHeight / 2);
pathSprite.graphics.lineTo((pathVector[cycle + 1] % mazeWidth) * mazeCellWidth + mazeCellWidth / 2, int(pathVector[cycle + 1] / mazeWidth) * mazeCellHeight + mazeCellHeight / 2);
pathBitmapData.draw(pathSprite);

cycle += 1;

if (cycle >= pathVector.length - 1)
{
cycle = 0;
removeEventListener(Event.ENTER_FRAME, onLoop);
initMazeButton.enabled = true;
}
}

private function findPath():void
{
pathVector = dfp.pathTo(endCell);
//trace(pathVector);
}

private function initPath(e:Event):void
{
initPathButton.enabled = false;
showPathButton.enabled = true;

startCell = Math.random() * mazeWidth * mazeHeight;
do
{
endCell = Math.random() * mazeWidth * mazeHeight;
} while (startCell == endCell)

//trace(startCell, endCell);

pathBitmapData.fillRect(pathBitmapData.rect, 0x00ffffff);
pathBitmapData.fillRect(new Rectangle((startCell % mazeWidth) * mazeCellWidth+ cellIndent, int(startCell / mazeWidth) * mazeCellHeight+ cellIndent, mazeCellWidth- cellIndent, mazeCellHeight- cellIndent), startCellColor);
pathBitmapData.fillRect(new Rectangle((endCell % mazeWidth) * mazeCellWidth + cellIndent, int(endCell / mazeWidth) * mazeCellHeight + cellIndent, mazeCellWidth - cellIndent, mazeCellHeight - cellIndent), endCellColor);

//trace(pathData);

var vNum:int = parseInt(pathData[0]);
pathData[1] = (pathData.length - 2);
var eNum:int = parseInt(pathData[1]);

pathGraph = new Graph(vNum, eNum, pathData);

}

private function doRandomMaze():void
{
var randomMax:int = mazeWidth * mazeHeight * 4 * randomDoProb;
for (var i:int = 0; i < randomMax; i += 1)
{
var randX:int = int(Math.random() * mazeWidth);
var randY:int = int(Math.random() * mazeHeight);
var randDirection:int = int(Math.random() * 4);
mazeData[randX][randY][randDirection] = !mazeData[randX][randY][randDirection];
switch(randDirection)
{
case 0:
if (randX > 0)
mazeData[randX - 1][randY][randDirection] = !mazeData[randX - 1][randY][randDirection];
break;
case 1:
if (randY < mazeHeight - 1)
mazeData[randX][randY + 1][randDirection] = !mazeData[randX][randY + 1][randDirection];
break;
case 2:
if (randX < mazeWidth - 1)
mazeData[randX + 1][randY][randDirection] = !mazeData[randX + 1][randY][randDirection];
break;
case 3:
if (randY > 0)
mazeData[randX][randY - 1][randDirection] = !mazeData[randX][randY - 1][randDirection];
break;
}
}
}

private function initGraphics():void
{

}

private function initMaze(e:Event):void
{
initMazeButton.enabled = false;
initPathButton.enabled = true;

var i:int;
var j:int;
var k:int;

mazeWidth = mazeWidthNumericStepper.value;
mazeCellWidth = mazeFullWidth / mazeWidth;
mazeHeight = mazeHeightNumericStepper.value;
mazeCellHeight = mazeFullHeight / mazeHeight;
mazeCellWidth = Math.min(mazeCellWidth, mazeCellHeight);
mazeCellHeight = mazeCellWidth;

mazeData = new Vector.<Vector.<Vector.<Boolean>>>(mazeWidth);
for (i = 0; i < mazeWidth; i += 1)
{
mazeData[i] = new Vector.<Vector.<Boolean>>(mazeHeight);
for (j = 0; j < mazeHeight; j += 1)
{
mazeData[i][j] = new Vector.<Boolean>(4);
for (k = 0; k < 4; k += 1)
{
mazeData[i][j][k] = false;
}
}
}

//adj = new Vector.<Vector.<int>>(mazeWidth * mazeHeight);
//for (i = 0; i < mazeWidth * mazeHeight; i += 1)
//{
//}

pathData = [];
pathData.push(mazeWidth * mazeHeight);
pathData.push(0);
pathBitmapData.fillRect(pathBitmapData.rect, 0x00ffffff);

genMaze();
}

private function genMaze():void
{
var visitedCellNum:int = 0;
var allCellNum:int = mazeWidth * mazeHeight;
marked = new Vector.<Boolean>(mazeWidth * mazeHeight);
var emptycells:Array = [];
var cellStack:Vector.<int> = new Vector.<int>();
var str:String;

var nowX:int = Math.random() * mazeWidth;
var nowY:int = Math.random() * mazeHeight;
marked[nowX + nowY * mazeWidth] = true;
visitedCellNum += 1;

while (visitedCellNum < allCellNum)
{
emptycells = [];

//check cells
if (nowX > 0 && marked[nowX - 1 + nowY * mazeWidth] != true) // W is empty
{
emptycells.push("W");
}
if (nowY < mazeHeight - 1 && marked[nowX + (nowY + 1) * mazeWidth] != true) // S is empty
{
emptycells.push("S");
}
if (nowX < mazeWidth - 1 && marked[nowX + 1 + nowY * mazeWidth] != true) // E is empty
{
emptycells.push("E");
}
if (nowY > 0 && marked[nowX + (nowY - 1) * mazeWidth] != true) // N is empty
{
emptycells.push("N");
}

if (emptycells.length != 0)
{
cellStack.push(nowX + nowY * mazeWidth);

var rand:int = Math.random() * emptycells.length;
switch(emptycells[rand])
{
case "W":
mazeData[nowX][nowY][0] = true;
mazeData[nowX - 1][nowY][2] = true;
//adj[nowX + nowY * mazeWidth].push(nowX - 1 + nowY * mazeWidth);
//adj[nowX - 1 + nowY * mazeWidth].push(nowX + nowY * mazeWidth);
str = String(nowX + nowY * mazeWidth) + " " + String(nowX - 1 + nowY * mazeWidth);
pathData.push(str);
nowX -= 1;
break;

case "S":
mazeData[nowX][nowY][1] = true;
mazeData[nowX][nowY + 1][3] = true;
//adj[nowX + nowY * mazeWidth].push(nowX + (nowY + 1) * mazeWidth);
//adj[nowX + (nowY + 1) * mazeWidth].push(nowX + nowY * mazeWidth);
str = String(nowX + nowY * mazeWidth) + " " + String(nowX + (nowY + 1) * mazeWidth);
pathData.push(str);
nowY += 1;
break;

case "E":
mazeData[nowX][nowY][2] = true;
mazeData[nowX + 1][nowY][0] = true;
//adj[nowX + nowY * mazeWidth].push(nowX + 1 + nowY * mazeWidth);
//adj[nowX + 1 + nowY * mazeWidth].push(nowX + nowY * mazeWidth);
str = String(nowX + nowY * mazeWidth) + " " + String(nowX + 1 + nowY * mazeWidth);
pathData.push(str);
nowX += 1;
break;

case "N":
mazeData[nowX][nowY][3] = true;
mazeData[nowX][nowY - 1][1] = true;
//adj[nowX + nowY * mazeWidth].push(nowX + (nowY - 1) * mazeWidth);
//adj[nowX + (nowY - 1) * mazeWidth].push(nowX + nowY * mazeWidth);
str = String(nowX + nowY * mazeWidth) + " " + String(nowX + (nowY - 1) * mazeWidth);
pathData.push(str);
nowY -= 1;
break;

default:
trace("Error on ", nowX, nowY);
break;
}

marked[nowX + nowY * mazeWidth] = true;
visitedCellNum += 1;
}
else
{
if (cellStack.length != 0)
{
var newCell:int = cellStack.pop();
nowX = newCell % mazeWidth;
nowY = newCell / mazeWidth;
}

}
}

drawMaze();

}

private function dfs(nowX:int, nowY:int):void
{
marked[nowX + nowY * mazeWidth] = true;

}

private function drawMaze():void
{
var i:int;
var j:int;

mazeSprite.graphics.clear();
mazeSprite.graphics.lineStyle(0, 0xcccccc);

for (i = 0; i < mazeData.length; i += 1)
{
for (j = 0; j < mazeData[i].length; j += 1)
{
if (mazeData[i][j][0] == false) // W
{
mazeSprite.graphics.moveTo(i * mazeCellWidth, j * mazeCellHeight);
mazeSprite.graphics.lineTo(i * mazeCellWidth, (j + 1) * mazeCellHeight);
}
if (mazeData[i][j][1] == false) // S
{
mazeSprite.graphics.moveTo(i * mazeCellWidth, (j + 1) * mazeCellHeight);
mazeSprite.graphics.lineTo((i + 1) * mazeCellWidth, (j + 1) * mazeCellHeight);
}
if (mazeData[i][j][2] == false) // E
{
mazeSprite.graphics.moveTo((i + 1) * mazeCellWidth, j * mazeCellHeight);
mazeSprite.graphics.lineTo((i + 1) * mazeCellWidth, (j + 1) * mazeCellHeight);
}
if (mazeData[i][j][3] == false) // N
{
mazeSprite.graphics.moveTo(i * mazeCellWidth, j * mazeCellHeight);
mazeSprite.graphics.lineTo((i + 1) * mazeCellWidth, j * mazeCellHeight);
}
}
}

mazeBitmapData.fillRect(mazeBitmapData.rect, 0x00ffffff);
mazeBitmapData.fillRect(new Rectangle(0, 0, mazeWidth * mazeCellWidth, mazeHeight * mazeCellHeight), 0xff003300);

mazeBitmapData.draw(mazeSprite);
}
}

}

{
private var marked:Vector.<Boolean>;

private var edgeTo:Vector.<int>;
private var s:int;

{
marked = new Vector.<Boolean>(G.getV());
edgeTo = new Vector.<int>(G.getV());
this.s = s;
bfs(G, s);
}

private function bfs(G:Graph, s:int):void
{
var queue:Vector.<int> = new Vector.<int>();
marked[s] = true;
queue.push(s);
while (queue.length != 0)
{
var v:int = queue.shift();
for each (var w:int in G.adj[v])
{
if (!marked[w])
{
edgeTo[w] = v;
marked[w] = true;
queue.push(w);
}
}
}
}

public function hasPathTo(v:int):Boolean
{
return marked[v];
}

public function pathTo(v:int):Vector.<int>
{
if (!hasPathTo(v)) return null;
var path:Vector.<int> = new Vector.<int>();
for (var x:int = v; x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;
}

}

class Graph
{
private var V:int;
private var E:int;

public function Graph(V:int, E:int = 0, data:Array = null)
{
this.V = V;
this.E = 0;
for (var v:int = 0; v < V; v += 1)
{
}

if (data != null)
{
for (var i:int = 0; i < E; i += 1)
{
var nodes:Array = data[2+i].split(" ");
var a:int = parseInt(nodes[0]);
var b:int = parseInt(nodes[1]);
}
}
}

public function getV():int { return V; }
public function getE():int { return E; }

{
E += 1; //trace(E);
}

{
}

public function toString():String
{
var s:String = V + " vertices, " + E + " edges\n";
for (var v:int = 0; v < V; v += 1)
{
s += String(v) + " : ";
for (var w:int = 0; w < this.adj[v].length; w += 1 )
{
s += this.adj[v][w] + " ";
}
s += "\n";
}
return s;
}

public function hasEdge(v:int, w:int):Boolean
{
var i:int;
var vwExist:Boolean = false;
var wvExist:Boolean = false;

for (i = 0; i < adj[v].length; i += 1)
{
{
vwExist = true;
break;
}
}
for (i = 0; i < adj[w].length; i += 1)
{