Breadth-first pathfinding in a randomly generated maze

Read all posts about "" game

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.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

214 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers