Генерация лабиринтов: DFS, рандомизированные Прим и Краскал

Лабиринт — это остовное дерево

Представьте клетки вершинами, а внутренние стены — возможными рёбрами. Удаление стены добавляет проход. Каждый генератор соединяет все клетки без циклов: между любыми двумя получается ровно один маршрут. Такой лабиринт называют совершенным. Для N клеток нужно N−1 проходов. В примере внешние стены остаются закрытыми: генерация не требует рисовать вход или искать выход.

По умолчанию сетка 9×7: 63 клетки и 110 внутренних стен. В каждом готовом лабиринте открыты 62 стены. Порядок и рисунок проходов могут отличаться, но связность и отсутствие циклов выполняются у всех трёх результатов.

DFS: продолжать текущую ветку

Начинаем с левой верхней клетки. Случайно выбираем ещё не посещённого соседа, открываем стену и кладём новую клетку в стек. Если непосещённых соседей нет, снимаем клетку со стека и возвращаемся к предыдущей. В этом сравнении останавливаем генерацию, как только соединили все клетки: окончательное опустошение стека уже не изменит лабиринт.

Синие проходы показывают построенное дерево, яркая ветка — текущий стек. После возврата исчерпанная ветка сразу тускнеет. Такое правило часто даёт длинные извилистые ветки, но конкретный seed не задаёт свойство всех лабиринтов. Здесь выбираем из непосещённых соседей; тот же seed не обязан повторять отдельную страницу DFS с перемешиванием направлений.

Рандомизированный Прим: выбирать на всей границе

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

Это вариант со случайным выбором на границе: числовые веса здесь не минимизируются. Назначить каждому ребру фиксированный случайный вес и запустить обычного Прима — другой эксперимент. Генератор сохраняет одну связанную растущую область и может продолжать её из разных мест границы.

Рандомизированный Краскал: соединять компоненты

Сначала каждая клетка — отдельная компонента. Один раз перемешиваем все внутренние стены алгоритмом Фишера — Йетса. Просматриваем этот порядок: удаляем стену, только если клетки принадлежат разным компонентам, и объединяем их. Внутри одной компоненты стену оставляем, иначе появится цикл. Такой пропуск отмечен красным ×. После N−1 проходов останавливаемся.

Зелёные фрагменты проходов могут возникать далеко друг от друга: это разные деревья одного растущего леса. У Краскала нет стартовой клетки и единой границы роста. Связность отслеживает система непересекающихся множеств с объединением по размеру и сжатием путей.

Как читать одновременные шаги

В каждом раунде вместе выбираем по одному действию незавершённых алгоритмов, затем вместе применяем решения. Возврат DFS, новый проход и отброшенная стена — разные действия; одинаковые такты анимации не означают одинаковое число вычислений. Готовый генератор удерживает итог, пока остальные заканчивают.

Размер и seed общие, но каждый метод получает отдельный экземпляр воспроизводимого генератора случайных чисел. Алгоритмы по-разному расходуют его значения. Одинаковый seed означает повторяемость каждой версии, а не одинаковые решения или равномерную выборку остовов. Ссылка сохраняет также версию генераторов, такт и скорость; чистая страница открывается на паузе.

Что сравнивать в готовом лабиринте

Проходы — число открытых внутренних стен. В компоненты входят и ещё изолированные клетки, поэтому на всём построении их число равно N минус число принятых проходов. Тупик готового лабиринта имеет ровно один проход, развилка — не менее трёх. У лабиринта из одной клетки нет проходов, тупиков и развилок.

Для сетки 9×7 с seed 34 у DFS получилось 8 тупиков и 6 развилок, у Прима — 23 и 20, у Краскала — 20 и 17. Меняйте seed и сравнивайте несколько законченных лабиринтов. Счётчики описывают конкретные образцы, а не универсальный рейтинг или сложность прохождения. Эти варианты генерации не обещают равномерного распределения по всем возможным совершенным лабиринтам.

Время, память и исполняемый код

Пусть N — число клеток, E — число внутренних стен; в прямоугольной сетке E<2N. Без хранения истории эти DFS и Прим требуют O(N+E) времени и памяти. Каждая стена попадает в список Прима не более одного раза. У Краскала амортизированное время O(N+E·α(N)), включая перемешивание за O(E), память O(N+E). Сортировки по весу в этой случайной версии нет.

Плеер дополнительно копирует O(N+E) данных в снимок каждого действия. Для O(N+E) действий сохранённая история требует O((N+E)²) памяти и времени копирования, в отличие от кода получения результата ниже. Поэтому интерфейс ограничен 225 клетками. Экспорт использует те же снимки и отрисовку: сохраняется полный проход с начала на выбранной скорости, без звука.

function generateMaze(width, height, seed, method) {
  const n = width * height;
  if (!Number.isInteger(width) || !Number.isInteger(height) ||
      width < 1 || width > 21 || height < 1 || height > 15 || n > 225 ||
      !Number.isInteger(seed) || seed < 0 || seed > 0xffffffff ||
      !["dfs", "prim", "kruskal"].includes(method)) throw Error("Invalid input");
  let state = seed >>> 0;
  const random = () => {
    state = (state + 0x6d2b79f5) >>> 0;
    let v = Math.imul(state ^ (state >>> 15), state | 1);
    v ^= v + Math.imul(v ^ (v >>> 7), v | 61);
    return ((v ^ (v >>> 14)) >>> 0) / 0x100000000;
  };
  const edges = [], incident = Array.from({length: n}, () => []);
  const add = (a, b) => {
    incident[a].push(edges.length); incident[b].push(edges.length);
    edges.push({from: a, to: b});
  };
  for (let v = 0; v < n; v++) {
    if (v % width + 1 < width) add(v, v + 1);
    if (v + width < n) add(v, v + width);
  }
  const other = (id, v) => edges[id].from === v ? edges[id].to : edges[id].from;
  incident.forEach((ids, v) => {
    const dir = id => {
      const u = other(id, v);
      return u === v - width ? 0 : u === v + 1 && v % width + 1 < width ? 1 : u === v + width ? 2 : 3;
    };
    ids.sort((a, b) => dir(a) - dir(b));
  });
  const walls = Array(n).fill(15), passages = [], seen = Array(n).fill(false);
  const stack = [0], frontier = [], queued = new Set();
  const enqueue = v => { for (const id of incident[v]) if (!queued.has(id)) {
    queued.add(id); frontier.push(id);
  }};
  const parent = Array.from({length: n}, (_, i) => i), size = Array(n).fill(1);
  const find = x => { while (parent[x] !== x) {
    parent[x] = parent[parent[x]]; x = parent[x];
  } return x; };
  const order = edges.map((_, i) => i);
  if (method === "kruskal") for (let i = order.length - 1; i > 0; i--) {
    const j = Math.floor(random() * (i + 1)); [order[i], order[j]] = [order[j], order[i]];
  }
  if (method !== "kruskal") seen[0] = true;
  if (method === "prim") enqueue(0);
  let cursor = 0;
  while (passages.length < n - 1) {
    let id, from, to;
    if (method === "dfs") {
      from = stack[stack.length - 1];
      const choices = incident[from].filter(id => !seen[other(id, from)]);
      if (!choices.length) { stack.pop(); continue; }
      id = choices[Math.floor(random() * choices.length)]; to = other(id, from);
    } else if (method === "prim") {
      const i = Math.floor(random() * frontier.length);
      id = frontier[i]; frontier[i] = frontier[frontier.length - 1]; frontier.pop();
      from = seen[edges[id].from] ? edges[id].from : edges[id].to;
      to = other(id, from); if (seen[to]) continue;
    } else {
      id = order[cursor++]; from = edges[id].from; to = edges[id].to;
      if (find(from) === find(to)) continue;
    }
    const e = edges[id];
    if (e.to === e.from + 1 && e.from % width + 1 < width) {
      walls[e.from] &= ~2; walls[e.to] &= ~8;
    } else { walls[e.from] &= ~4; walls[e.to] &= ~1; }
    passages.push(id); seen[from] = seen[to] = true;
    if (method === "dfs") stack.push(to);
    if (method === "prim") enqueue(to);
    if (method === "kruskal") {
      let a = find(from), b = find(to);
      if (size[a] < size[b]) [a, b] = [b, a];
      parent[b] = a; size[a] += size[b];
    }
  }
  return {edges, passages, walls};
}
// generateMaze(9, 7, 34, "dfs"); // or "prim", "kruskal"