Breadth-first pathfinding in a randomly generated maze
Talking about Maze game, Actionscript 3, Flash and Users contributions.
Do you like my tutorials?
Then consider supporting me on Ko-fi.
If you are following the blog for a long time, you should know I love mazes and pathfinding algorithms.
Just to show you a couple of examples, look at the perfect maze generation with AS3, perfect maze generation – tile based version and the basics of pathfinding – animated example.
Today Chevy Ray Johnston shares with us a simple breadth-first search pathfinding system (on a randomly generated maze).
In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. (source: Wikipedia)
Click on 2 black tiles to pathfind between them.
And here is the source code for you to study it:
package {
import flash.display.Shape;
import flash.geom.Point;
import flash.events.MouseEvent;
import flash.display.BitmapData;
import flash.display.Bitmap;
import flash.display.Sprite;
//CLICK ON 2 BLACK TILES TO PATHFIND BETWEEN THEM!
public class Main extends Sprite {
//Maze should always be an odd-number of tiles! (eg. 9x9, 33x15, etc.)
public const MAZE_WIDTH:int=31;
public const MAZE_HEIGHT:int=23;
public const MAZE_SCALE:Number=20;
//Directional constants
public const ILLEGAL:int=0;
public const OPEN:int=1;
public const RIGHT:uint=2;
public const LEFT:uint=3;
public const DOWN:uint=4;
public const UP:uint=5;
public var closed:BitmapData=new BitmapData(MAZE_WIDTH,MAZE_HEIGHT,false,0);
public var data:BitmapData=new BitmapData(MAZE_WIDTH,MAZE_HEIGHT,false,0xFFFFFF);
public var bitmap:Bitmap=new Bitmap(data);
public var start:Point;
public var end:Point;
public var pathShape:Shape = new Shape();
public function Main() {
x=10;
y=10;
bitmap.scaleX=bitmap.scaleY=MAZE_SCALE;
addChild(bitmap);
pathShape.scaleX=pathShape.scaleY=MAZE_SCALE;
pathShape.x=pathShape.y=MAZE_SCALE/2;
addChild(pathShape);
generateMaze();
stage.addEventListener(MouseEvent.CLICK, onClick);
}
public function onClick(e:MouseEvent):void {
start=end;
end = new Point(int(mouseX / MAZE_SCALE), int(mouseY / MAZE_SCALE));
if (start != null) {
pathShape.graphics.clear();
pathShape.graphics.beginFill(0xFF0000);
pathShape.graphics.drawCircle(start.x, start.y, 0.25);
pathShape.graphics.drawCircle(end.x, end.y, 0.25);
pathShape.graphics.endFill();
pathShape.graphics.lineStyle(0, 0xFF0000);
var path:Array=pathfind(start,end);
if (path != null && path.length > 1) {
pathShape.graphics.moveTo(path[0].x, path[0].y);
for (var i:int = 1; i < path.length; i++) {
pathShape.graphics.lineTo(path[i].x, path[i].y);
}
}
}
}
public function pathfind(start:Point, end:Point):Array {
if (! getTile(start.x,start.y)&&! getTile(end.x,end.y)) {
closed.fillRect(closed.rect, 0xFF000000 | OPEN);
setClosed(start.x, start.y, ILLEGAL);
var x:int;
var y:int;
var xQueue:Array=[];
var yQueue:Array=[];
xQueue.push(start.x);
yQueue.push(start.y);
while (xQueue.length > 0) {
x=xQueue.shift();
y=yQueue.shift();
if (x == end.x && y == end.y) {
var path:Array=[];
var tile:int=getClosed(x,y);
while (tile != ILLEGAL) {
path.push(new Point(x, y));
switch (tile) {
case RIGHT :
x++;
break;
case LEFT :
x--;
break;
case DOWN :
y++;
break;
case UP :
y--;
break;
}
tile=getClosed(x,y);
}
path.push(new Point(x, y));
return path.reverse();
}
else {
if (getClosed(x + 1, y) == OPEN && !getTile(x + 1, y)) {
setClosed(x + 1, y, LEFT);
xQueue.push(x + 1);
yQueue.push(y);
}
if (getClosed(x - 1, y) == OPEN && !getTile(x - 1, y)) {
setClosed(x - 1, y, RIGHT);
xQueue.push(x - 1);
yQueue.push(y);
}
if (getClosed(x, y + 1) == OPEN && !getTile(x, y + 1)) {
setClosed(x, y + 1, UP);
xQueue.push(x);
yQueue.push(y + 1);
}
if (getClosed(x, y - 1) == OPEN && !getTile(x, y - 1)) {
setClosed(x, y - 1, DOWN);
xQueue.push(x);
yQueue.push(y - 1);
}
}
}
}
return null;
}
public function generateMaze():void {
var xStack:Array=[];
var yStack:Array=[];
var sides:Array=[];
data.fillRect(data.rect, 0xFFFFFFFF);
//Pick random start point
var x:int=1+int(Math.random()*(MAZE_WIDTH/2))*2;
var y:int=1+int(Math.random()*(MAZE_HEIGHT/2))*2;
xStack.push(x);
yStack.push(y);
//Maze generation loop
while (xStack.length > 0) {
x=xStack[xStack.length-1];
y=yStack[yStack.length-1];
sides.length=0;
if (getTile(x + 2, y)) {
sides.push(RIGHT);
}
if (getTile(x - 2, y)) {
sides.push(LEFT);
}
if (getTile(x,y+2)) {
sides.push(DOWN);
}
if (getTile(x,y-2)) {
sides.push(UP);
}
if (sides.length>0) {
var side:int=sides[int(Math.random()*sides.length)];
switch (side) {
case RIGHT :
setTile(x + 1, y, false);
setTile(x + 2, y, false);
xStack.push(x + 2);
yStack.push(y);
break;
case LEFT :
setTile(x - 1, y, false);
setTile(x - 2, y, false);
xStack.push(x - 2);
yStack.push(y);
break;
case DOWN :
setTile(x, y + 1, false);
setTile(x, y + 2, false);
xStack.push(x);
yStack.push(y + 2);
break;
case UP :
setTile(x, y - 1, false);
setTile(x, y - 2, false);
xStack.push(x);
yStack.push(y - 2);
break;
}
}
else {
xStack.pop();
yStack.pop();
}
}
}
public function getTile(x:int, y:int):Boolean {
if (x < 0 || y < 0 || x >= MAZE_WIDTH || y >= MAZE_HEIGHT) {
return false;
}
return data.getPixel(x, y) > 0x000000;
}
public function setTile(x:int, y:int, solid:Boolean):void {
data.setPixel(x, y, solid ? 0xFFFFFF : 0x000000);
}
public function getClosed(x:int, y:int):int {
if (x < 0 || y < 0 || x >= MAZE_WIDTH || y >= MAZE_HEIGHT) {
return ILLEGAL;
}
return closed.getPixel(x, y);
}
public function setClosed(x:int, y:int, value:int):void {
closed.setPixel(x, y, value);
}
}
}
You can also download the entire project.
Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.