Ch. 8 Map Generation

The first function that we will add is called maze_generator_kruskal. Uses randomized Kruskal's algorithm to generate a maze. https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal.27s_algorithm

Normally this algorithm generates 'perfect' mazes, with only one route from end to beginning. For gameplay reasons multiple routes through the maze is preferred. This is achieved by randomly deleting additional walls.


class Cell {
	constructor(x, y, i, j) {
	  this.ind_x = i;
    this.ind_y = j;
    this.x = x;
    this.y = y;
    this.right_wall = true;
    this.bottom_wall = true;
    }
	};

We will embed a function called shuffle. Shuffles array in place. Taken from http://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array-in-javascript


function shuffle(a) {
  var j, x, i;
  for (var i = a.length; i; i--) {
	  j = Math.floor(Math.random() * i);
    x = a[i - 1];
    a[i - 1] = a[j];
    a[j] = x;
  }
}

Our next function is called find_cell_set. Finds the set where the given cell is found.


function find_cell_set(cell, sets) {
	for (set in sets) {
	  if (sets[set].has(cell)) return set;
  }
}

Our next function is called join_cell_sets. Checks if given cells are in different sets, joins the sets and returns true. Otherwise returns false.


function join_cell_sets(cell_1, cell_2, sets) {
	set_ind1 = find_cell_set(cell_1, sets);
  set_ind2 = find_cell_set(cell_2, sets);
  if (!(set_ind1 === set_ind2)) {
	  var joined_set = new Set(function*() {
	    yield* sets[set_ind1]; yield* sets[set_ind2]; }()
     );
     delete sets[set_ind1];
     delete sets[set_ind2];
     sets.push(joined_set);
     return true;
	   }
     return false;
  }

We will create some attributes for each of our cells.


cell_size_min = 30;
cell_size_max = 100;
rand = Math.random();
CELL_SIZE = 30 + (rand * (100-30)); // A random number between min and max
CELL_SIZE = Math.floor(CELL_SIZE);
console.log(CELL_SIZE);
console.log(CELL_SIZE % 5);
CELL_SIZE -= CELL_SIZE % 5;
console.log(CELL_SIZE);

Next we will create cells to assist with maze generation.



var cells = [];
CELLS_X = Math.floor(WIDTH / CELL_SIZE);
CELLS_Y = Math.floor(HEIGHT / CELL_SIZE);
for (var i = 0; i < CELLS_X; i++) {
  var x = i * CELL_SIZE + CELL_SIZE / 2;
  var column = []

  for (var j = 0; j < CELLS_Y; j++) {
    var y = j * CELL_SIZE + CELL_SIZE / 2;
    new_cell = new Cell(x, y, i, j);
    column[j] = new_cell;
  }
  cells[i] = column;
}

And then we add all walls to arrays and create a set for each cell.


var right_walls = [];
var bottom_walls = [];
var cell_sets = [];
for (var i = 0; i < CELLS_X; i++) {
  for (var j = 0; j < CELLS_Y; j++) {
    cell = cells[i][j];
    cell_sets.push(new Set([cell]));
    right_walls.push(cell);
    bottom_walls.push(cell);
  }
}

To make sure that each map is random and doesn’t repeat we will shuffle walls to randomize the maze


shuffle(right_walls);
shuffle(bottom_walls);

Next we will have some variables adjust the proportion of removed horizontal and vertical walls.


var horiz_prob = 0.6; // value must be 0 < x <= 1
    var vert_prob = 0.7; // value must be 0 < x <= 1
    var remove_anyway_prob = 0.2; // Probability for removing extra walls

We will use a while loop with a couple nested if statements that remove all walls between disconnected cells.


while (right_walls.length > 0 && bottom_walls.length > 0) {
  // Right walls
  if (right_walls.length > 0 && Math.random() < vert_prob) {
    var cell = right_walls.pop();
    if (cell.ind_x + 1 < CELLS_X) {
      next_cell = cells[cell.ind_x+1][cell.ind_y];
      // Check if the cell on right belongs to the same set (already connected)
      if (join_cell_sets(cell, next_cell, cell_sets)) {
        cell.right_wall = false;
      }
      // Randomly delete the wall anyway
      else if (Math.random() < remove_anyway_prob) cell.right_wall = false;
    }
  }

if (bottom_walls.length > 0 && Math.random() < horiz_prob) {
    var cell = bottom_walls.pop();
    if (cell.ind_y + 1 < CELLS_Y) {
      next_cell = cells[cell.ind_x][cell.ind_y+1];
      // Check if the cell below belongs to the same set (already connected)
      if (join_cell_sets(cell, next_cell, cell_sets)) {
        cell.bottom_wall = false;
      }
      // Randomly delete the wall anyway
      else if (Math.random() < remove_anyway_prob) cell.bottom_wall = false;
    }
  }
}

Remember when we created gameobjects. Well, each wall is a gameobject because how how it acts (destructable, insdestructable). So we create a GameObject for every wall.


for (column_ind in cells) {
  column = cells[column_ind];
  for (cell_ind in column) {
    cell = column[cell_ind];
    var x = cell.x;
    var y = cell.y;
    var s = CELL_SIZE/2;
    var w = WALL_WIDTH/2;
    if (cell.bottom_wall) {
	    let wall = new GameObject(x, y+s, s*2, w*2);
      if (cell_ind == column.length-1) {
        // Make the border walls indestructible
	      wall.set_destructible(false);
      }
    }
    if (cell.right_wall) {
      let wall = new GameObject(x+s, y, w*2, s*2);
      if (column_ind == cells.length-1) {
        // Make the border walls indestructible
        wall.set_destructible(false);
      }
    }

    // Add left border wall
    if (column_ind == 0) {
      let wall = new GameObject(x-s+1, y, w*2, s*2); 
			// Offset by one to improve visibility
      // Make the border walls indestructible
      wall.set_destructible(false);
    }
    // Add top border wall
    if (cell_ind == 0) {
      let wall = new GameObject(x, y-s+1, s*2, w*2); 
			// Offset by one to improve visibility
      // Make the border walls indestructible
      wall.set_destructible(false);
    }
  }
 }
}

After this we will call the main function for it just to repeat all over again, for a new game.

The very last part that we need to add is something to return some objects/methods for debugging purposes.


return {
	GAME_OBJECTS : GAME_OBJECTS,
	SET_DEBUG : function set_debug(value) { DEBUG = value; },
  SET_COLLISION_DISTANCE : function set_collision_distance(value) { MAX_DIST_FOR_COLLISIONS = value; },
};

})();

ALL OF CHAPTER EIGHT CODE https://pastebin.com/mnwHpL70

All code: Tank Game Code

Previous Chapter

7️⃣

Ch. 7 Main Functions