Эта статья — продолжение нашего большого проекта с лабиринтом. Вот что уже сделано:
Но у этих лабиринтов есть две проблемы:
- Непонятно, где в лабиринте вход, а где выход.
- Если задать размер лабиринта больше, чем 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 клеток, то получим такое:
Дело в том, что если у нас чётное количество клеток по какой-то стороне, то вот как ведёт себя алгоритм:
- Нумерация массивов в JavaScript начинается с нуля.
- 40 клеток по горизонтали превращаются в массив от 0 до 39.
- Число 39 — нечётное, значит, клетки с этими координатами не влияют на готовность лабиринта.
- За последней, 39-й, клеткой нет стены, а значит, трактор не может дойти до неё, чтобы расчистить.
- В итоге он оставляет нетронутыми стены в 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);
Ускоряем алгоритм
Так как у нас уже есть скрипт, который рисует лабиринт на странице, то можно сделать так: удалим из функции проверки готовности лабиринта код, который выводит карту в консоль.
Но если мы сделаем только это, то не заметим прироста скорости: в консоль браузер выводит карту только один раз, и это не очень затратная по времени процедура. Намного полезнее будет увеличить количество тракторов на поле, чтобы было так:
- У нас на старте есть много тракторов.
- Все они трактор появятся в случайном чётном месте поля, откуда разъедутся по всей карте.
- Каждый трактор двигается по своим траекториям и не мешает двигаться другим, потому что это просто переменные, а не настоящие тракторы.
- Чем больше тракторов — тем быстрее мы получим готовую карту.
Чтобы работать с большим массивом тракторов, нам нужна отдельная переменная. У нас алгоритм с тракторами находится в файле 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);
Проверка
Чтобы проверить, работает новый алгоритм быстрее или нет, проведите такой тест:
- Установите размер лабиринта 450 на 450 клеток.
- Установите количество тракторов = 1 и запустите страницу (если страница грузится больше двух минут — это нормально, трактор быстрее не может).
- Установите количество тракторов = 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();
Что дальше
А дальше финал — наконец сделаем алгоритм, который нарисует путь от входа до выхода.