Прокачиваем генератор лабиринтов: оптимизируем код и добавляем выходы
hard

Прокачиваем генератор лабиринтов: оптимизируем код и добавляем выходы

Для тех, кто соскучился по серьёзному программированию

Эта статья — продолжение нашего большого проекта с лабиринтом. Вот что уже сделано:

Но у этих лабиринтов есть две проблемы:

  1. Непонятно, где в лабиринте вход, а где выход.
  2. Если задать размер лабиринта больше, чем 150 на 150 клеток, то алгоритм надолго задумается и страница будет грузиться долго.

Сегодня исправим обе.

Делаем вход и выход

У нашего лабиринта есть свойство чётности — это значит, что у него свободны все ячейки с обеими чётными координатами. Например, ячейка (0, 0) свободна, потому что каждая координата делится на 2 без остатка, а ячейка (5, 6) может быть со стеной, а может быть и нет, заранее неизвестно. Мы используем это свойство, чтобы сделать вход и выход в лабиринте.

Начнём со входа. Левый верхний угол лабиринта, не считая рамки, имеет координату (0, 0) — это значит, что эта ячейка точно свободна. А раз так, то мы можем сделать вход прямо над ней. Для этого достаточно нарисовать белый прямоугольник точно над этой клеткой.

Сделаем для этого новую функцию drawExit(), добавим её вызов в самый конец файла drawMaze.js и напишем внутри этой функции простой код:

// рисуем вход и выход из лабиринта
function drawExit() {
	// берём белый цвет
	context.fillStyle = 'white';
	// начинаем рисовать новую фигуру
	context.beginPath();
	// рисуем белый прямоугольник над первой ячейкой лабиринта
	context.rect(padding, 0, fieldSize, padding);
	// закрашиваем его белым
	context.fill();
}
Прокачиваем генератор лабиринтов
У лабиринта появился вход, но пока нет выхода

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

// берём белый цвет
context.fillStyle = 'white';
// начинаем рисовать новую фигуру
context.beginPath();
// рисуем белый прямоугольник под последней ячейкой лабиринта
context.rect((columnsSize - 1) * fieldSize + padding, rowsSize * fieldSize + padding, fieldSize, padding);
// закрашиваем его белым
context.fill();

Но этот код работает, только когда у нас в лабиринте нечётное количество строк по вертикали и горизонтали. Если поставим размер лабиринта 40 на 40 клеток, то получим такое:

Прокачиваем генератор лабиринтов

Дело в том, что если у нас чётное количество клеток по какой-то стороне, то вот как ведёт себя алгоритм:

  1. Нумерация массивов в JavaScript начинается с нуля.
  2. 40 клеток по горизонтали превращаются в массив от 0 до 39.
  3. Число 39 — нечётное, значит, клетки с этими координатами не влияют на готовность лабиринта.
  4. За последней, 39-й, клеткой нет стены, а значит, трактор не может дойти до неё, чтобы расчистить.
  5. В итоге он оставляет нетронутыми стены в 39-м ряду и в 39-й строке.

Решение — добавить проверку на чётность размеров и ввести дополнительный параметр сдвига. Если у лабиринта чётное количество клеток по вертикали или горизонтали, мы пропорционально увеличиваем размер нашего выхода.

Сначала добавим в самое начало скрипта две переменные — они будут отвечать за сдвиг:

// переменные сдвига
var shiftX = 0;
var shiftY = 0;

Теперь сделаем проверку на чётность: если у нас чётная координата, то сдвиг по этой координате будет равен размеру клетки:

// считаем размеры сдвига
if (columnsSize % 2 == 0) {shiftX = fieldSize};
if (rowsSize % 2 == 0) {shiftY = fieldSize};

А теперь добавляем значение этого сдвига в команде, которая рисует выход:

context.rect((columnsSize - 1) * fieldSize + padding - shiftX, rowsSize * fieldSize + padding - shiftY, fieldSize, padding + shiftY);
Прокачиваем генератор лабиринтов
Теперь у лабиринта есть и вход, и выход. Можно искать путь.

Ускоряем алгоритм

Так как у нас уже есть скрипт, который рисует лабиринт на странице, то можно сделать так: удалим из функции проверки готовности лабиринта код, который выводит карту в консоль. 

Но если мы сделаем только это, то не заметим прироста скорости: в консоль браузер выводит карту только один раз, и это не очень затратная по времени процедура. Намного полезнее будет увеличить количество тракторов на поле, чтобы было так:

  1. У нас на старте есть много тракторов.
  2. Все они трактор появятся в случайном чётном месте поля, откуда разъедутся по всей карте.
  3. Каждый трактор двигается по своим траекториям и не мешает двигаться другим, потому что это просто переменные, а не настоящие тракторы.
  4. Чем больше тракторов — тем быстрее мы получим готовую карту.

Чтобы работать с большим массивом тракторов, нам нужна отдельная переменная. У нас алгоритм с тракторами находится в файле generateMaze.js, а внутри него есть функция generateMaze() — запишем новую переменную в начале этой функции вместо переменной с одним трактором:

// тракторы, которые будут очищать дорожки в лабиринте
var tractors = []

Точно так же заменим установку одного трактора по случайным координатам на установку множества тракторов в то же самое место:

// создаём тракторы
for (let i = 0; i < tractorsNumber; i++) {
	// пока они не закончились — отправляем в массив с тракторами пары случайных координат для старта
	tractors.push({ x: getRandomFrom(Array(columnsNumber).fill(0).map((item, index) => index).filter(x => isEven(x))), y: startY });
	console.log(startX + ' ' + startY);
}

Сейчас в цикле у нас есть переменная tractorsNumber, которая пока нигде не объявлена. Добавим её в описание функции, чтобы при вызове мы получали и количество тракторов:

function generateMaze (columnsNumber, rowsNumber, tractorsNumber) {

Последнее, что нам осталось сделать, — в функцию moveTractor() добавить цикл, который будет отвечать за движение всех тракторов. Для этого мы пойдём на хитрость: организуем такой цикл for, в котором он сам выяснит, сколько у него тракторов, и будет работать с каждым по отдельности.

// перебираем в цикле все тракторы из массива
for (const tractor of tractors) {
  // здесь — всё прошлое содержимое функции
}

Обновляем вызов функции generateMaze()

Раз мы добавили параметр tractorsNumber в описание функции generateMaze(), то теперь нам нужно поправить скрипт drawMaze.js. Ставим нужное количество тракторов — например 50 — и добавляем эту переменную в вызов функции:

// количество тракторов
const tractorsNumber = 50;
// создаём новую карту лабиринта, которую будем отрисовывать
const map = generateMaze(columnsSize, rowsSize, tractorsNumber);

Проверка

Чтобы проверить, работает новый алгоритм быстрее или нет, проведите такой тест: 

  1. Установите размер лабиринта 450 на 450 клеток.
  2. Установите количество тракторов = 1 и запустите страницу (если страница грузится больше двух минут — это нормально, трактор быстрее не может).
  3. Установите количество тракторов = 500, обновите страницу и почувствуйте разницу.

Открыть лабиринт 450 на 450 с одним трактором.

Открыть лабиринт 450 на 450 с 500 тракторами.

// строим карту нового лабиринта
function generateMaze (columnsNumber, rowsNumber, tractorsNumber) {
	// карта лабиринта, на старте пустая
	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 tractors = []

	// создаём тракторы
	for (let i = 0; i < tractorsNumber; i++) {
		// пока они не закончились — отправляем в массив с тракторами пары случайных координат для старта
		tractors.push({ x: startX, 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;
				}
			}
		}
		// а если мы дошли до сюда и функция не прервалась на предыдущей проверке, то лабиринт готов
		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 () {
		// перебираем в цикле все тракторы из массива
		for (const tractor of tractors) {
			// массив с возможными направлениями трактора
			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;
			}
		}
	}

}

// количество колонок в лабиринте
const columnsSize = 450;
// количество строк в лабиринте
const rowsSize = 450;
// размер клетки в лабиринте
const fieldSize = 7;
 // рамка (внешняя граница лабиринта)
const padding = 10;


// находим холст на странице по имени элемента
const canvas = document.querySelector('canvas');
// создаём переменную, через которую будем работать с холстом
const context = canvas.getContext('2d');

// количество тракторов
const tractorsNumber = 50;
// создаём новую карту лабиринта, которую будем отрисовывать
const map = generateMaze(columnsSize, rowsSize, tractorsNumber);

// переменные сдвига
var shiftX = 0;
var shiftY = 0;

// рисуем рамку и готовимся к отрисовке лабиринта
function init () {
	// устанавливаем размеры холста
	canvas.width = padding * 2 + columnsSize * fieldSize;
	canvas.height = padding * 2 + rowsSize * fieldSize;

	// цвет заливки
	context.fillStyle = 'black';
	// рисуем прямоугольник на весь холст с координатами левого верхнего и правого нижнего углов
	context.rect(0, 0, canvas.width, canvas.height);
	// закрашиваем его выбранным цветом
	context.fill();

	// делаем белое поле внутри рамки, чтобы потом нарисовать на нём стены
	context.fillStyle = 'white';
	// сообщаем скрипту, что сейчас будем рисовать новую фигуру
	context.beginPath();
	// рисуем прямоугольник, отступив от границ холста на толщину рамки
	context.rect(padding, padding, canvas.width - padding * 2, canvas.height - padding * 2);
	// закрашиваем его белым 
	context.fill();
}


// получаем значение ячейки из лабиринта
function getField (x, y) {
	// если хотя бы одна из координат не находится в границах карты
	if (x < 0 || x >= columnsSize || y < 0 || y >= rowsSize) {
		// выходим из функции и говорим, что такой ячейки нет
		return null;
	}
	// если дошли до сюда, значит координата верная и мы возвращаем её значение из карты лабиринта
	return map[y][x];
}

// отрисовываем карту
function drawMap () {
	// обрабатываем по очереди все ячейчки в каждом столбце и строке
	for (let x = 0; x < columnsSize; x++) {
		for (let y = 0; y < rowsSize; y++) {
			// если на карте лабиринта эта ячейка помечена как стена
			if (getField(x, y) === '▉') {
				// берём чёрный цвет
				context.fillStyle = 'black';
				// начинаем рисовать новую фигуру
				context.beginPath();
				// делаем прямоугольник на месте этой ячейки
				context.rect(padding + x * fieldSize, padding + y * fieldSize, fieldSize, fieldSize);
				// закрашиваем его чёрным
				context.fill();
			}
		}
	}
}

// рисуем вход и выход из лабиринта
function drawExit() {
	// берём белый цвет
	context.fillStyle = 'white';
	// начинаем рисовать новую фигуру
	context.beginPath();
	// рисуем белый прямоугольник над первой ячейкой лабиринта
	context.rect(padding, 0, fieldSize, padding);
	// закрашиваем его белым
	context.fill();

	// берём белый цвет
	context.fillStyle = 'white';
	// начинаем рисовать новую фигуру
	context.beginPath();

	// считаем размеры сдвига
	if (columnsSize % 2 == 0) {shiftX = fieldSize};
	if (rowsSize % 2 == 0) {shiftY = fieldSize};

	// рисуем белый прямоугольник под последней ячейкой лабиринта
	context.rect((columnsSize - 1) * fieldSize + padding - shiftX, rowsSize * fieldSize + padding - shiftY, fieldSize, padding + shiftY);
	// закрашиваем его белым
	context.fill();

}

// рисуем рамку и готовимся к отрисовке лабиринта
init();
// рисуем лабиринт
drawMap();
// делаем вход и выход из лабиринта
drawExit();

Что дальше

А дальше финал — наконец сделаем алгоритм, который нарисует путь от входа до выхода.

Текст и код:

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

Обложка:

Алексей Сухов

Корректор:

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

Вёрстка:

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

Соцсети:

Юлия Зубарева

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Вам может быть интересно
hard