I am trying to generate a maze using javascript (Depth First Search Algorithm). I have already read much on DFS Algorithms. But I am facing difficulty in generation of maze. The generated maze do not look like a maze at all. I am trying to follow the very basic one using stacks to keep the record of path followed to create a maze. I have two files one maze.js and another index.html to display the output of maze.
Below is the code for maze.js
function Cell(center) {
this.center_cell = center;
this.neighbours = null;
this.visited = false;
// top, right, bottom, left neighbours, 1
// means the wall in between has been
// removed
this.walls = [ 0, 0, 0, 0 ];
this.last_selected_neigh = null;
this.calc_neighbours = function() {
var n_top = [ this.center_cell[0], this.center_cell[1] - 1 ];
var n_right = [ this.center_cell[0] + 1, this.center_cell[1] ];
var n_bottom = [ this.center_cell[0], this.center_cell[1] + 1 ];
var n_left = [ this.center_cell[0] - 1, this.center_cell[1] ];
this.neighbours = new Array(n_top, n_right, n_bottom, n_left);
// console.log(this.neighbours);
return this.neighbours;
};
this.set_visited = function() {
this.visited = true;
};
this.get_visited = function() {
return this.visited;
};
this.get_neighbours = function() {
return this.calc_neighbours();
};
this.get_random_neighbour = function() {
this.calc_neighbours();
var rand_neigh = Math.floor(Math.random() * 4);
this.last_selected_neigh = rand_neigh;
// break the walls that is in-between this cell and other neighbour
// this.walls[rand_neigh] = 1;
return this.neighbours[rand_neigh];
};
this.get_walls = function() {
return this.walls;
};
this.remove_wall = function() {
this.walls[this.last_selected_neigh] = 1;
};
};
var maze = {
width : null,
height : null,
cells : [],
build : function(width, height) {
this.width = width;
this.height = height;
return this;
},
get_width : function() {
return this.width;
},
get_height : function() {
return this.height;
},
put_cell : function(x, y, item) {
this.cells[x][y] = item;
},
pop_cell : function() {
this.cells.pop();
},
init : function() {
for ( var y = 0; y < this.get_height(); y++) {
// cell_pos = new Array();
for ( var x = 0; x < this.get_width(); x++) {
this.cells[x] = new Array();
this.cells[x][y] = new Array();
}
}
return this;
},
begin : function() {
// initialize the empty cells
this.init();
var randomCell = [ Math.floor(Math.random() * this.get_height()),
Math.floor(Math.random() * this.get_width()) ];
var cell = new Cell(randomCell);
var total_cells = this.width * this.height;
var total_visits = 1;
var stack = [];
cell.set_visited();
stack.push(cell);
while (total_visits <= total_cells) {
var random_pos = cell.get_random_neighbour();
var r_x = random_pos[0];
var r_y = random_pos[1];
var random_neighbour = new Cell(random_pos);
// get all neighbours
random_neighbour.calc_neighbours();
if (random_neighbour.get_visited() == false) {
// this.cells.push(cell);
if (r_x > -1 && r_x < this.get_width() && r_y > -1
&& r_y < this.get_height()) {
stack.push(random_neighbour);
random_neighbour.set_visited();
cell.remove_wall();
this.put_cell(r_x, r_y, cell);
cell = random_neighbour;
}
// Set the currently selected random neighbour as current cell
} else {
cell = stack.pop();
}
// Update the visit counter
total_visits++;
}
// console.log(this.get_all_cells());
},
get_cell : function(x, y) {
return this.cells[x][y];
},
get_all_cells : function() {
return this.cells;
},
draw : function() {
$table = $('<tbody></tbody>');
for ( var y = 0; y < this.height; y++) {
$tr = $('<tr></tr>');
$table.append($tr);
for ( var x = 0; x < this.width; x++) {
$td = $('<td> </td>');
$tr.append($td);
if (this.get_cell(x, y) != undefined) {
var cur_cell = this.get_cell(x, y);
// console.log(cur_cell.center_cell);
if (typeof cur_cell == "object") {
if (cur_cell.visited
&& cur_cell.center_cell[0] < this.get_width()
&& cur_cell.center_cell[0] > -1
&& cur_cell.center_cell[1] > -1
&& cur_cell.center_cell[1] < this.get_height()) {
var walls = cur_cell.get_walls();
// console.log(cur_cell);
// / console.log(walls);
if (walls[0] == 0) {
$td.css({
'border-top' : '2px solid #000'
});
}
if (walls[1] == 0) {
$td.css('border-right', '2px solid #000');
}
if (walls[2] == 0) {
$td.css('border-bottom', '2px solid #000');
}
if (walls[3] == 0) {
$td.css('border-left', '2px solid #000');
}
// console.log(walls_bound);
}
}
}
}
}
$("#maze").html($table);
}
}
Below is the code for index.html:
<html>
<head>
<title>Maze</title>
<script src="lib/jquery.js"></script>
<script src="src/maze.js"></script>
<style type="text/css">
#maze {
border:2px solid #000;
border-spacing:0;
border-collapse:collapse;
}
#maze td {
/* border:2px solid #000; */
width: 20px;
height: 20px;
}
#maze tr {
height:20px;
}
</style>
</head>
<body>
<table id="maze" cellspacing="1" cellpadding="1">
</table>
<script>
var m = maze.build(4,4);
m.begin();
m.draw();
</script>
</body>
</html>
The output that I get is very different and doesn't even look like maze at all. This was supposed to be very basic algorithm.
My problem:
- My code never pops the element from the stack, I don't know why. I tried keeping breakpoint in the
cell=stack.popand it seems like it never gets there. - I am still unclear about dead end for maze. Can anyone please point me in the right direction?
Thank you in advance.
