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

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;