Попробуем сделать элегантную алгоритмическую игрушку — лабиринт. Сначала специальный алгоритм будет рисовать для нас случайный лабиринт, а потом мы сделаем так, чтобы его можно было пройти.
Что тут будет интересного:
- Алгоритм создания случайного лабиринта. Оказывается, есть довольно простые закономерности, по которым можно сгенерировать проходимый лабиринт
- Много вложенных циклов и функций, каждая из которых делает что-то простое, но вместе получается нечто сложное и прекрасное
За основу мы возьмём код Сергея Григоровича и адаптируем его под нашу задачу.
Логика проекта
Изначально лабиринт полностью заполнен стенами, в нём нет ходов и свободных мест. Чтобы внутри лабиринта появились маршруты, по которым можно двигаться, мы запустим в лабиринт виртуальный трактор. Он стартует со случайной клетки и расчищает лабиринт до тех пор, пока он не будет готов.
Чтобы понять, готов лабиринт или нет, используем такое свойство лабиринта: если на всех чётных ячейках нет стен, значит, этот лабиринт можно пройти.
👉 Чётные места — это такие места в лабиринте, которые по оси X и Y одновременно имеют чётные координаты. Например, клетка с координатами (2,6) чётная, потому что 2 и 6 чётные числа, а с координатами (2,7) — нет.
Подготовка
Проект пока будет состоять из двух частей:
- HTML-файл, где мы сделаем холст для рисования лабиринта и вызовем нужные скрипты. Холст сейчас нам не понадобится, но мы подготовим всё заранее для следующего шага.
- Скрипт, который сгенерирует лабиринт и запишет карту лабиринта в отдельную переменную.
Дальше мы добавим скрипт, который нарисует наш лабиринт, а потом научим делать всё остальное.
Сейчас сделаем первую часть: напишем HTML-код.
<!DOCTYPE html>
<html lang="ru">
<head>
<meta charset="UTF-8">
<title>Лабиринт</title>
</head>
<body>
<!-- подготавливаем пустой холст, чтобы работать с ним из скрипта -->
<canvas></canvas>
</body>
</html>Сейчас это просто пустая страница, на которой ничего не видно кроме заголовка. Когда мы напишем скрипт и добавим его на страницу, то в консоли сможем увидеть черновую версию лабиринта.
Создаём скрипт
За создание будет отвечать отдельный скрипт — назовём его generateMaze.js и сразу добавим его в HTML-файл:
<!— скрипт, который создаёт лабиринт —>
<script src=»generateMaze.js»></script>Теперь напишем сам скрипт. Чтобы было потом проще его вызывать, сделаем весь скрипт одной большой функцией generateMaze(), а внутри распишем всё, что нужно.
Чтобы скрипт создавал лабиринт нужного нам размера, объявим функцию так:
function generateMaze (columnsNumber, rowsNumber) {}
Всё остальное будем писать внутри этой функции.
Делаем карту и заполняем её стенами
Нам нужно завести отдельную переменную, в которой будет храниться вся карта лабиринта, и на первом этапе заполнить её полностью стенами, чтобы трактору было что чистить:
// карта лабиринта, на старте пустая
const map = [];
// сначала заполняем все ячейки карты стенами
for (let y = 0; y < rowsNumber; y++) {
// в цикле создаём сначала пустой массив — строку
const row = [];
// и заполняем её ячейками с пометкой «стена» столько раз, сколько у нас столбцов
for (let x = 0; x < columnsNumber; x++) {
row.push('▉');
};
// как только собрали очередную строку, отправляем её в массив с картой
map.push(row);
}Готовим трактор к выезду
Чтобы наш трактор работал как нужно, мы должны сделать несколько подготовительных вещей: научиться проверять числа на чётность и выбирать случайные координаты лабиринта на карте.
Проверка на чётность делается просто — объявляем новую функцию и передаём ей число на проверку. Если вернёт true — число чётное.
// функция проверяет чётное число или нет, и если чётное — возвращает true
function isEven (n) {
return n % 2 === 0;
}Со случайными координатами тоже всё легко: берём случайное число в диапазоне от 0 до размера массива, получаем значение ячейки с нужным индексом и возвращаем его:
// функция возвращает случайный элемент из переданного ей массива
function getRandomFrom (array) {
// получаем случайным образом индекс элемента массива
// число будет в диапазоне от 0 до количества элементов в массиве минус 1
const index = Math.floor(Math.random() * array.length);
// возвращаем элемент массива с полученным случайным индексом
return array[index];
}Ставим трактор в лабиринт
Теперь у нас есть всё что нужно для установки трактора. Единственное сложное место в коде — получение стартовых координат. Для этого мы делаем сложный трюк:
- Прямо во время объявления координат по каждой оси вызываем функцию getRandomFrom().
- Внутри этой функции объявляем новый массив, который сразу заполняем числами от 0 до верхнего размера нашей карты лабиринта.
- Во время заполнения постоянно проверяем, чётное число нам попалось или нет. Если чётное — кладём в новый массив, если нет — не кладём.
- В итоге у нас получился массив только из чётных чисел, из которого мы и получаем случайным образом какое-то число с помощью функции getRandomFrom().
// выбираем случайным образом чётные координаты на карте с лабиринтом
const startX = getRandomFrom(Array(columnsNumber).fill(0).map((item, index) => index).filter(x => isEven(x)));
const startY = getRandomFrom(Array(rowsNumber).fill(0).map((item, index) => index).filter(x => isEven(x)));
// трактор, который будет очищать дорожки в лабиринте
var tractor = {};
// ставим его на чётную клетку
tractor.x = startX;
tractor.y = startY;Очищаем клетку с трактором
Чтобы трактор не стоял в стене, нам нужно очистить клетку, на которой оказался трактор. Для этого напишем функцию setField() — она записывает переданное значение по нужным координатам. Смысл её в том, что она сразу проверяет, а правильные ли координаты мы ей передали. Если с координатами всё в порядке, то она сработает; если координат таких в лабиринте нет, то она не будет ничего менять и записывать.
// функция — записать значение ячейки в карту по координатам
function setField (x, y, value) {
// если координаты выходят за границы карты с лабиринтом
if (x < 0 || x >= columnsNumber || y < 0 || y >= rowsNumber) {
// прекращаем работу функции и возвращаем пустое значение
return null;
};
// если дошли досюда, значит, с координатами всё в порядке, и мы записываем значение ячейки по нашим координатам
map[y][x] = value;
}
// сделаем ячейку, в которой стоит трактор, пустой
setField(startX, startY, ' ');Проверяем, лабиринт готов или нет
Чтобы лабиринт был готов, каждая чётная клетка в нём должна быть пустой. Зная это, напишем простую функцию с проверкой:
// функция проверяет, готов лабиринт или ещё нет
// возвращает true, если лабиринт готов; false, если ещё нет
function isMaze () {
// во вложенном цикле проверяем по очереди все ячейки карты
for (let x = 0; x < columnsNumber; x++) {
for (let y = 0; y < rowsNumber; y++) {
// если на чётных местах ещё можно встретить стену,
if (isEven(x) && isEven(y) && getField(x, y) === 'wall') {
// то карта с лабиринтом не готова
return false
}
}
}
// а если мы дошли досюда и функция не прервалась на предыдущей проверке, то лабиринт готов
return true
}Запускаем трактор
Задача трактора — двигаться, очищать и менять направление до тех пор, пока лабиринт не будет готов. Запишем это на языке JavaScript:
// пока лабиринт не готов, отправляем трактор двигаться дальше
while (!isMaze()) {
moveTractor();
}
// если предыдущий цикл закончился, то заканчиваем общую работу скрипта и возвращаем готовую карту
return map;Если помните, мы весь этот код пишем внутри большой функции generateMaze(), поэтому, как только лабиринт готов, — мы прерываем её и возвращаем готовую карту. Она нам пригодится на этапе отрисовки.
Выбираем направления и очищаем лабиринт
Последнее, что нам осталось сделать — написать логику движения трактора. Так как он будет постоянно работать с клетками лабиринта, напишем сначала функцию, которая получает значение любой клетки по её координатам. Логика будет такая же, как и в функции setField() — сначала проверяем правильность координат и только потом возвращаем значение.
// получить значение ячейки из карты по координатам
function getField (x, y) {
// если координаты выходят за границы карты с лабиринтом
if (x < 0 || x >= columnsNumber || y < 0 || y >= rowsNumber) {
// прекращаем работу функции и возвращаем пустое значение
return null;
}
// если дошли досюда, значит, с координатами всё в порядке, и мы возвращаем значение ячейки по нашим координатам
return map[y][x];
}Логика работы трактора будет такая:
- Трактор может ходить на две любые клетки в любом направлении: вверх, вниз, влево или вправо.
- Если в выбранном направлении через две клетки есть стена, то очищаем обе и меняем направление. Если через две клетки стены нет, то просто меняем направление.
- Там, где прошёл трактор, появляется свободное место.
Запишем это в виде кода. Выглядит громоздко, но на самом деле всё просто, комментарии помогут разобраться.
// двигаем трактор, который расчищает лабиринт
// трактор двигается на 2 клетки, и если вторая клетка — это стена, то очищаем обе
function moveTractor () {
// массив с возможными направлениями трактора
const directs = [];
// если есть место слева
if (tractor.x > 0) {
// помечаем, что можно идти налево
directs.push('left');
};
// если есть место справа
if (tractor.x < columnsNumber - 2) {
// помечаем, что можно идти направо
directs.push('right');
};
// если есть место сверху
if (tractor.y > 0) {
// помечаем, что можно идти наверх
directs.push('up');
};
// если есть место внизу
if (tractor.y < rowsNumber - 2) {
// помечаем, что можно идти вниз
directs.push('down');
};
// случайным образом выбираем направление, в котором можно пойти
const direct = getRandomFrom(directs);
// в зависимости от выбранного направления, обрабатываем клетки
switch (direct) {
case 'left':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x - 2, tractor.y) === '▉') {
setField(tractor.x - 1, tractor.y, ' ');
setField(tractor.x - 2, tractor.y, ' ');
};
// меняем координату трактора
tractor.x -= 2;
break;
case 'right':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x + 2, tractor.y) === '▉') {
setField(tractor.x + 1, tractor.y, ' ');
setField(tractor.x + 2, tractor.y, ' ');
};
// меняем координату трактора
tractor.x += 2;
break;
case 'up':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x, tractor.y - 2) === '▉') {
setField(tractor.x, tractor.y - 1, ' ');
setField(tractor.x, tractor.y - 2, ' ');
};
// меняем координату трактора
tractor.y -= 2
break;
case 'down':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x, tractor.y + 2) === '▉') {
setField(tractor.x, tractor.y + 1, ' ');
setField(tractor.x, tractor.y + 2, ' ');
};
// меняем координату трактора
tractor.y += 2;
break;
}
}Рисуем лабиринт
Сейчас рисунок лабиринта у нас хранится в массиве.
Чтобы нарисовать лабиринт на холсте, нужен отдельный большой скрипт — мы его напишем в другой раз. А пока, чтобы убедиться, что алгоритм работает, мы выведем карту лабиринта в консоли.
У нас уже есть функция, которая проверяет, готов лабиринт или нет. Всё, что нам нужно, — это поместить код вывода на консоль в самый конец этой функции. Вот что у нас получится в итоге:
// функция проверяет, готов лабиринт или ещё нет
// возвращает true, если лабиринт готов; false, если ещё нет
function isMaze () {
// во вложенном цикле проверяем по очереди все ячейки карты
for (let x = 0; x < columnsNumber; x++) {
for (let y = 0; y < rowsNumber; y++) {
// если на чётных местах ещё можно встретить стену,
if (isEven(x) && isEven(y) && getField(x, y) === '▉') {
// то карта с лабиринтом не готова
return false;
}
}
}
// а если мы дошли досюда и функция не прервалась на предыдущей проверке, то лабиринт готов
// рисуем лабиринт в консоли
// переменные для отрисовки строк и границ
var s,d = '';
// рисуем верхнюю границу лабиринта
for (var i = 0; i < columnsNumber; i++) {
d = d + '▉';
}
console.log('▉' + d + '▉');
// рисуем каждую строку
for (var i = 0; i < rowsNumber; i++) {
s = '';
for (var j = 0; j < columnsNumber; j++) {
s = s + map[i][j];
}
console.log('▉' + s + '▉');
}
// рисуем нижнюю границу лабиринта
console.log('▉' + d + '▉');
// сообщаем, что всё готово и выходим из функции
return true;
}Запускаем генератор
Для запуска добавляем в HTML-файл скрипт запуска нашей основной функции:
<script>
generateMaze(15,15);
</script>
Посмотреть работу на странице проекта.
<!DOCTYPE html>
<html lang="ru">
<head>
<meta charset="UTF-8">
<title>Лабиринт</title>
</head>
<body>
<!-- подготавливаем пустой холст, чтобы работать с ним из скрипта -->
<canvas></canvas>
<!-- скрипт, который создаёт лабиринт -->
<script src="generateMaze.js"> </script>
<script>
generateMaze(15,15);
</script>
</body>
</html>// строим карту нового лабиринта
function generateMaze (columnsNumber, rowsNumber) {
// карта лабиринта, на старте пустая
const map = [];
// сначала заполняем все ячейки карты стенами
for (let y = 0; y < rowsNumber; y++) {
// в цикле создаём сначала пустой массив — строку
const row = [];
// и заполняем её ячейками с пометкой «стена» столько раз, сколько у нас столбцов
for (let x = 0; x < columnsNumber; x++) {
row.push('▉');
};
// как только собрали очередную строку, отправляем её в массив с картой
map.push(row);
}
// функция проверяет чётное число или нет, и если чётное — возвращает true
function isEven (n) {
return n % 2 === 0;
}
// функция возвращает случайный элемент из переданного ей массива
function getRandomFrom (array) {
// получаем случайным образом индекс элемента массива
// число будет в диапазоне от 0 до количества элементов в массиве минус 1
const index = Math.floor(Math.random() * array.length);
// возвращаем элемент массива с полученным случайным индексом
return array[index];
}
// выбираем случайным образом чётные координаты на карте с лабиринтом
const startX = getRandomFrom(Array(columnsNumber).fill(0).map((item, index) => index).filter(x => isEven(x)));
const startY = getRandomFrom(Array(rowsNumber).fill(0).map((item, index) => index).filter(x => isEven(x)));
// трактор, который будет очищать дорожки в лабиринте
var tractor = {};
// ставим его на чётную клетку
tractor.x = startX;
tractor.y = startY;
// функция — записать значение ячейки в карту по координатам
function setField (x, y, value) {
// если координаты выходят за границы карты с лабиринтом
if (x < 0 || x >= columnsNumber || y < 0 || y >= rowsNumber) {
// прекращаем работу функции и возвращаем пустое значение
return null;
};
// если дошли досюда, значит, с координатами всё в порядке, и мы записываем значение ячейки по нашим координатам
map[y][x] = value;
}
// сделаем ячейку, в которой стоит трактор, пустой
setField(startX, startY, ' ');
// функция проверяет, готов лабиринт или ещё нет
// возвращает true, если лабиринт готов; false, если ещё нет
function isMaze () {
// во вложенном цикле проверяем по очереди все ячейки карты
for (let x = 0; x < columnsNumber; x++) {
for (let y = 0; y < rowsNumber; y++) {
// если на чётных местах ещё можно встретить стену,
if (isEven(x) && isEven(y) && getField(x, y) === '▉') {
// то карта с лабиринтом не готова
return false;
}
}
}
// а если мы дошли досюда и функция не прервалась на предыдущей проверке, то лабиринт готов
// рисуем лабиринт в консоли
// переменные для отрисовки строк и границ
var s,d = '';
// рисуем верхнюю границу лабиринта
for (var i = 0; i < columnsNumber; i++) {
d = d + '▉';
}
console.log('▉' + d + '▉');
// рисуем каждую строку
for (var i = 0; i < rowsNumber; i++) {
s = '';
for (var j = 0; j < columnsNumber; j++) {
s = s + map[i][j];
}
console.log('▉' + s + '▉');
}
// рисуем нижнюю границу лабиринта
console.log('▉' + d + '▉');
// сообщаем, что всё готово и выходим из функции
return true;
}
// пока лабиринт не готов, отправляем трактор двигаться дальше
while (!isMaze()) {
moveTractor();
}
// если предыдущий цикл закончился, то заканчиваем общую работу скрипта и возвращаем готовую карту
return map;
// получить значение ячейки из карты по координатам
function getField (x, y) {
// если координаты выходят за границы карты с лабиринтом
if (x < 0 || x >= columnsNumber || y < 0 || y >= rowsNumber) {
// прекращаем работу функции и возвращаем пустое значение
return null;
}
// если дошли досюда, значит, с координатами всё в порядке, и мы возвращаем значение ячейки по нашим координатам
return map[y][x];
}
// двигаем трактор, который расчищает лабиринт
// трактор двигается на 2 клетки, и если вторая клетка — это стена, то очищаем обе
function moveTractor () {
// массив с возможными направлениями трактора
const directs = [];
// если есть место слева
if (tractor.x > 0) {
// помечаем, что можно идти налево
directs.push('left');
};
// если есть место справа
if (tractor.x < columnsNumber - 2) {
// помечаем, что можно идти направо
directs.push('right');
};
// если есть место сверху
if (tractor.y > 0) {
// помечаем, что можно идти наверх
directs.push('up');
};
// если есть место внизу
if (tractor.y < rowsNumber - 2) {
// помечаем, что можно идти вниз
directs.push('down');
};
// случайным образом выбираем направление, в котором можно пойти
const direct = getRandomFrom(directs);
// в зависимости от выбранного направления, обрабатываем клетки
switch (direct) {
case 'left':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x - 2, tractor.y) === '▉') {
setField(tractor.x - 1, tractor.y, ' ');
setField(tractor.x - 2, tractor.y, ' ');
};
// меняем координату трактора
tractor.x -= 2;
break;
case 'right':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x + 2, tractor.y) === '▉') {
setField(tractor.x + 1, tractor.y, ' ');
setField(tractor.x + 2, tractor.y, ' ');
};
// меняем координату трактора
tractor.x += 2;
break;
case 'up':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x, tractor.y - 2) === '▉') {
setField(tractor.x, tractor.y - 1, ' ');
setField(tractor.x, tractor.y - 2, ' ');
};
// меняем координату трактора
tractor.y -= 2
break;
case 'down':
// если через 2 ячейки стена, то очищаем обе
if (getField(tractor.x, tractor.y + 2) === '▉') {
setField(tractor.x, tractor.y + 1, ' ');
setField(tractor.x, tractor.y + 2, ' ');
};
// меняем координату трактора
tractor.y += 2;
break;
}
}
}Что дальше
Мы сделали большую подготовительную работу — получили генератор лабиринтов любой сложности. Но в консоли его проходить неудобно, нужно нарисовать лабиринт красиво на холсте. Этим и займёмся в следующий раз.
