dmitmel/maze.js

## maze.js
/*
 * maze.js
 * Written in 2019 by Dmytro Meleshko <dmytro dot meleshko at gmail dot com>
 * To the extent possible under law, the author(s) have dedicated all copyright and related and neighboring rights to this software to the public domain worldwide. This software is distributed without any warranty.
 * You should have received a copy of the CC0 Public Domain Dedication along with this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
 */

// Автор: Дмитрий Мелешко
//
// Задача состоит в написании программы для поиска выхода из лабиринта. Тебе
// надо создать класс Solver, у которого обязательно должен быть хотя бы два
// метода: step и drawState, которые делают следующее:
//
// step:
//   1. Если путь к выходу найден - метод возвращает true
//   2. Иначе он возвращает false и добавляет направление, в которое сейчас надо
//      пойти, в массив stepsToExit
//
//   Направление задаётся строкой 'up' или 'right' или 'down' или 'left'.
//   Следует заметить, что из массива stepsToExit можно удалять сделанные шаги,
//   главное - чтобы когда выход будет найден (когда этот метод вернёт true)
//   этот массив содержал правильную последовательность шагов, которые ведут к
//   выходу.
//
// drawState:
//   Отображает текущее состояние алгоритма поиска пути (очень пригодится для
//   отладки)
//
// Я уже реализовал графику (конкретнее отрисовку лабиринта и пути к выходу),
// некоторые полезные функции для рисования и работы с лабиринтом и генератор
// самих лабиринтов. Перед написанием решения советую просмотреть код,
// отвечающий за графику - я постарался всё детально прокомментировать, чтобы
// был понятен принцип работы моего кода. Код генератора я, напротив, не советую
// читать вначале если ты хочешь полностью придумать алгоритм для поиска выхода
// сам, т.к. использованный мною алгоритм для генерации чем-то напоминает поиск
// выхода (иначе, если тебя интересует именно практическая реализация, смотреть
// можно). Искать алгоритмы для поиска выхода, скажем, в Интернете, не
// запрещено, но опять таки, это зависит от тебя.
//
// Графику я реализовал на HTML5-элементе canvas из-за простоты его
// использования, про который есть хороший туториал на Mozilla Developer Network
// https://developer.mozilla.org/en-US/docs/Web/API/Canvas_API/Tutorial
//
// Код для проверки правильности решения я умышленно не писал для простоты
// написания всей программы и, в частности, решения. Так что для проверки
// правильности твоего решения тебе нужно обратится ко мне и отправить свой код.
//
// В целях соблюдения прозрачности и моих Принципов Программирования, любой код
// этой программы можно менять, если тебе вдруг захочется. Можно даже сказать,
// что такой подход приветствуется, так как я упустил многие фичи для
// упрощения кода. Более того, любой код из этой программы можно копировать без
// моего разрешения и указания моего авторства.
//
// В целом, всё. Надеюсь тебе понравится это инспытание. Удачи!

// Заметки от будущего Меня:
//
// Решение я уже заполнил перед выкладыванием этой программы в Интернет. Для
// запуска нужен вот такой HTML-файл:
/*
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  </head>
  <body style="margin: 0">
    <canvas id="canvas" style="display: block"></canvas>
    <script src="maze.js"></script>
  </body>
</html>
*/
// В целях архивации метаданных прикрепляю вот такой листинг файлов проекта:
/*
drwxr-xr-x dmitmel/dmitmel     0 2019-11-18 09:55 maze/
-rw-r--r-- dmitmel/dmitmel  1211 2019-11-17 13:10 maze/UNLICENSE
-rw-r--r-- dmitmel/dmitmel 22010 2019-11-17 16:11 maze/maze.js
-rw-r--r-- dmitmel/dmitmel   106 2019-11-13 21:26 maze/.eslintrc.yml
-rw-r--r-- dmitmel/dmitmel   135 2019-11-17 13:43 maze/package.json
-rw-r--r-- dmitmel/dmitmel 43089 2019-11-13 17:22 maze/yarn.lock
-rw-r--r-- dmitmel/dmitmel   388 2019-11-18 09:55 maze/maze.html
-rw-r--r-- dmitmel/dmitmel 24048 2019-11-17 16:09 maze/maze.solved.js
-rw-r--r-- dmitmel/dmitmel   968 2019-11-17 16:07 maze/Session.vim
*/
// Удачи, Искатель.

// ===== КОНСТАНТЫ КОНФИГУРАЦИИ ================================================

// размеры лабиринта в комнатах
const MAZE_WIDTH = 20;
const MAZE_HEIGHT = 10;

// размер одной комнаты в пикселях при отрисовке
const ROOM_SIZE = 32;

// цвет стен
const WALL_COLOR = '#000000';
// толщина линии в пикселях, с помощью которой отображается стена (рекомендую
// использовать только чётные значения, т.к. при нечётных картинка выходит
// размытой)
const WALL_LINE_WIDTH = 2;

// цвет пола в обычных комнатах
const ROOM_FLOOR_COLOR = '#ffffff';
// цвет пола стартовой комнаты
const START_ROOM_COLOR = '#ffff00';
// цвет пола комнаты с выходом
const EXIT_ROOM_COLOR = '#00ff00';

// цвет и толщина линии пути к выходу
const PATH_COLOR = '#888888';
// см. комметарий к WALL_LINE_WIDTH про нечётные значения
const PATH_LINE_WIDTH = 4;

// Интервалы в миллисекундах между шагами генератора и решателя лабиринта. Если
// указать 0, то пошаговое вычисление будет выключено и соответствующий алгоритм
// выполнится без задержки, почти моментально.
const GENERATOR_INTERVAL = 0;
const SOLVER_INTERVAL = 50;

// цвет фона
const CANVAS_BACKGROUND_COLOR = '#dddddd';
// отступы в пикселях от краёв к картинке
const CANVAS_PADDING = 32;
// размеры элемента canvas, в котором рисуется графика
const CANVAS_WIDTH = CANVAS_PADDING * 2 + ROOM_SIZE * MAZE_WIDTH;
const CANVAS_HEIGHT = CANVAS_PADDING * 2 + ROOM_SIZE * MAZE_HEIGHT;

// ===== ПОЛЕЗНЫЕ ФУНКЦИИ И КЛАССЫ ОБЩЕГО НАЗНАЧЕНИЯ ===========================

// Генерирует случайное целой число в диапазоне от min до max (включая min, но
// не max).
function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

// Возвращает случайный элемент непустого массива.
function randomElement(array) {
  if (array.length === 0) throw new Error('expected a non-empty array');
  return array[randomInt(0, array.length)];
}

// Двух-мерный массив, по сути - сетка. На самом деле реализован на одномерном
// массиве, но это скрытые детали реализации (методы, начинающиеся с нижнего
// подчёркивания являются скрытыми и к использованию не рекомендуются).
class Array2D {
  constructor(width, height, defaultValue) {
    this.width = width;
    this.height = height;
    // создаём массив с заданой длинной, т.к. она не будет менятся
    this._data = new Array(width * height);
    for (let i = 0; i < this._data.length; i++) this._data[i] = defaultValue;
  }

  get(x, y) {
    return this._data[this._index(x, y)];
  }

  set(x, y, value) {
    this._data[this._index(x, y)] = value;
  }

  // Возвращает индекс, который используется для адресации элементов по
  // координатам внутри одномерного массива, который хранит все данные.
  _index(x, y) {
    this._checkCoordinates(x, y);
    return y * this.width + x;
  }

  // Возвращает объект со свойствами top, right, bottom и left, которые
  // соответствуют соседям ячейки с задаными координатами. Если какого-то соседа
  // нету (например, если указаны координаты ячейки возле какой-то границы) -
  // то вместо его значения будет записан null.
  getNeighbors(x, y) {
    this._checkCoordinates(x, y);
    return {
      top: y > 0 ? this.get(x, y - 1) : null,
      right: x + 1 < this.width ? this.get(x + 1, y) : null,
      bottom: y + 1 < this.height ? this.get(x, y + 1) : null,
      left: x > 0 ? this.get(x - 1, y) : null,
    };
  }

  // Проверяет, находятся ли координаты внутри размеров этого массива.
  _checkCoordinates(x, y) {
    if (!(x >= 0 && x < this.width))
      throw new RangeError(`x: ${x}, width: ${this.width}`);
    if (!(y >= 0 && y < this.height))
      throw new RangeError(`y: ${y}, height: ${this.height}`);
  }
}

// ===== ДАННЫЕ ЛАБИРИНТА И ФУНКЦИИ ДЛЯ РАБОТЫ С НИМ ===========================

let startRoomX = 0;
let startRoomY = 0;

let exitRoomX = MAZE_WIDTH - 1;
let exitRoomY = MAZE_HEIGHT - 1;

// Лабиринт сохраняется не как один двухмерный массив, а как два таких массива
// для вертикальных и горизонтальных стен. Стены сохраняются в виде логических
// значений - если стена есть, то true, иначе - false. С этими массивами
// напрямую работать не прийдётся, я реализовал парочку вспомагательных функций.
let verticalWalls = new Array2D(MAZE_WIDTH - 1, MAZE_HEIGHT, true);
let horizontalWalls = new Array2D(MAZE_WIDTH, MAZE_HEIGHT - 1, true);

// Выщеупомянутый массив с шагами к выходу, который надо заполнить
// направлениями, которые обозначаются строками 'up', 'right', 'down' и 'left'.
let stepsToExit = [];

// Возвращает объект со свойствами top, right, bottom и left, которые
// соответствуют стенам комнаты с задаными координатами. Если комната находится
// возле границы лабиринта, то вернётся значения true (так как сбежать из
// лабиринта так нельзя).
function getRoomWalls(x, y) {
  return {
    top: y === 0 || horizontalWalls.get(x, y - 1),
    right: x === MAZE_WIDTH - 1 || verticalWalls.get(x, y),
    bottom: y === MAZE_HEIGHT - 1 || horizontalWalls.get(x, y),
    left: x === 0 || verticalWalls.get(x - 1, y),
  };
}

// Изменяет стены комнаты с задаными комментариями. Новые значения передаются в
// объекте. Если свойство для значения какой-то стены отсутствует, равно null
// или эта стена является границей лабиринта, находящейся возле комнаты - то оно
// просто будет проигнорировано.
function changeRoomWalls(x, y, walls) {
  if (walls.top != null && y > 0) {
    horizontalWalls.set(x, y - 1, walls.top);
  }
  if (walls.right != null && x < MAZE_WIDTH - 1) {
    verticalWalls.set(x, y, walls.right);
  }
  if (walls.bottom != null && y < MAZE_HEIGHT - 1) {
    horizontalWalls.set(x, y, walls.bottom);
  }
  if (walls.left != null && x > 0) {
    verticalWalls.set(x - 1, y, walls.left);
  }
}

// ===== ГРАФИКА ===============================================================

// фаза анимации, строка 'generating' либо 'solving'
let animationPhase = 'generating';
let generator;
let solver;

// следующая строка нужна для указания типа переменной, чтобы Visual Studio Code
// дал автокомплишен для переменных canvas и ctx
/** @type {HTMLCanvasElement} */
let canvas = document.getElementById('canvas');
canvas.width = CANVAS_WIDTH;
canvas.height = CANVAS_HEIGHT;
// контекст, в котором и рисуется графика
let ctx = canvas.getContext('2d');

// Эта функция рисует один кадр анимации.
function draw() {
  // очищаем canvas
  ctx.fillStyle = CANVAS_BACKGROUND_COLOR;
  ctx.fillRect(0, 0, canvas.width, canvas.height);

  // Графический контекст позволяет применять разные трансформации, которые
  // хранятся в матрице (см. https://habr.com/ru/post/131931/) внутри контекста,
  // типа перемещения (ctx.translate), изменения размера (ctx.scale) и вращения
  // (ctx.rotate). Для упрощения кода я буду ими очень часто пользоватся.
  // Функции ctx.save и ctx.restore сохраняют и восстанавливают состояние этой
  // матрицы.
  ctx.save();
  // перемещаем всю графику на отступ
  ctx.translate(CANVAS_PADDING, CANVAS_PADDING);

  drawRooms();

  if (animationPhase === 'generating') {
    generator.drawState();
  } else if (animationPhase === 'solving') {
    solver.drawState();
  }

  drawStepsToExit();

  drawWalls();

  // возобнавляем состояние матрицы, чтобы оно не ломало следующие кадры
  ctx.restore();
}

function drawRooms() {
  for (let y = 0; y < MAZE_HEIGHT; y++) {
    for (let x = 0; x < MAZE_WIDTH; x++) {
      let floorColor = ROOM_FLOOR_COLOR;
      if (x === startRoomX && y === startRoomY) floorColor = START_ROOM_COLOR;
      else if (x === exitRoomX && y === exitRoomY) floorColor = EXIT_ROOM_COLOR;
      drawRoom(x, y, floorColor);
    }
  }
}

// Эта функция сделана для быстрого рисования в drawState у Solver и Generator.
function drawRoom(x, y, floorColor, alpha = 1) {
  ctx.save();
  ctx.scale(ROOM_SIZE, ROOM_SIZE);
  ctx.globalAlpha = alpha;
  ctx.fillStyle = floorColor;
  ctx.fillRect(x, y, 1, 1);
  ctx.restore();
}

function drawStepsToExit() {
  // зачем рисовать пустой путь?
  if (stepsToExit.length < 1) return;

  // путь рисуется за один вызов функции ctx.stroke() вконце этой
  ctx.beginPath();
  ctx.save();
  ctx.scale(ROOM_SIZE, ROOM_SIZE);
  // перемещаемся на полкомнаты для того, чтобы рисовать путь посредине
  ctx.translate(0.5, 0.5);

  let currentX = startRoomX;
  let currentY = startRoomY;
  ctx.moveTo(currentX, currentY);
  for (let i = 0; i < stepsToExit.length; i++) {
    let step = stepsToExit[i];
    if (step === 'up') currentY--;
    if (step === 'right') currentX++;
    if (step === 'down') currentY++;
    if (step === 'left') currentX--;
    ctx.lineTo(currentX, currentY);
  }

  // восстановка контекста происходит до отрисовки для того, чтобы матрица
  // влияла только на координаты узлов пути, а не на толщины линий
  ctx.restore();
  ctx.strokeStyle = PATH_COLOR;
  ctx.lineWidth = PATH_LINE_WIDTH;
  ctx.stroke();
}

function drawWalls() {
  // все стены тоже рисуются за один вызов ctx.stroke()
  ctx.beginPath();
  ctx.save();
  ctx.scale(ROOM_SIZE, ROOM_SIZE);
  ctx.rect(0, 0, MAZE_WIDTH, MAZE_HEIGHT);

  for (let y = 0; y < MAZE_HEIGHT; y++) {
    for (let x = 0; x < MAZE_WIDTH; x++) {
      if (x < MAZE_WIDTH - 1 && verticalWalls.get(x, y)) {
        // вертикальныя стена справа от текущей комнаты
        ctx.moveTo(x + 1, y);
        ctx.lineTo(x + 1, y + 1);
      }
      if (y < MAZE_HEIGHT - 1 && horizontalWalls.get(x, y)) {
        // вертикальныя стена внизу от текущей комнаты
        ctx.moveTo(x, y + 1);
        ctx.lineTo(x + 1, y + 1);
      }
    }
  }

  // история с трансформациями таже самая, что и в drawStepsToExit
  ctx.restore();
  ctx.strokeStyle = WALL_COLOR;
  ctx.lineWidth = WALL_LINE_WIDTH;
  ctx.stroke();
}

// ===== АЛГОРИТМ ГЕНЕРАЦИИ ЛАБИРИНТОВ =========================================

// см. https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search
class DepthFirstGenerator {
  constructor() {
    this.headX = startRoomX;
    this.headY = startRoomY;
    this.stack = [];
    this.visitedRooms = new Array2D(MAZE_WIDTH, MAZE_HEIGHT, false);
    this.visitedRooms.set(this.headX, this.headY, true);
  }

  _pushHeadPosition() {
    this.stack.push({ x: this.headX, y: this.headY });
  }

  _popHeadPosition() {
    let pos = this.stack.pop();
    this.headX = pos.x;
    this.headY = pos.y;
  }

  drawState() {
    for (let y = 0; y < MAZE_HEIGHT; y++) {
      for (let x = 0; x < MAZE_WIDTH; x++) {
        if (!this.visitedRooms.get(x, y)) drawRoom(x, y, 'red', 0.1);
      }
    }

    drawRoom(this.headX, this.headY, 'blue', 0.5);
  }

  step() {
    let possibleDirections = this._getPossibleDirections();
    if (possibleDirections.length > 0) {
      let direction = randomElement(possibleDirections);
      this._pushHeadPosition();
      this._breakWallInDirection(direction);
      this._moveInDirection(direction);
      this.visitedRooms.set(this.headX, this.headY, true);
      return false;
    } else if (this.stack.length > 0) {
      this._popHeadPosition();
      return false;
    } else {
      return true;
    }
  }

  _getPossibleDirections() {
    let ns = this.visitedRooms.getNeighbors(this.headX, this.headY);

    let dirs = [];
    if (ns.top != null && !ns.top) dirs.push('up');
    if (ns.right != null && !ns.right) dirs.push('right');
    if (ns.bottom != null && !ns.bottom) dirs.push('down');
    if (ns.left != null && !ns.left) dirs.push('left');

    return dirs;
  }

  _breakWallInDirection(dir) {
    // честно говоря, при написании этой функции я вспомнил один момент из
    // CrossCode (см. https://www.youtube.com/watch?v=ki78r_ep9pI) из, наверное,
    // самой крутой части игры
    let walls = {};
    if (dir === 'up') walls.top = false;
    else if (dir === 'right') walls.right = false;
    else if (dir === 'down') walls.bottom = false;
    else if (dir === 'left') walls.left = false;
    changeRoomWalls(this.headX, this.headY, walls);
  }

  _moveInDirection(dir) {
    if (dir === 'up') this.headY--;
    if (dir === 'right') this.headX++;
    if (dir === 'down') this.headY++;
    if (dir === 'left') this.headX--;
  }
}

// ===== АЛГОРИТМ ПОИСКА ПУТИ В ЛАБИРИНТЕ ======================================

// см. https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search
// этот алгоритм подходит не только для генерации, но и для решения лабиринтов
class Solver {
  constructor() {
    this.headX = startRoomX;
    this.headY = startRoomY;
    this.stack = [];
    this.visitedRooms = new Array2D(MAZE_WIDTH, MAZE_HEIGHT, false);
    this.visitedRooms.set(this.headX, this.headY, true);
  }

  _pushHeadPosition() {
    this.stack.push({ x: this.headX, y: this.headY });
  }

  _popHeadPosition() {
    let pos = this.stack.pop();
    this.headX = pos.x;
    this.headY = pos.y;
  }

  drawState() {
    for (let y = 0; y < MAZE_HEIGHT; y++) {
      for (let x = 0; x < MAZE_WIDTH; x++) {
        if (!this.visitedRooms.get(x, y)) drawRoom(x, y, 'red', 0.1);
      }
    }

    drawRoom(this.headX, this.headY, 'blue', 0.5);
  }

  step() {
    if (this.headX === exitRoomX && this.headY === exitRoomY) return true;

    let possibleDirections = this._getPossibleDirections();
    if (possibleDirections.length > 0) {
      let direction = randomElement(possibleDirections);
      this._pushHeadPosition();
      this._moveInDirection(direction);
      this.visitedRooms.set(this.headX, this.headY, true);
      stepsToExit.push(direction);
      return false;
    } else if (this.stack.length > 0) {
      this._popHeadPosition();
      stepsToExit.pop();
      return false;
    } else {
      return false;
    }
  }

  _getPossibleDirections() {
    let vrs = this.visitedRooms.getNeighbors(this.headX, this.headY);
    let walls = getRoomWalls(this.headX, this.headY);

    let dirs = [];
    if (vrs.top != null && !vrs.top && !walls.top) dirs.push('up');
    if (vrs.right != null && !vrs.right && !walls.right) dirs.push('right');
    if (vrs.bottom != null && !vrs.bottom && !walls.bottom) dirs.push('down');
    if (vrs.left != null && !vrs.left && !walls.left) dirs.push('left');

    return dirs;
  }

  _moveInDirection(dir) {
    if (dir === 'up') this.headY--;
    if (dir === 'right') this.headX++;
    if (dir === 'down') this.headY++;
    if (dir === 'left') this.headX--;
  }
}

// ===== ЗАПУСК АНИМАЦИИ!!! ====================================================

generator = new DepthFirstGenerator();
solver = new Solver();

// Вызывает функцию callback с переодичностью в миллисекундах interval
// (setInterval с блэкджеком и некоторыми дополнительными фичами). Если interval
// равен 0, то используется не setInterval, а обычный цикл (т.е. задача
// выполняется моментально, без задержек). Когда callback возвращает правдивое
// значение - задача останавливается и вызывается функция onFinished.
function runRepeatedTask(interval, callback, onFinished) {
  if (interval > 0) {
    let intervalId = setInterval(function tick() {
      let finished = callback();
      if (finished) {
        clearInterval(intervalId);
        onFinished();
      }
    }, interval);
  } else {
    let finished;
    do finished = callback();
    while (!finished);
    onFinished();
  }
}

function startGenerator() {
  animationPhase = 'generating';
  runRepeatedTask(
    GENERATOR_INTERVAL,
    function generatorStep() {
      return generator.step();
    },
    function onFinishedGenerating() {
      console.log('finished generating');
      startSolver();
    },
  );
}

function startSolver() {
  animationPhase = 'solving';
  runRepeatedTask(
    SOLVER_INTERVAL,
    function solverStep() {
      return solver.step();
    },
    function onFinishedSolving() {
      console.log('finished solving');
      finishAnimation();
    },
  );
}

function finishAnimation() {
  console.log('steps to exit', stepsToExit);
  animationPhase = 'finished';
}

// погнали!!!
startGenerator();
// requestAnimationFrame вызывает функцию примерно 60 раз в секунду (реже, если
// не успевает) для синхронизации с внутрибраузерными процессами и частотой
// обновления монитора, сделан и идеально подходит для рендеринга графики.
requestAnimationFrame(function onAnimationFrame() {
  draw();
  requestAnimationFrame(onAnimationFrame);
});