SQL HowTo: генерируем лабиринты (алгоритм Прима и геометрические типы) / Хабр

Пример сгенерированного дерева для лабиринта 21x21

SQL является мощным инструментом для обработки множеств, а функционал PostgreSQL позволяет делать многие вещи еще проще, поэтому идеально подходит для реализации некоторых алгоритмов на графах.

Причем работа с графами - это не просто разминка для ума, а вполне себе прикладная задача. Например, в прошлой статье мы сделали "из мухи - слона" волновым алгоритмом Ли, аналогичным используемому у нас в СБИС при расчете себестоимости на производстве в многокомпонентных актах выпуска продукции.

А сегодня мы научимся генерации случайных лабиринтов алгоритмом Прима с использованием геометрических типов данных.

Алгоритм Прима (упрощенный)

Алгоритм Прима используется для создания минимального остовного дерева в неориентированном графе. В нашей упрощенной версии вершинам графа будут соответствовать узлы координатной сетки, а ребра вести к 4 соседям (слева, справа, сверху и снизу) и обратно - то есть все ребра будут равновесными, а граф - неориентированным.

Поэтому таких "минимальных" деревьев может быть сгенерировано множество, и каждое из них будет представлять свой лабиринт, где ребро между вершинами графа - наличие прохода между смежными комнатами.

Исходный координатный граф и пример лабиринта по дереву в нем

Алгоритм, стартующий со случайного узла, состоит из двух шагов:

для всех уже достигнутых вершин дерева выбираем ребра, которые ведут в еще не достигнутые вершины
выбираем любое из них случайным образом и добавляем вместе с новой вершиной к дереву

В ходе работы алгоритма могут возникнуть вершины, из которых будет уже нельзя никуда "шагнуть" (розовые), поэтому можно исключить их из анализа ребер на следующих шагах и проводить его только для "фронта" формируемой волны (красные), который состоит из вершин, откуда можно было двигаться дальше:

А теперь - на SQL!

Очевидно, что наш алгоритм подразумевает цикличность, что на SQL соответствует рекурсивному запросу - будьте осторожны при их использовании!

Договоримся, что наш лабиринт будет квадратным и сначала зададим его "радиус":

-- задаем "радиус" лабиринта
WITH RECURSIVE sz(r) AS (
  VALUES(10)
)

Очертим границы нашего лабиринта, чтобы случайно не вылезти за них - для этого подойдет тип прямоугольника box:

-- границы лабиринта
, box AS (
  SELECT
    box( -- прямоугольник по противоположным углам
      point(-r, -r)
    , point(+r, +r)
    )
  FROM
    sz
)

Теперь определим��я с рекурсивным циклом.

На каждом шаге нам понадобится знать уже достигнутые узлы дерева, "фронт" волны и выбранное ребро. В нашем случае каждый узел описывается как точка с двумя координатами, поэтому мы можем использовать тип point для его хранения, а ребро будет отрезком - тип lseg.

На стартовом шаге мы "вбрасываем" в лабиринт случайную точку с координатами [-r .. +r] и составляем из нее стартовое дерево и текущий "фронт":

-- цикл выбора ребер
, T AS (
  SELECT
    ARRAY[p]::point[] points    -- уже достигнутые точки
  , ARRAY[p]::point[] wavefront -- фронт "волны"
  , NULL::lseg edge             -- выбранное ребро
  FROM
    sz
  , LATERAL
      point( -- случайная стартовая точка
        (random() * 2 * r)::integer - r
      , (random() * 2 * r)::integer - r
      ) p
UNION ALL
  -- ... Hic sunt dracones
  WHERE
    array_length(T.points, 1) = 1 OR -- стартовый шаг
    T.edge IS NOT NULL               -- продолжаем, пока можно выбрать ребро
)

И "шагать" в цикле мы будем, пока будут находиться подходящие ребра. Поскольку в нашем квадратном лабиринте (2 * r + 1) ^ 2 узлов и один из них мы уже выбрали, то для достижения остальных нам потребуется ровно на единицу меньше шагов.

Here be dragons

Основной шаг нашего алгоритма будет выглядеть так:

для каждой точки "фронта" волны сформировали lseg-ребра до "соседей"

FROM
  unnest(T.wavefront) s -- для каждой точки фронта
, LATERAL ( -- формируем все 4 возможных ребра
    VALUES
      (lseg(s, point(s[0] - 1, s[1])))
    , (lseg(s, point(s[0] + 1, s[1])))
    , (lseg(s, point(s[0], s[1] - 1)))
    , (lseg(s, point(s[0], s[1] + 1)))
  ) X(e)

оставляем только те ребра, где целевая точка d лежит в границах лабиринта и еще не принадлежит дереву

, LATERAL ( -- получаем "целевые" точки
    SELECT e[1] d
  ) Y
WHERE
  d <@ (TABLE box) AND -- целевая точка должна находиться в границах лабиринта
  d <> ALL(T.points)   -- и не должна быть достигнута ранее

все оставшиеся ребра группируем в массив, а из их исходных точек формируем "фронт" для следующего шага
Нам совсем не нужно, чтобы в массиве "плодились" одинаковые точки, поэтому тут пришлось пойти на хитрость, преобразовав для уникализации тип point в text (поскольку оператор point = point не реализован, из-за чего и DISTINCT выдает ошибку), и сразу обратно полученный text[] в point[]:
```
SELECT
  array_agg(e) edges -- набор все полученные ребра
, array_agg(DISTINCT s::text)::point[] wavefront -- новый фронт - все возможные "источники" предыдущего шага
```

остается лишь выбрать из набора произвольное ребро, а его целевую точку добавить к дереву и фронту

SELECT
  T.points || X.edge[1]    -- "хвост" выбранного ребра добавляем к достигнутым точкам
, X.wavefront || X.edge[1] -- ... и к фронту
, X.edge
FROM
  T
, LATERAL (
    SELECT
      Z.wavefront
    , Z.edges[
        (random() * (array_length(Z.edges, 1) - 1))::integer + 1
      ] edge -- выбираем случайное ребро из набора
    FROM
      (
-- ...
      ) Z
  ) X

Здесь мы пошли на сознательное небольшое упрощение, составив "фронт" для следующего шага из всех точек-источников и новой точки, хотя какие-то из них уже не смогут стать источниками для новых ребер (оказались в тупике). Но это не страшно - они просто отсеются на следующем шаге.

Собственно, на этом - все, в T.edge находятся искомые ребра дерева.

Полная генерация дерева

-- цикл выбора ребер
, T AS (
  SELECT
    ARRAY[p]::point[] points    -- уже достигнутые точки
  , ARRAY[p]::point[] wavefront -- фронт "волны"
  , NULL::lseg edge             -- выбранное ребро
  FROM
    sz
  , LATERAL
      point( -- случайная стартовая точка
        (random() * 2 * r)::integer - r
      , (random() * 2 * r)::integer - r
      ) p
UNION ALL
  SELECT
    T.points || X.edge[1]    -- "хвост" выбранного ребра добавляем к достигнутым точкам
  , X.wavefront || X.edge[1] -- ... и к фронту
  , X.edge
  FROM
    T
  , LATERAL (
      SELECT
        Z.wavefront
      , Z.edges[
          (random() * (array_length(Z.edges, 1) - 1))::integer + 1
        ] edge -- выбираем случайное ребро из набора
      FROM
        (
          SELECT
            array_agg(e) edges -- набор все полученные ребра
          , array_agg(DISTINCT s::text)::point[] wavefront -- новый фронт - все возможные "источники" предыдущего шага
          FROM
            unnest(T.wavefront) s -- для каждой точки фронта
          , LATERAL ( -- формируем все 4 возможных ребра
              VALUES
                (lseg(s, point(s[0] - 1, s[1])))
              , (lseg(s, point(s[0] + 1, s[1])))
              , (lseg(s, point(s[0], s[1] - 1)))
              , (lseg(s, point(s[0], s[1] + 1)))
            ) X(e)
          , LATERAL ( -- получаем "целевые" точки
              SELECT e[1] d
            ) Y
          WHERE
            d <@ (TABLE box) AND -- целевая точка должна находиться в границах лабиринта
            d <> ALL(T.points)   -- и не должна быть достигнута ранее
        ) Z
    ) X
  WHERE
    array_length(T.points, 1) = 1 OR -- стартовый шаг
    T.edge IS NOT NULL               -- продолжаем, пока можно выбрать ребро
)

Делаем красиво

Но мало просто сгенерировать дерево в памяти - хочется хоть как-то (а лучше красиво!) его увидеть, чтобы проверить себя.

Чтобы вывод в консоль выглядел приятно для глаза, будем рисовать наши узлы и ребра (где они присутствуют) на удвоенной координатной сетке:

То есть узлы окажутся в точках с обеими четными координатами, горизонтальные ребра - с нечетным X, вертикальные - с нечетным Y. Причем для соблюдения пропорций вертикальные ребра будем выводить одним символом '|', а горизонтальные - двумя '--' (или '---' - тут все зависит от используемого вами в консоли шрифта):

Для начала приведем набор отображаемых ребер (узлы-то заведомо будут все) в удобный вид. Для этого с помощью функции point(lseg) находим центр отрезка, масштабируем его координаты с коэффициентом 2 оператором * point(scale, rotate) , чтобы превратить их в целочисленные, и проверяем "вертикальность" отрезка оператором ?| lseg:

-- приводим ребра в удобный вид
, edges AS (
  SELECT
    point(edge) * point(2, 0) cx2 -- удваиваем координаты центра ребра
  , CASE
      WHEN ?| edge THEN '|' -- вертикальный отрезок
      ELSE '--'
    END v -- определяем его положение (вертикально/горизонтально)
  FROM
    T
  WHERE
    edge IS NOT NULL
)

Теперь генерируем и заполняем координатную сетку в соответствии с описанными выше правилами, используя оператор совпадения ~= для проверки равенства точек сетки и центра отрезка:

-- заполняем координатную сетку
, map AS (
  SELECT
    m.*
  , CASE
      WHEN x % 2 = 0 AND y % 2 = 0 THEN '+'
      WHEN x % 2 = 0 THEN coalesce(v, ' ')
      ELSE coalesce(v, '  ')
    END v
  FROM
    ( -- удвоенная координатная сетка
      SELECT
        x
      , y
      FROM
        sz
      , generate_series(-r * 2, r * 2) x
      , generate_series(-r * 2, r * 2) y
    ) m
  LEFT JOIN
    edges e
      ON point(x, y) ~= cx2 -- point = point
)

И, наконец, собираем итоговый построчный вывод:

-- рисуем картинку
SELECT
  string_agg(v, '' ORDER BY x) maze
FROM
  map
GROUP BY
  y
ORDER BY
  y;

Вот теперь - все!

 +   +---+---+   +
 |           |   |
 +---+---+---+---+
 |           |
 +   +   +---+---+
     |       |
 +---+---+---+---+
     |       |
 +---+   +---+---+

Нарисуй свой лабиринт!

-- задаем "радиус" лабиринта
WITH RECURSIVE sz(r) AS (
  VALUES(10)
)
-- границы лабиринта
, box AS (
  SELECT
    box( -- прямоугольник по противоположным углам
      point(-r, -r)
    , point(+r, +r)
    )
  FROM
    sz
)
-- цикл выбора ребер
, T AS (
  SELECT
    ARRAY[p]::point[] points    -- уже достигнутые точки
  , ARRAY[p]::point[] wavefront -- фронт "волны"
  , NULL::lseg edge             -- выбранное ребро
  FROM
    sz
  , LATERAL
      point( -- случайная стартовая точка
        (random() * 2 * r)::integer - r
      , (random() * 2 * r)::integer - r
      ) p
UNION ALL
  SELECT
    T.points || X.edge[1]    -- "хвост" выбранного ребра добавляем к достигнутым точкам
  , X.wavefront || X.edge[1] -- ... и к фронту
  , X.edge
  FROM
    T
  , LATERAL (
      SELECT
        Z.wavefront
      , Z.edges[
          (random() * (array_length(Z.edges, 1) - 1))::integer + 1
        ] edge -- выбираем случайное ребро из набора
      FROM
        (
          SELECT
            array_agg(e) edges -- набор все полученные ребра
          , array_agg(DISTINCT s::text)::point[] wavefront -- новый фронт - все возможные "источники" предыдущего шага
          FROM
            unnest(T.wavefront) s -- для каждой точки фронта
          , LATERAL ( -- формируем все 4 возможных ребра
              VALUES
                (lseg(s, point(s[0] - 1, s[1])))
              , (lseg(s, point(s[0] + 1, s[1])))
              , (lseg(s, point(s[0], s[1] - 1)))
              , (lseg(s, point(s[0], s[1] + 1)))
            ) X(e)
          , LATERAL ( -- получаем "целевые" точки
              SELECT e[1] d
            ) Y
          WHERE
            d <@ (TABLE box) AND -- целевая точка должна находиться в границах лабиринта
            d <> ALL(T.points)   -- и не должна быть достигнута ранее
        ) Z
    ) X
  WHERE
    array_length(T.points, 1) = 1 OR -- стартовый шаг
    T.edge IS NOT NULL               -- продолжаем, пока можно выбрать ребро
)
-- приводим ребра в удобный вид
, edges AS (
  SELECT
    point(edge) * point(2, 0) cx2 -- удваиваем координаты центра ребра
  , CASE
      WHEN ?| edge THEN '|' -- вертикальный отрезок
      ELSE '--'
    END v -- определяем его положение (вертикально/горизонтально)
  FROM
    T
  WHERE
    edge IS NOT NULL
)
-- заполняем координатную сетку
, map AS (
  SELECT
    m.*
  , CASE
      WHEN x % 2 = 0 AND y % 2 = 0 THEN '+'
      WHEN x % 2 = 0 THEN coalesce(v, ' ')
      ELSE coalesce(v, '  ')
    END v
  FROM
    ( -- удвоенная координатная сетка
      SELECT
        x
      , y
      FROM
        sz
      , generate_series(-r * 2, r * 2) x
      , generate_series(-r * 2, r * 2) y
    ) m
  LEFT JOIN
    edges e
      ON point(x, y) ~= cx2 -- point = point
)
-- рисуем картинку
SELECT
  string_agg(v, '' ORDER BY x) maze
FROM
  map
GROUP BY
  y
ORDER BY
  y;

SQL HowTo: генерируем лабиринты (алгоритм Прима и геометрические типы)

Алгоритм Прима (упрощенный)

А теперь - на SQL!

Here be dragons

Делаем красиво

Публикации

Информация