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;