Создание случайного связанного лабиринта
kromkoСоздание случайного связанного лабиринта¶
После Урока 4 школы и представленного там генератора комнат со стенами, мне стало любопытно чисто для себя написать генератор, который из любой комнаты со случайно разбросанными стенами сделает связный лабирант.
Я использовал некоторые функции Julia, которые не были представлены на Уроках, но буду оставляю комментарии. Возможно, кому-то будет интересно.
Я буду вводить используемые мной модули по мере востребования.
Создание стен¶
Представим нашу прямоугольную комнату, состоящую из тайлов. Каждый тайл может быть либо пустым пространством, либо стеной. Я предлагаю сделать тайл в виде исчисляемого типа (enum). В Julia это реализовано при помощи макроса @enum
@enum Tile Empty Wall
typeof(Wall) # выводит тип данных
Хорошо. Давайте создадим пустую комнату с окружающими стенами.
function generateroom(w, h)
room = fill(Empty, (h, w))
room[begin, :] .= room[end, :] .= Wall
room[:, begin] .= room[:, end] .= Wall
room
end
И отрисуем её. Я создам словарь с палитрой для тайлов
using Images, Colors
function drawtiles(room::Matrix{Tile})
map(e -> tilecolors[e], room)
end
tilecolors = Dict(Empty => RGB(0,0,0), Wall => RGB(0,0.8,0))
let
# блок let создаёт локальное пространство переменных, т.е. этот room доступен только внутри него
room = generateroom(60, 40)
drawtiles(room)
end
Хорошо. Но допустим, я хочу её чем-то наполнить. Например, случайным шумом. Я переделаю свою функцию generateroom, чтобы можно было контролировать содержание комнаты извне.
CI = CartesianIndex
function generateroom(w, h; walls=Returns(Empty))
indices = CI(1,1):CI(h,w) # индексы 2-мерной матрицы размером h на w.
room = map(walls, indices)
room[begin, :] .= room[end, :] .= Wall
room[:, begin] .= room[:, end] .= Wall
room
end
Немного объяснений. Я добавил именной аргумент walls, и ожидаю, что он будет принимать функцию с одним аргумент, которая возвращает либо Empty либо Wall. Значение по-умолчанию, Returns(Empty) эквивалентно функции x -> Empty, т.е. по умолчанию все внутренние тайлы будут пустыми.
Давайте наполним эту комнату чем-либо. Первое же что приходит в голову - расставить по комнате стены случайным образом.
using Distributions
randomwall(p_wall) = idx -> ifelse(rand(Bernoulli(p_wall)), Wall, Empty)
drawtiles(generateroom(60, 40; walls=randomwall(0.7)))
Внезапно комната стала чуть более тесной.
Я добавил пакет Distributions, в котором содержатся различные функции распределения случайных величин. Удобно то, что функция генерации случайного числа rand умеет принимать в качестве первого аргумента такие распределения и создавать на основании него значения.
В качестве распределения я использовал распределение Бернулли. С вероятностью p случайное значение будет истинным, а с вероятностью 1-p - ложным. Функция ifelse здесь заменяет тернарный оператор. Они не совсем 1:1 эквивалентны, но в моём случае это не имеет значения.
Итак, randomwall принимает в качестве аргумента вероятность, и возвращает функцию от одного аргумента (игнорируя этот аргумент), которая в свою очередь возвращает случайно Wall или Empty.
Можно на этом остановиться, но я хочу добавить ещё одну функцию генерации стен, а заодно несколько полезных вспомогательных.
function fillcircle(origin::CI{2}, r::Real; inside=Returns(Wall))
function f(idx)
d = origin - idx
return euclid(d) ≤ r ? inside(idx) : Empty
end
end
euclid(a::CI) = norm(Tuple(a), 2)
euclid(a, b) = euclid(b - a)
taxicab(a::CI) = Int(norm(Tuple(a), 1))
taxicab(a, b) = taxicab(b - a)
fillcircle по-умолчанию делает полностью заполенный стенами круг, но ей можно указать, каким образом осуществлять заливку.
Далее я добавил несколько норм - евклидову, которая пригодится здесь, и метрику городских кварталов, которую я буду использовать позднее. Функция norm является стандартной, и считает норму n-го порядка для вектора. Мне пришлось превратить CI в кортеж, поскольку в Julia принудительно нельзя производить итерацию по координатам в декартовом индексе.
Скомпонуем эти функции:
room = generateroom(60, 40;
walls=fillcircle(CI(30, 30), 25; inside=randomwall(0.8))
)
# при создании комнаты я сначала указываю ширину, а потом высоту
# а индекс CI(строка, столбец), т.е. наоборот
drawtiles(room)
Меня вполне устраивает такая фигура. Те, кому интересно, могут поэкспериментировать сами.
Далее можно определить, много ли у нас сегментов. На глаз понятно что много, но сначала неплохо их найти, а потом объединить (ведь такую задачу я ставил изначально)
Я буду использовать метод заливки, написанный не подглядывая. Коротко изложу принципы, которые я использовал при написании:
- Ищется неразмеченный свободный тайл (если таких нет, значит всё готово).
- Этот тайл отмечается как принадлежащий сегменту с номером
n. Его соседи тоже отмечаются как часть этого сегмента, как и их соседи. - Как только соседи закончились, возвращаемся к п.1.
К сожалению, на этом этапе я вынужнен расстаться с enum. Сегментированная комната будет в виде матрицы целых чисел.
Прошу не обращать внимание на аргумент callback, я буду использовать его после. По умолчанию он ничего не делает.
function floodfill(room::Matrix{Tile}; callback=Returns(nothing))
# сделаем из Wall -1, а из Empty 0
segmentedroom = map(t -> ifelse(iswall(t), -1, 0), room)
callback(segmentedroom)
segmentnumber = 1
while true
unassignedtile = findfirst(t -> t == 0, segmentedroom)
if isnothing(unassignedtile) break end
# но можно сразу `return segmentedroom` вместо break
fillin!(segmentedroom, segmentnumber, unassignedtile; callback) # заливаем сегмент начиная с найденного тайла
segmentnumber += 1
end
segmentedroom
end
# вспомогательные функции для удобства
iswall(t::Integer) = t == -1
iswall(t::Tile) = t == Wall
iswall(i::CI, room) = iswall(room[i])
Собственно, сам перебор соседей можно реализовать при помощи типа данных Очередь (как список, но данные добавляются в конец, а извлекаются с начала). Стандатный Vector в Julia довольно универсален, и для него определены нужные фунции.
В этой функции я в качестве именного аргумента добавил empty - это то значение (по умолчанию 0), которое мы заменяем номером сегмента. Опять же, игнорируйте callback.
function fillin!(segmentedroom::AbstractMatrix, segmentnumber::Integer, starttile::CartesianIndex{2}; empty=0, callback=Returns(nothing))
# указывать типы данных необязательно, это больше для читателя
queue = [starttile]
while length(queue) > 0
currenttile = popfirst!(queue)
if segmentedroom[currenttile] != empty continue end
# если это стена, или тайл уже ассоциирован с сегментом, пропускаем
segmentedroom[currenttile] = segmentnumber
callback(segmentedroom)
neighbours = getneighbours(currenttile)
push!(queue, neighbours...)
end
segmentedroom
end
Почти всё готово - осталось только понять, как определить соседей. Поскольку наш будущий робот может двигаться горизонтально и вертикально, их можно подобать вот так:
getneighbours(tile) = map(n -> n+tile, [CI(0,1), CI(1,0), CI(0,-1), CI(-1,0)])
getneighbours(predicate, tile) = filter(predicate, getneighbours(tile))
Вторая функция нам может не пригодиться, но её можно использовать, если у нас есть критерий, по которому мы хотим отобрать соседей (например, не-стены). Я мог использовать её в fillin!, но я все равно там делаю ещё одну проверку.
И, в общем-то всё. Давайте нарисуем. Но сначала добавим палитру.
fillcolors = distinguishable_colors(10, collect(values(tilecolors)), dropseed=true)
function drawsegments(segments; scale=1)
function tocolor(s)
if s == 0 return tilecolors[Empty] end
if s == -1 return tilecolors[Wall] end
return fillcolors[rem(s-1, length(fillcolors)) + 1]
end
img = map(tocolor, segments)
repeat(img, inner=(scale, scale)) # на случай если мы захотим увеличить размер картинки путём повторения пикселей
end
let
segmentedroom = floodfill(room)
nsegments = filter(!iswall, segmentedroom)
println("Количество найденных сегментов: $(length(unique(nsegments)))")
drawsegments(segmentedroom)
end
Посмотрим как это выглядит пошагово. Но сначала добавлю вспомогательную функцию для отображения видео в Jupyter/Engee.
using Base64
function display_webm(filename)
display("text/html", string("""<video autoplay controls><source src="data:video/x-m4v;base64,""",
base64encode(open(read,filename)),"""" type="video/webm"></video>"""))
end
#добавлю возможность масштабировать картинку тайлов
drawtiles(room; scale) = repeat(drawtiles(room), inner=(scale, scale))
using VideoIO
let
scale = 6
encoder_options = (crf=23,)
framerate=30
path = joinpath(@__DIR__, "fill1.webm")
initial = drawtiles(room; scale)
# VideoIO принимает не все RGB форматы, а только RGB{N0f8}
initial = Matrix{RGB{N0f8}}(initial)
open_video_out(path, initial, framerate=framerate, encoder_options=encoder_options) do writer
cb(segments) = write(writer, Matrix{RGB{N0f8}}(drawsegments(segments; scale=scale)))
# а вот и callback понадобился
seg = floodfill(room; callback=cb)
end
display_webm(path)
end
Обратите внимание, я использовал замыкание callback, чтобы отрисовывать изображение. floodfill не знает ничего, что делает callback.
Ломать - не строить!¶
С большой вероятностью (которая зависит от параметра p_wall, использованного при генерации заполненного стенами круга), результат заливки показал наличие нескольких сегментов. Поскольку изначально я задал необходимость создания связного лабиринта, перейдём к более весёлой части: обратное строительство.
Исходил из следующих соображений:
- Если у нас больше одного сегмента в комнате, я хочу сломать стену которая ближе всего к двум сегментам.
- Я не хочу перебирать всё изображение несколько раз в поиске самой "тонкой" стены. Имеет смысл начать с самого маленького сегмента, и искать сначала около него.
- При оценке потециального кандидата на снос, я опять же не хочу перебирать все возможные тайлы в поиске ближайших. Разумно начать с ближайших соседей и идти по нарастанию расстояния.
function joinsegments!(room::AbstractMatrix{T}; callback=Returns(nothing)) where T<:Integer
# ограничение на матрицу целых чисел для того, чтобы случайно не подсунуть матрицу из тайлов
while true
allsegments = findsegments(room) # см.далее
if length(allsegments) == 1 return room end
# ищу самый маленький сегмент. Итерация по словарю выдаёт пару `k => v` (s[2] как раз ссылается на v)
# s[2] тут кортеж с именными элементами (см. allsegments)
smallest = argmin(s -> s[2].size, allsegments)[1]
# начнём с центра сегмента и будем искать самую уязвимую стену, см.далее
weakest = findweakwall(room, smallest, allsegments[smallest].center)
neigh = getneighbours(n -> !iswall(n, room), weakest)
neighseg = unique(map(n->room[n], neigh))
if length(neighseg) == 0
# если эта стена оказалась вдали от всех сегментов, сделаем её новым сегментов
newseg = maximum(keys(allsegments))+1
room[weakest] = newseg
elseif length(neighseg) == 1
# если стена была рядом с одним сегментом, присоединим её ему
room[weakest] = neighseg[1]
else
# а здесь случай, когда эта стена разделяет два или более сегментов
neighseg = sort(neighseg; by=n->allsegments[n].size, rev=true)
biggest = popfirst!(neighseg)
# я воспользую здесь уже существующим алгоритмом заливки чтобы сделать анимацию в конце
# но room[room .== n] .= biggest скорее всего было бы эффективнее
for n in neighseg
room[weakest] = n
fillin!(room, biggest, weakest; empty=n, callback)
end
end
callback(room)
end
room
end
В поиске сегментов, я нахожу их номер, размер, а также координаты центра этого сегмента, и выдаю в качестве Dict.
function findsegments(room)
centers = Dict{Int, CI{2}}()
sizes = Dict{Int, Int}()
for (idx, tile) in pairs(room)
if iswall(tile) continue end
if !haskey(centers, tile)
centers[tile] = idx
sizes[tile] = 1
else
centers[tile] += idx
sizes[tile] += 1
end
end
# объединим в один кортеж
middle(idx::CI, n) = CI(round.(Int, Tuple(idx) ./ n)...)
Dict((k => (center=middle(centers[k], sizes[k]), size=sizes[k]) for k in keys(centers))...)
end
Допустим, мы нашли самый маленький сегмент, и знаем, где его центр. Это место не хуже других, чтобы начать искать вокруг него слабые стены.
Первое что я делаю - задаю себе ограничение, что я не ищу намного дальше расстояния до самого дальнего тайла моего сегмента.
Я также ввожу вспомогательную функцию isinner, чтобы не анализировать тайлы вне комнаты.
Поскольку я не знаю, как далеко мне нужно искать, имеет смысл сделать итератор (о нём чуть дальше).
isinner(idx, m) = 1 < idx[1] < size(m, 1) && 1 < idx[2] < size(m, 2)
function findweakwall(room, seg, origin)
segmentindices = filter(idx -> room[idx] == seg, CartesianIndices(room))
maxdistance = maximum(idx -> taxicab(origin, idx), segmentindices)
maxdistance += 2 # добавляем две клетки для удаления
iter = NearestIterator(origin; maxdist=sum(size(room))) # см. далее
iter = Iterators.takewhile(idx -> taxicab(origin, idx) ≤ maxdistance, iter)
iter = Iterators.filter(idx -> isinner(idx, room), iter)
iter = Iterators.filter(idx -> iswall(idx, room), iter)
nearest = collect(iter)
# я мог бы делать дальше перебор по итератору через Iterators.accumulate в поисках самой слабой стены,
# но посчитал что проще собрать его в и сделать argmin
argmin(idx -> distancetonearestsegment(room, idx; firstsegment=seg), nearest)
end
Для оценки того, как далеко потенциальная слабая стена находится от других сегментов (а именно от того, с которого я начал поиск, и какого-либо другого), имеет смысл использовать такой же итератор, как и для поиска стен вокруг центра сегмента (выше).
function distancetonearestsegment(room, origin; firstsegment)
d1 = -1 # расстояние до стартового сегмента
dother = -1 # расстояние до другого сегмента
# тут по-хорошему нужно быть уверенным что в комнате хотя бы 2 сегмента, один из которых исходный
for idx in NearestIterator(origin; skiporigin=true, maxdist=sum(size(room)))
if !isinner(idx, room) continue end
tile = room[idx]
if iswall(tile) continue end
if (tile == firstsegment && d1 == -1) d1 = taxicab(origin, idx) end
if (tile != firstsegment && dother == -1) dother = taxicab(origin, idx) end
if d1 != -1 && dother != -1 return d1+dother end
end
end
А теперь о самом итераторе. Этот объект можно использовать для перебора значений в цикле for (в функции distancetonearestsegment) или специальные функции для работы с итераторами (из модуля Iterators, см. функцию findweakwall). Чтобы сделать из итератора Vector, его необходимо собрать функцией collect.
Итератор - это любой объект, для которого определены методы iterate(iter::MyIterator) и iterate(iter::MyIterator, state). Первый начинает итерацию, а второй использует предыдущее состояние. Оба они возвращают либо кортеж (значение, состояние), либо nothing, чтобы закончить итерацию.
Поиск соседей осуществляется по-спирали. Когда соседи на расстоянии r заканчиваются, переходим на круг r+1 (по расстоянию городских кварталов)
# создаю тип для итератора...
struct NearestIterator
origin::CI{2} # исходная точка для поиска
skiporigin::Bool # пропускать ли вывод исходный точки?
maxdist::Int # максимальное расстояние от начальной точки (чисто для безопасности, чтобы не уйти в вечный цикл случайно)
end
# ... и дополнительный конструктор для него
NearestIterator(origin; skiporigin=true, maxdist=100) = NearestIterator(origin, skiporigin, maxdist)
# начало итерации. Если включаем начальную точку, то начинаем с неё, если нет, то с первого соседа.
function Base.iterate(iter::NearestIterator)
iter.skiporigin ? (iter.origin + CI(-1,0), CI(-1,0)) : (iter.origin, CI(0,0))
end
function Base.iterate(iter::NearestIterator, state::CI{2})
if state == CI(0,0)
# если мы начали с исходной точки, продолжим с ближайшего соседа
return (iter.origin + CI(-1, 0), CI(-1, 0))
end
dist = taxicab(iter.origin, iter.origin + state)
if dist > iter.maxdist
# окончание итерации, поскольку мы ушли слишком далеко
return nothing
end
if state[2] == -1 && state[1] == -dist+1
return (iter.origin + CI(-dist-1,0), CI(-dist-1, 0))
end
offset = if state[1] < 0 && state[2] ≥ 0
CI(1,1)
elseif state[2] > 0 && state[1] ≥ 0
CI(1,-1)
elseif state[1] > 0 && state[2] ≤ 0
CI(-1,-1)
else
CI(-1,1)
end
return (iter.origin + state + offset, state + offset)
end
И это всё. Можем запустить нашу функцию, получить картинку и посчитать количество сегментов.
let
seg = floodfill(room)
joinsegments!(seg)
nsegments = filter(!iswall, seg)
println("Количество найденных сегментов: $(length(unique(nsegments)))")
# перекрашиваем сегмент обратно в неразмеченный для отрисовки тайлов
seg[.!iswall.(seg)] .= 0
drawsegments(seg)
end
Как мы видим, все наши сегменты слились в один. Сделаем анимацию.
let
scale = 6
encoder_options = (crf=23,)
framerate=30
path = joinpath(@__DIR__, "fill2.webm")
initial = drawtiles(room; scale)
initial = Matrix{RGB{N0f8}}(initial)
open_video_out(path, initial, framerate=framerate, encoder_options=encoder_options) do writer
cb(segments) = write(writer, Matrix{RGB{N0f8}}(drawsegments(segments; scale=scale)))
seg = floodfill(room; callback=cb)
joinsegments!(seg; callback=cb)
# перекрашиваем сегмент обратно в неразмеченный для отрисовки тайлов
seg[.!iswall.(seg)] .= 0
for _ in 1:10
cb(seg)
end
end
display_webm(path)
end
Вот, собственно, всё, что я хотел сделать в этом проекте. Я не ставил перед собой задачу что-то очень сильно оптимизировать, просто старался делать всё последовательно. Я надеюсь, вам был интересно.