Maze Creation with DFS

https://ezgineer.wordpress.com/2016/02/07/build-your-own-maze/




Just click “Start” and enjoy this hypnotizing maze creation process.

 

And here’s the code:

Sorry for being lazy about comments.

var UP = 1;
var LEFT = 2;
var DOWN = 4;
var RIGHT = 8;

var speed = 50; //actions per second

var c = document.getElementById('mazeCanvas');
var ctx = c.getContext("2d");

var canvasWidth = 500;
var canvasHeight = 500;

var gridWidth=50;
var gridHeight=50;

var visibleGridWidth = canvasWidth / gridWidth / 2;
var visibleGridHeight = canvasHeight / gridHeight / 2;
var margin = 1;

var stack = [];

var visited = [];


function getSq(x, y) {
	return x + gridWidth * y;
}

function isVisited(x, y) {
	if(x >= 0 && x < gridWidth && y >= 0 && y < gridHeight) { return (visited[getSq(x, y)] == 1) ? true : false; } return true; } function chooseRandom(directions) { var i = 0; while(true) { var rnd = Math.random(); if(rnd >= 0.5) {
			return directions[i];
		}
		i++;
		if(i >= directions.length) i = 0;
	}
}


var currentX = 0;
var currentY = 0;

function drawTo(direction) {
	ctx.fillStyle = "#FFFFFF";
	switch(direction) {
		case UP:
			ctx.fillRect(currentX * visibleGridWidth * 2 + margin,
						 (currentY-1) * visibleGridHeight * 2 + margin,
						 visibleGridWidth - margin,
						 3 * visibleGridHeight - margin);
			break;
		case DOWN:
			ctx.fillRect(currentX * visibleGridWidth * 2 + margin,
						 currentY * visibleGridHeight * 2 + margin,
						 visibleGridWidth - margin,
						 3 * visibleGridHeight - margin);
			break;
		case LEFT:
			ctx.fillRect((currentX-1) * visibleGridWidth * 2 + margin,
						 currentY * visibleGridHeight * 2 + margin,
						 3 * visibleGridWidth - margin,
						 visibleGridHeight - margin);
			break;
		case RIGHT:
			ctx.fillRect(currentX * visibleGridWidth * 2 + margin,
						 currentY * visibleGridHeight * 2 + margin,
						 3 * visibleGridWidth - margin,
						 visibleGridHeight - margin);
			break;
	}
	
}

function markPlace() {
	ctx.fillStyle = "#FF0000";
	ctx.fillRect(currentX * visibleGridWidth * 2 + margin,
						 currentY * visibleGridHeight * 2 + margin,
						 visibleGridWidth - margin,
						 visibleGridHeight - margin);
}

function markBlue() {
	ctx.fillStyle = "#0000FF";
	ctx.fillRect(currentX * visibleGridWidth * 2 + margin * 2,
						 currentY * visibleGridHeight * 2 + margin * 2,
						 visibleGridWidth - margin * 4,
						 visibleGridHeight - margin * 4);
}

function removeMark() {
	ctx.fillStyle = "#FFFFFF";
	ctx.fillRect(currentX * visibleGridWidth * 2 + margin,
						 currentY * visibleGridHeight * 2 + margin,
						 visibleGridWidth - margin,
						 visibleGridHeight - margin);
}

var intervalId;

function doWork() {
	
	var directions = [];
	if(!isVisited(currentX + 1, currentY)) {
		directions.push(RIGHT);
	}
	if(!isVisited(currentX - 1, currentY)) {
		directions.push(LEFT);
	}
	if(!isVisited(currentX, currentY + 1)) {
		directions.push(DOWN);
	}
	if(!isVisited(currentX, currentY - 1)) {
		directions.push(UP);
	}

	if(directions.length == 0) {
		if(!isVisited(currentX, currentY)) {
			visited[getSq(currentX, currentY)] = 1;
		}
		removeMark();
		var backTrack = stack.pop();
		currentX = backTrack % gridWidth;
		currentY = Math.floor(backTrack / gridWidth);
	} else {
		var d = chooseRandom(directions);
		stack.push(getSq(currentX, currentY));
		visited[getSq(currentX, currentY)] = 1;
		drawTo(d);
		markBlue();
		switch(d) {
			case UP:
				currentY--;
				break;
			case DOWN:
				currentY++;
				break;
			case LEFT:
				currentX--;
				break;
			case RIGHT:
				currentX++;
				break;
		}

	}
	markPlace();
	
	if(stack.length == 0) {
		removeMark();
		clearInterval(intervalId);
	}
	
}
function start() {
	clearInterval(intervalId);

	var _speed = document.getElementById('speed').value;
	var _gridWidth = document.getElementById('grid_horizontal_tiles').value;
	var _gridHeight = document.getElementById('grid_vertical_tiles').value;

	if(_speed) {
		if(parseInt(_speed) > 0) {
			speed = _speed;
		}
	}
	if(_gridWidth) {
		if(parseInt(_gridWidth) > 0) {
			gridWidth = _gridWidth;
		}
	}
	if(_gridHeight) {
		if(parseInt(_gridHeight) > 0) {
			gridHeight = _gridHeight;
		}
	}

	visibleGridWidth = canvasWidth / gridWidth / 2;
	visibleGridHeight = canvasHeight / gridHeight / 2;

	stack = [];
	visited = [];

	visited[getSq(0, 0)] = 1;
	stack.push(getSq(0, 0));

	currentX = 0; currentY = 0;

	ctx.fillStyle = "#00FF00";
	ctx.fillRect(0, 0, 500, 500);

	intervalId = setInterval(doWork, 1000 / speed);
}

2 thoughts on “Maze Creation with DFS

Leave a Reply

Your email address will not be published. Required fields are marked *