Gaze path find

gaze-path-find.ts

type MazeNode = '.' | '#';

interface PathNode {
  x: number,
  y: number
}

type Direction = 'top' | 'right' | 'bottom' | 'left';

/**
 * @param maze - x * x matrix
 * @param exit - optional - exit node from maze
 *  */
function findMazePath(maze: MazeNode[][], exit: PathNode = {x: maze.length - 1, y: maze.length - 1}) {
  const path: PathNode[] = []

  if (exit.y > maze.length || exit.x > maze[exit.y].length)
    throw new RangeError('Exit is outside of maze');

  // Если начало или выход - стена
  if (maze[0][0] === '#' || maze[exit.y][exit.x] === '#') return path;

  // 1. Зададим начальную позицию и направление движения
  let cursor: PathNode = {
    x: 0,
    y: 0
  }

  let direction: Direction = 'bottom';

  function rotate(direction: Direction, by: 'clockwise' | 'counter-clockwise') {
    function clamp(idx: number, arr: unknown[]) {
      return idx === -1
        ? arr.length - 1
        : idx > arr.length - 1
          ? 0
          : idx;
    }

    const dirs: Direction[] = ['top', 'right', 'bottom', 'left'];

    const shift = by === 'clockwise' ? 1 : -1

    const nextIdx = clamp(dirs.indexOf(direction) + shift, dirs);

    return dirs[nextIdx];
  }

  function move(direction: Direction, cursor: PathNode) {
    return {
      x: direction === 'left' ? cursor.x - 1 : direction === 'right' ? cursor.x + 1 : cursor.x,
      y: direction === 'top' ? cursor.y - 1 : direction === 'bottom' ? cursor.y + 1 : cursor.y
    }
  }

  function isWall(maze: MazeNode[][], cursor: PathNode) {
    const endIdx = maze.length - 1;
    const isOutside = cursor.x < 0 || cursor.y < 0 || cursor.x > endIdx || cursor.y > endIdx;
    return isOutside || maze[cursor.y][cursor.x] === '#';
  }

  do {
    // 2. Запоминаем текущую пройденную позицию
    path.push(cursor);
    // 3. Поворачиваем на 90 градусов против часовой стрелки
    direction = rotate(direction, 'counter-clockwise');

    let next = move(direction, cursor);

    // 4. Проверяем, что находится впереди - если это стена, поворачиваем по часовой стрелке и повторяем пункт 4
    // Прерываем цикл после 4 поворотов, во избежание infinite loop - если начальная позиция окружена стенами
    let rotatesCount = 0;
    while (isWall(maze, next)) {
      if (rotatesCount > 3) break;

      direction = rotate(direction, 'clockwise');
      next = move(direction, cursor);

      rotatesCount++;
    }

    // 5. Переходим на новое место
    cursor = next;

    // 6. По истории всех посещённых ячеек проверяем, были ли мы уже здесь
    const currentIdx = path.findIndex(node => node.x === cursor.x && node.y === cursor.y);

    // Если были - удаляем из истории посещения все записи от последней до текущей ячейки включительно
    if (currentIdx !== -1) {
      path.splice(currentIdx, path.length - currentIdx);
    }

    // 7. Проверяем, является ли текущая позиция точкой выхода
    // Если является - добавляем в путь и прерываем поиск, если нет, то повторяем с шага 2
    if (cursor.x === exit.x && cursor.y === exit.y) {
      path.push(cursor);
      break;
    }
  } while (path.length > 0);

  return path;
}

// tests
function print(maze: MazeNode[][], path: PathNode[] = []) {
  const rowPrints = maze.map((row, y) => {
    return row.reduce((rp, el, x) => {
      if (path.some(node => node.y === y && node.x === x)) {
        return rp + '  ' + `$`;
      }

      return rp + '  ' + el;
    }, '');
  })

  const matrix = rowPrints.join('\n\r');

  console.log(matrix)
}

function generate(n: number, proportion: number = 0.3) {
  const maze: MazeNode[][] = [];

  for (let y = 0; y < n; y++) {
    const row: MazeNode[] = [];

    for (let x = 0; x < n; x++) {
      row.push(Math.random() < proportion ? '#' : '.')
    }

    maze.push(row);
  }

  return maze;
}

const maze = generate(10);
const path = findMazePath(maze);
print(maze, path);