DFS+BFS maze solver
1) make maze with DFS
2) solve maze with BFS
Java code from Algorithms Fourth Edition - Princeton University
/**
* Copyright greentec ( http://wonderfl.net/user/greentec )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/ts97
*/
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 adj:Vector.<Vector.<int>>;
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 roadCellColor:uint = 0xffffff00;
public var roadCellIndent:int = mazeCellWidth / 5;
public var pathBitmapData:BitmapData;
public var pathBitmap:Bitmap;
public var pathGraph:Graph;
public var dfp:BreadthFirstPaths;
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;
addChild(mazeBitmap);
pathBitmapData = new BitmapData(465, 465, true, 0x00ffffff);
pathBitmap = new Bitmap(pathBitmapData);
pathBitmap.x = 10;
pathBitmap.y = 10;
addChild(pathBitmap);
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();
addEventListener(Event.ENTER_FRAME, onLoop);
showPathButton.enabled = false;
}
private function onLoop(e:Event):void
{
pathSprite.graphics.clear();
pathSprite.graphics.lineStyle(2, roadCellColor);
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);
dfp = new BreadthFirstPaths(pathGraph, startCell);
}
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)
//{
//adj[i] = new Vector.<int>();
//}
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);
}
}
}
class BreadthFirstPaths
{
private var marked:Vector.<Boolean>;
private var edgeTo:Vector.<int>;
private var s:int;
public function BreadthFirstPaths(G:Graph, 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 var adj:Vector.<Vector.<int>>;
public function Graph(V:int, E:int = 0, data:Array = null)
{
this.V = V;
this.E = 0;
adj = new Vector.<Vector.<int>>(V);
for (var v:int = 0; v < V; v += 1)
{
adj[v] = new Vector.<int>;
}
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]);
addEdge(a, b);
}
}
}
public function getV():int { return V; }
public function getE():int { return E; }
public function addEdge(v:int, w:int):void
{
adj[v].push(w);
adj[w].push(v);
E += 1; //trace(E);
}
public function getadj(v:int):Vector.<int>
{
return adj[v];
}
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)
{
if (adj[v][i] == w)
{
vwExist = true;
break;
}
}
for (i = 0; i < adj[w].length; i += 1)
{
if (adj[w][i] == v)
{
wvExist = true;
break;
}
}
return vwExist && wvExist;
}
}