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

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

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

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

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

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

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

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

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

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

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

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

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

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

-- задаем "радиус" лабиринта
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;