8️⃣

# 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);
}
}

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);
}
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

©2024 Code 4 Tomorrow 501(c)(3) Non-Profit (EIN: 92-0635065)