In the previous tutorial, I implemented a simple maze game. In this tutorial, I will improve the game by using an algorithm for constructing a new maze, once a game has been completed (i.e. the player has escaped the maze).
The algorithm is takes from Rosettacode, but altered, so it is more logic (in my opinion).
The algorithm has to give us a set of two double arrays describing the walls in the maze, vertical_walls and horizontal_walls. The idea for the algorithm is:
In our maze with a grid of 5 time 5 cells we imagine that we initially have walls at all cell edges and further, that all cells are unvisited - here marked as grey:
The algorithm choose a random cell and starts a path from there. For example it can start in the first row (index 0) and fourth column (index 3), here notated as [0,3]. This cell is now visited (and therefore blue and not grey):
The selected (and current) cell has 3 neighbors, the cells at [0,2], [0,4] and [1,3] (using the above notation where the first digit refers to the row index and the second to the column index). Now the algorithm will choose a random neighbor and move to this cell. In this example the random selected cell is the one just below the first (i.e. ayt [1,3]). During the movement from one cell to the next, the wall being passed is removed:
Thus continuing under the condition, never to go into a visited cell if there are unvisited neightbor cells. One can however end in a cell which only has visited neighbors:
In this case one will step back to the previous cell and continue from there to the next unvisited cell. If this cell neither has unvisited neighbors one has to go one step further back an so fort, untill one get to a cell with unvisited neighbord. In our case the next step will be:
To implement the algorithm one will first have to define the two double arrays describing the walls of the maze. And these will initially describe a scenario, where alle cells are surronded by walls:
var horizontal =[]; // matrix holding booleans telling if there's an horizontal edge or not
for(i=0;i<columns;i++) {
horizontal[i] = [];
for(j=0;j<rows+1;j++) {
horizontal[i][j] = true; // initially there is walls in all possible locations, i.e. around every cell
}
}
var vertical =[]; // matrix holding booleans telling if there's an vertical edge or not
for(i=0;i<rows;i++) {
vertical[i] = [];
for(j=0;j<columns+1;j++) {
vertical[i][j] = true; // initially there is walls in all possible locations, i.e. around every cell
}
}
Here rows is the number of rows in the maze and columns is the number of columns in the maze. In our example both will take the value 5.
Now we will define a 5 time 5 grid describing which of the cell is unvisited. Initially all cells are unvisited:
var unvisited = []; // double array telling if cells have been visited or not
for (j=0; j<rows; j++) {
unvisited[j] = [];
for (k=0; k<columns; k++) {
unvisited[j].push(true); // Initially all cells in maze are not visited
}
}
The algorithm wil start selecting a random cell to start. This cell will be marked as visited and the number of visited cells will be counted up. Moreover this cell is added to a path, which purpose is to be able to to go back in case we end in a cell, with no unvisited neighbors (i.e. in a dead end as depitched above):
var n = rows*columns; // number og unvisited neighbors var path = []; // select random starting cell var here = [Math.floor(Math.random()*rows), Math.floor(Math.random()*columns)]; unvisited[here[0]][here[1]]= false; // the starting point is visited n = n-1; // now one less cell is unvisited path.push(here); // add current cell to path
Finally we have the main part of the algorithms, where we examine if any of the current cell neighbor cells haven't been visited. If this is the case, we pick a random of these cells, let it be the new current cell, removes the wall between the previous cell and this cell, marking the now current cell as visited and adds it to the path. And count the number of unvisited cells one down:
// loop till all cell have been visited
while (n > 0) {
var neighbors = []; // neighboring points to current cell, here
if(here[0] > 0) {
neighbors.push([here[0]-1,here[1]]); // cell to the left of current cell
}
if(here[0] < rows-1) {
neighbors.push([here[0]+1,here[1]]); // cell to the right of current cell
}
if(here[1] > 0) {
neighbors.push([here[0],here[1]-1]); // cell over the current cell
}
if(here[1] < columns-1) {
neighbors.push([here[0],here[1]+1]); // cell below the current cell
}
var potential = []; // list of potential next cells, i.e. neighboring cell that haven't been visited
for (j = 0; j < neighbors.length; j++) {
if (unvisited[neighbors[j][0]][neighbors[j][1]]) {
potential.push(neighbors[j]); // only unvisited neighbors are potential
}
}
if (potential.length > 0) { // go to random neighbor cell
var next = potential[Math.floor(Math.random()*potential.length)];
unvisited[next[0]][next[1]]= false;
n = n-1;
// remove wall either ...
if(next[0] == here[0]) { // ... same row (i.e. removing vertical wall)
vertical[next[0]][Math.max(next[1],here[1])] = false;
} // ... or ...
else { // ... same column (i.e. removing horizontal wall)
horizontal[next[1]][Math.max(next[0],here[0])] = false;
}
path.push(next);
here = next;
}
else { // all neighbor cells have been visited go one step back
here = path.pop();
}
}
The case where there is no unvisited neighbor cells implies we remove the last cell from the path.
The full algorithm can be gathered in a function, which will have the number of rows and columns for the maze as argument, and thus can be used for an arbitrary maze:
function createEdges(columns,rows) {
// initialise
var n=columns*rows;
var horizontal =[]; // matrix holding booleans telling if there's an horizontal edge or not
for(i=0;i<columns;i++) {
horizontal[i] = [];
for(j=0;j<rows+1;j++) {
horizontal[i][j] = true;
}
}
var vertical =[]; // matrix holding booleans telling if there's an vertical edge or not
for(i=0;i<rows;i++) {
vertical[i] = [];
for(j=0;j<columns+1;j++) {
vertical[i][j] = true;
}
}
var unvisited = []; // cells in maze are initially not visited
for (j=0; j<rows; j++) {
unvisited[j] = [];
for (k=0; k<columns; k++) {
unvisited[j].push(true);
}
}
var path = [];
// select random starting cell and later current cell
var here = [Math.floor(Math.random()*rows), Math.floor(Math.random()*columns)];
unvisited[here[0]][here[1]]= false; // the starting point is visited
n = n-1;
path.push(here);
// loop till all cell visited
while (n > 0) {
var neighbors = []; // neighboring points to current cell, here
if(here[0] > 0) {
neighbors.push([here[0]-1,here[1]]);
}
if(here[0] < rows-1) {
neighbors.push([here[0]+1,here[1]]);
}
if(here[1] > 0) {
neighbors.push([here[0],here[1]-1]);
}
if(here[1] < columns-1) {
neighbors.push([here[0],here[1]+1]);
}
var potential = [];
for (j = 0; j < neighbors.length; j++) {
if (unvisited[neighbors[j][0]][neighbors[j][1]]) {
potential.push(neighbors[j]); // only unvisited neighbors are potential
}
}
if (potential.length > 0) {
var next= potential[Math.floor(Math.random()*potential.length)];
unvisited[next[0]][next[1]]= false;
n = n-1;
if(next[0] == here[0]) { // previous and new cell are in same row, i.e. removing vertical wall
vertical[next[0]][Math.max(next[1],here[1])] = false;
}
else { // // previous and new cell are in same column, i.e. removing horizontal wall
horizontal[next[1]][Math.max(next[0],here[0])] = false;
}
path.push(next);
here = next;
}
else {
here = path.pop();
}
}
return {horizontal: horizontal, vertical: vertical};
}
Now all we need is to use the algorithm in our maze game. To keep it simple we will first calculate and create a new maze when the player has completed a game (i.e. escaped a maze). In the function move_up we changed the code to:
function move_up() {
if(horizontal_walls[current_column][current_row]) {
alert("Bump - you can't go up!");
}
else {
current_row--;
move_marker();
if(current_row == -1) {
alert("Congratulation - you got out of the maze");
var obj = createEdges(5,5); // create new maze
vertical_walls = obj.vertical;
horizontal_walls = obj.horizontal;
horizontal_walls[4][0] = false; // removing horizontal wall at upper right corner, so we can get out of the maze
drawMaze();
current_row = 4;
current_column = 0;
move_marker();
}
}
}
The function draw_maze have to be implemented so the player will se the correct maze. Fortunately this is quite easy:
function drawMaze() {
var group = document.getElementById("maze");
// Clean up previous maze
while (group.firstChild) {
group.removeChild(group.firstChild);
}
// first draw vertical walls
for(row=0; row&l;5; row++) {
for(column=0; column&l;6; column++) {
if(vertical_walls[row][column]) {
var x = 61 + column*60;
var y = 61 + row*60;
var line = document.createElementNS("http://www.w3.org/2000/svg", "line");
line.setAttributeNS(null,"x1",parseInt(x));
line.setAttributeNS(null,"y1",parseInt(y));
line.setAttributeNS(null,"x2",parseInt(x));
line.setAttributeNS(null,"y2",parseInt(y+60));
group.appendChild(line);
}
}
}
// then draw vertical walls
for(column=0; column&l;5; column++) {
for(row=0; row&l;6; row++) {
if(horizontal_walls[column][row]) {
var x = 61 + column*60;
var y = 61 + row*60;
var line = document.createElementNS("http://www.w3.org/2000/svg", "line");
line.setAttributeNS(null,"x1",parseInt(x));
line.setAttributeNS(null,"y1",parseInt(y));
line.setAttributeNS(null,"x2",parseInt(x+60));
line.setAttributeNS(null,"y2",parseInt(y));
group.appendChild(line);
}
}
}
}
The first few lines of codes in this function removes all contents from the SVG group element with id maze, in other words the previous drawn walls.
With this modification our games have been improved and made more challenging and fun. From here it is a straighforward to expand the game both with regards to complexity (making the maze bigger, implementing key listerner for using keyboard arrow keys as alternative to button, etc) and visually (making it more visual appealing), as has been done on my homepage.
This new improved version of our maze game can be seen and played here.