Генератор лабиринтов

Попро­бу­ем сде­лать эле­гант­ную алго­рит­ми­че­скую игруш­ку — лаби­ринт. Сна­ча­ла спе­ци­аль­ный алго­ритм будет рисо­вать для нас слу­чай­ный лаби­ринт, а потом мы сде­ла­ем так, что­бы его мож­но было пройти. 

Что тут будет интересного: 

  • Алго­ритм созда­ния слу­чай­но­го лаби­рин­та. Ока­зы­ва­ет­ся, есть доволь­но про­стые зако­но­мер­но­сти, по кото­рым мож­но сге­не­ри­ро­вать про­хо­ди­мый лабиринт
  • Мно­го вло­жен­ных цик­лов и функ­ций, каж­дая из кото­рых дела­ет что-то про­стое, но вме­сте полу­ча­ет­ся нечто слож­ное и прекрасное

За осно­ву мы возь­мём код Сер­гея Гри­го­ро­ви­ча и адап­ти­ру­ем его под нашу задачу.

Попробуем сделать элегантную алгоритмическую игрушку — лабиринт Мож­но созда­вать лаби­рин­ты любой сте­пе­ни сложности. 

Логика проекта

Изна­чаль­но лаби­ринт пол­но­стью запол­нен сте­на­ми, в нём нет ходов и сво­бод­ных мест. Что­бы внут­ри лаби­рин­та появи­лись марш­ру­ты, по кото­рым мож­но дви­гать­ся, мы запу­стим в лаби­ринт вир­ту­аль­ный трак­тор. Он стар­ту­ет со слу­чай­ной клет­ки и рас­чи­ща­ет лаби­ринт до тех пор, пока он не будет готов.

Что­бы понять, готов лаби­ринт или нет, исполь­зу­ем такое свой­ство лаби­рин­та: если на всех чёт­ных ячей­ках нет стен, зна­чит, этот лаби­ринт мож­но пройти. 

👉 Чёт­ные места — это такие места в лаби­рин­те, кото­рые по оси X и Y одно­вре­мен­но име­ют чёт­ные коор­ди­на­ты. Напри­мер, клет­ка с коор­ди­на­та­ми (2,6) чёт­ная, пото­му что 2 и 6 чёт­ные чис­ла, а с коор­ди­на­та­ми (2,7) — нет.

Подготовка

Про­ект пока будет состо­ять из двух частей:

  1. HTML-файл, где мы сде­ла­ем холст для рисо­ва­ния лаби­рин­та и вызо­вем нуж­ные скрип­ты. Холст сей­час нам не пона­до­бит­ся, но мы под­го­то­вим всё зара­нее для сле­ду­ю­ще­го шага.
  2. Скрипт, кото­рый сге­не­ри­ру­ет лаби­ринт и запи­шет кар­ту лаби­рин­та в отдель­ную переменную.

Даль­ше мы доба­вим скрипт, кото­рый нари­су­ет наш лаби­ринт, а потом научим делать всё остальное.

Сей­час сде­ла­ем первую часть: напи­шем 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];
}

Ставим трактор в лабиринт

Теперь у нас есть всё что нуж­но для уста­нов­ки трак­то­ра. Един­ствен­ное слож­ное место в коде — полу­че­ние стар­то­вых коор­ди­нат. Для это­го мы дела­ем слож­ный трюк:

  1. Пря­мо во вре­мя объ­яв­ле­ния коор­ди­нат по каж­дой оси вызы­ва­ем функ­цию getRandomFrom().
  2. Внут­ри этой функ­ции объ­яв­ля­ем новый мас­сив, кото­рый сра­зу запол­ня­ем чис­ла­ми от 0 до верх­не­го раз­ме­ра нашей кар­ты лабиринта.
  3. Во вре­мя запол­не­ния посто­ян­но про­ве­ря­ем, чёт­ное чис­ло нам попа­лось или нет. Если чёт­ное — кла­дём в новый мас­сив, если нет — не кладём.
  4. В ито­ге у нас полу­чил­ся мас­сив толь­ко из чёт­ных чисел, из кото­ро­го мы и полу­ча­ем слу­чай­ным обра­зом какое-то чис­ло с помо­щью функ­ции 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];
}

Логи­ка рабо­ты трак­то­ра будет такая:

  1. Трак­тор может ходить на две любые клет­ки в любом направ­ле­нии: вверх, вниз, вле­во или вправо.
  2. Если в выбран­ном направ­ле­нии через две клет­ки есть сте­на, то очи­ща­ем обе и меня­ем направ­ле­ние. Если через две клет­ки сте­ны нет, то про­сто меня­ем направление.
  3. Там, где про­шёл трак­тор, появ­ля­ет­ся сво­бод­ное место.

Запи­шем это в виде кода. Выгля­дит гро­мозд­ко, но на самом деле всё про­сто, ком­мен­та­рии помо­гут разобраться.

// двигаем трактор, который расчищает лабиринт
// трактор двигается на 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>

Попробуем сделать элегантную алгоритмическую игрушку — лабиринт Наш лаби­ринт в кон­со­ли браузера. 
Посмот­реть рабо­ту на стра­ни­це проекта.
Готовый код index.html

<!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>

Готовый код generateMaze.js

// строим карту нового лабиринта
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;
		}
	}

}

Что дальше

Мы сде­ла­ли боль­шую под­го­то­ви­тель­ную рабо­ту — полу­чи­ли гене­ра­тор лаби­рин­тов любой слож­но­сти. Но в кон­со­ли его про­хо­дить неудоб­но, нуж­но нари­со­вать лаби­ринт кра­си­во на хол­сте. Этим и зай­мём­ся в сле­ду­ю­щий раз.

Код:

Сер­гей Григорович

Текст:

Миха­ил Полянин

Редак­тор:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Олег Веш­кур­цев