Необыкновенный способ генерации лабиринтов

В этой статье я расскажу об одном необычном подходе к генерации лабиринтов. Он основан на модели Амари́ нейронной активности коры головного мозга, являющейся непрерывным аналогом нейронных сетей. При определенных условиях она позволяет создавать красивые лабиринты очень сложной формы, подобные тому, что приведен на картинке.

Вас ждет много анализа и немного частных производных. Код прилагается.
Прошу под кат!



Введение


Многие из читателей уже сталкивались с задачей генерации лабиринта в той или иной форме и знают, что для ее решения зачастую используют алгоритмы Прима и Крускала нахождения минимального остовного дерева в графе, вершины которого являются ячейками лабиринта, а ребра представляют проходы между соседними ячейками. Мы же сделаем смелый шаг прочь от теории графов в сторону… вычислительной нейробиологии.

В течение XX века ученые строили математические модели одиночных нейронов (клеток нервной системы) и их взаимодействия между собой. В 1975 году С. Амари представил свету свою непрерывную модель коры головного мозга. В ней нервная система рассматривалась как сплошная среда, в каждой точке которой находится «нейрон», характеризуемый значением потенциала своей мембраны, которая меняет свой потенциал, обмениваясь зарядами с соседними нейронами и внешними раздражителями. Модель Амари знаменита тем, что объясняет многие феномены человеческого зрения и, в частности, зрительные галлюцинации, вызываемые психоактивными веществами.

Модель Амари, в ее простейшем виде, представляет собой задачу Коши для одного интегро-дифференциального уравнения:
Здесь не обойтись без пояснений:
  • — вещественное значение потенциала мембраны нейрона в точке в момент времени .
  • — потенциал покоя (некоторая вещественная константа).
  • — ступенчатая функция Хэвисайда:
  • — весовая функция.
  • — внешний раздражитель.
  • — распределение потенциала в начальный момент времени.
  • — произвольная точка области , на которой определен потенциал. Поскольку мы планируем генерировать двумерное изображение лабиринта, в качестве будем рассматривать всю вещественную плоскость.
  • Частная производная по времени в левой части обозначает мгновенное изменение потенциала . Правая часть задает правило этого изменения.
  • Первые два слагаемых правой части означают, что при отсутствии раздражителей значение потенциала стремится к значению потенциала покоя.
  • Следующее слагаемое учитывает воздействие соседних нейронов. Функция Хэвисайда играет роль активационной функции нейрона: нейрон начинает влиять на соседей лишь при условии, что его потенциал больше нуля. Будем далее называть такие нейроны активными, а множество точек с положительным потенциалом — областью активности. Ясно, что покоящиеся нейроны не должны быть активными, то есть потенциал покоя не должен быть положительным. Активных соседей можно условно разделить на две группы: возбуждающие и тормозящие. Возбуждающие нейроны увеличивают потенциал соседей, а тормозящие — уменьшают. При этом возбуждающие создают мощный всплеск активности в малой окрестности, а тормозящие постепенно гасят активность в окрестности большого радиуса. Именно этот факт отражен в выборе весовой функции в форме «мексиканской шляпы»:

  • Последнее слагаемое правой части уравнения учитывает действие внешнего раздражителя. Например, для зрительной коры головного мозга естественным раздражителем является сигнал, полученный с сетчатки глаза. Будем считать, что раздражитель задан неотрицательной стационарной (независящей от времени) функцией.

Зададимся вопросом: можно ли подобрать параметры модели так, чтобы ее стационарное решение (при ) было изображением некоторого лабиринта?


Свойства решений модели Амари


Для анализа решений модели Амари нам будет достаточно ограничиться рассмотрением одномерного случая. Для простоты будем полагать, что постоянна на всей прямой.
В первую очередь нас интересуют так называемые бамп-решения. Они замечательны тем, что положительны лишь на некотором конечном интервале с подвижными границами. Уравнение Амари для них записывается следующим образом:
Чтобы понять, как ведет себя его решение, введем функцию
Теперь то же уравнение можно переписать так:
Нам известно, что бамп-решение обращается в ноль на границах интервала активности (потому они и называются границами). Запишем это условие на правой границе:
А теперь продифференцируем последнее тождество по переменной :
Отсюда:
Подставляя последнее выражение в уравнение для бамп-решения при , получим:
Теперь заметим, что частная производная по в левой части всегда отрицательна, так как слева от правой границы решение больше нуля, а справа от нее — меньше. Поэтому
Таким образом, направление сдвига границы зависит лишь от значения выражения в правой части. Если оно больше нуля, то область активности расширяется, если меньше — сужается. При равенстве нулю достигается равновесие.
Взглянем на возможные графики функции .

Очевидно, возможны два случая:
  1. Предельное значение неотрицательно. Тогда область активности бамп-решения будет неограниченно расширяться.
  2. Предельное значение отрицательно. Тогда область активности будет ограничена. Более того, в этом случае можно показать, что связные компоненты области активности решения уравнения Амари никогда не сливаются.

К сожалению, в двумерном случае получить явное выражение для функции затруднительно, поэтому мы просто оценим ее:
Отсюда:


Генерация лабиринта


Собрав багаж необходимых знаний, мы можем приступить к, собственно, алгоритму генерации лабиринта.
Прежде всего, определимся с самим понятием «лабиринт». Под лабиринтом будем подразумевать бинарную функцию такую, что область связна. Значение 0 соответствует свободной ячейке, а значение 1 — непроходимой стене. Условие связности говорит о том, что из любой свободной ячейки можно добраться до любой другой, не разрушая стены. Функцию будем искать в виде:
где — решение модели Амари. Осталось лишь определиться с параметрами модели.
Начнем с того, что зафиксируем произвольное отрицательное значение . Естественно положить . Теперь зададим функцию . Пусть ее значение в каждой точке определяется случайной величиной, равномерно распределенной на отрезке . В таком случае раздражитель не будет создавать активность. Зафиксируем произвольное положительное . Этот параметр влияет лишь на абсолютную величину потенциала, потому не представляет интереса. Зафиксируем произвольные положительные . Они определяют характерную толщину стен лабиринта. Параметр попробуем определить экспериментально, а затем сравнить с теоретической оценкой, полученной в предыдущем разделе.
Стационарное решение будем искать методом последовательных приближений:

А вот и долгожданная интерактивная демонстрация на Python:
import math
import numpy
import pygame
from scipy.misc import imsave
from scipy.ndimage.filters import gaussian_filter


class AmariModel(object):

    def __init__(self, size):
        self.h = -0.1
        self.k = 0.05
        self.K = 0.125
        self.m = 0.025
        self.M = 0.065

        self.stimulus = -self.h * numpy.random.random(size)
        self.activity = numpy.zeros(size) + self.h
        self.excitement = numpy.zeros(size)
        self.inhibition = numpy.zeros(size)

    def stimulate(self):
        self.activity[:, :] = self.activity > 0

        sigma = 1 / math.sqrt(2 * self.k)
        gaussian_filter(self.activity, sigma, 0, self.excitement, "wrap")
        self.excitement *= self.K * math.pi / self.k

        sigma = 1 / math.sqrt(2 * self.m)
        gaussian_filter(self.activity, sigma, 0, self.inhibition, "wrap")
        self.inhibition *= self.M * math.pi / self.m

        self.activity[:, :] = self.h
        self.activity[:, :] += self.excitement
        self.activity[:, :] -= self.inhibition
        self.activity[:, :] += self.stimulus


class AmariMazeGenerator(object):

    def __init__(self, size):
        self.model = AmariModel(size)

        pygame.init()
        self.display = pygame.display.set_mode(size, 0)
        pygame.display.set_caption("Amari Maze Generator")

    def run(self):
        pixels = pygame.surfarray.pixels3d(self.display)

        index = 0
        running = True
        while running:
            self.model.stimulate()

            pixels[:, :, :] = (255 * (self.model.activity > 0))[:, :, None]
            pygame.display.flip()

            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    running = False
                elif event.type == pygame.KEYDOWN:
                    if event.key == pygame.K_ESCAPE:
                        running = False
                    elif event.key == pygame.K_s:
                        imsave("{0:04d}.png".format(index), pixels[:, :, 0])
                        index = index + 1
                elif event.type == pygame.MOUSEBUTTONDOWN:
                    position = pygame.mouse.get_pos()
                    self.model.activity[position] = 1

        pygame.quit()


def main():
    generator = AmariMazeGenerator((512, 512))
    generator.run()


if __name__ == "__main__":
    main()

Я полагаю, что комментарии излишни. Хотелось бы отметить лишь то, что свертка с весовой функцией вычисляется через фильтр Гаусса, причем изображения продолжаются периодически на всю плоскость (параметр «wrap»). Демонстрация интерактивна в том смысле, что позволяет принудительно установить положительный потенциал в любой точке по клику.
Поведение решения, как и ожидалось, зависит от выбора параметра :

Теперь получим теоретическую оценку оптимального значения параметра . Оно удовлетворяет условию:
Поэтому его можно оценить следующим образом:
Неплохо, однако реальное значение чуть выше теоретической оценки. В этом легко убедиться, положив .

Наконец, можно менять степень «разреженности» лабиринта, изменяя значение параметра :

Заключение


Вот мы и закончили рассмотрение, пожалуй, самого необыкновенного способа генерации лабиринтов. Надеюсь, что статья показалась Вам интересной. В заключение приведу список литературы для желающих расширить свой кругозор:

[1] Konstantin Doubrovinski, Dynamics, Stability and Bifurcation Phenomena in the Nonlocal Model of Cortical Activity, 2005.
[2] Dequan Jin, Dong Liang, Jigen Peng, Existence and Properties of Stationary Solution of Dynamical Neural Field, 2011.
[3] Stephen Coombes, Helmut Schmidt, Ingo Bojak, Interface Dynamics in Planar Neural Field Models, 2012.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 54
  • +16
    Просто потрясающе!
    • +45
      Нужна ли математика программисту?
      • –23
        Suicide mode ON
      • +29
        Нужен ли программист математике?
        • +17
          Нужен ли программист?
          • НЛО прилетело и опубликовало эту надпись здесь
            • –3
              Нужен!
              • –2
                «Алло, Китайцы? У вас есть миллиард? Здорово! А не могли-бы вы мне его прислать?» — Лукашенко из Мульта Личности.
              • –2
                Не трогайте Брюса.
                • +1
                  Как минимум — Софус.
            • +56
              Ответ: Да, в частных случаях. В других частных случаях программисту нужна биохимия, экономика и куча других знаний необходимых для конкретного проекта.
              Реально достали уже с этим «нужналипрограммистуматематика».
              • +5
                Нужен ли этот вопрос здесь?
                • –7
                  Нет, есть гугл.
                  • +1
                    Программист — он как профессор Мориарти — по определению математик!
                  • +7
                    Это офигенно!

                    Респект как от лица программиста, так и от лица математика!
                  • +3
                    Очень классно, спасибо. Иллюстрации отличные.
                    • +5
                      Это просто великолепно! Автор — молодец, Хабр — торт!
                      • +3
                        Круто. Ещё решить бы, как добиться решаемости сгенерированного лабиринта by design.
                        Не «пробивать» же «дырки» в «стенах», попутно натравливая на него всякие А*.
                        • +3
                          Этому вопросу посвящен целый раздел.
                          Попробую объяснить на пальцах: если запускать демо с теми параметрами, что указаны в посте (M = 0.065), то белые «извилины» (стены) никогда не будут сливаться. Поскольку изначально черная область была связна (из любой черной точки можно было дойти до любой другой черной точки, передвигаясь лишь по черным точкам), то и в любой другой момент времени она останется связной. Иначе говоря, решаемости лабиринта «by design» можно добиться правильным выбором параметров модели (точнее, одного параметра M).
                          • 0
                            Спасибо за подробный ответ!
                            • +2
                              Поскольку изначально черная область была связна (из любой черной точки можно было дойти до любой другой черной точки, передвигаясь лишь по черным точкам), то и в любой другой момент времени она останется связной.

                              Только эта «связность» будет обеспечиваться наличием общей «внешней» оболочки, что несколько странно для лабиринта: они обычно обнесены стеной по периметру.
                              Вот немного пейнта по упомянутой картинке из статьи:
                              image
                              Хотя вот здесь все гораздо лучше:
                              image
                              • +1
                                Все абсолютно верно. В представленном варианте связным будет лишь бесконечное периодическое продолжение лабиринта на всю плоскость. Это связано с использованием режима «wrap» в фильтре Гаусса. Для того, чтобы получить конечный связный лабиринт, достаточно поменять «wrap» на «reflect».
                                • +1
                                  Вот пример для наглядности:

                              • 0
                                Вот интересны границы интервала значений M, когда лабиринт будет терять связность либо вырождаться в белое либо чёрное пятно.

                                Надо поэкспериментировать и потом попробовать доказать.
                              • +1
                                Тут скорее нужно не ломать стенки, а, наоброт, закрывать лишние дырки. Например, на самой первой картинке вариантов прохода от одной стены к другой слишком много. Вот тогда будет полная жесть :)
                              • 0
                                вот это хардкор!
                                • +13
                                  О, извилины! Дефицит! Мне такие нужны!
                                  • 0
                                    Спасибо, красиво! Но что касается практичности, то главное свойство лабиринта – запутанность. В нем должен быть неочевидный правильный путь (или небольшое количество правильных путей, не считая петель и циклов), плюс большое количество тупиков или петель. А ваши лабиринты проходятся почти по прямой. Можно ли по-простому доработать алгоритм так, чтобы удлинить и запутать правильный путь?
                                    • +2
                                      Согласен, но, боюсь, простейшей модификацией не обойтись. Скажем, это не те лабиринты, в которых есть «правильный путь», а те лабиринты, которые можно использовать в гейм-дизайне для генерации интересных уровней.
                                    • +1
                                      Вы довольно точно смоделировали рост некоторых колоний бактерий, или, например, коралла-мозговика :)
                                      • +15


                                        10 PRINT CHR$(205.5+RND(1)); : GOTO 10

                                        Видео
                                        Книга
                                        Обзор
                                        • +6
                                          Никто не может гарантировать связность этого лабиринта.
                                        • +5
                                          Заглянул под кат с мыслью: «Что может быть необыкновенного в генерации лабиринта?», а тут такое… Снимаю шляпу, вы украли у меня часов 5 ночного сна!
                                          *ушел генерировать лабиринты*
                                          • –3
                                            Хм-м, время: 18:57, место: Москва, если верить профилю. Вы спите днём?
                                            • 0
                                              … человек просто спит не дома. Только тссссс! Жене его не говорите!
                                          • +4
                                            Одна из тех очень немногих статей, ради которых я до сих пор и читаю хабр. По пальцам можно пересчитать их.
                                            • 0
                                              Благодарю за потрясающую иллюстрацию силы математики!
                                              • 0
                                                Спасибо за статью! Может быть, один лишь я не все понял, но все же: не могли бы вы пояснить, откуда берутся подобные формулы для сигмы: sigma = 1 / math.sqrt(2 * self.k) и sigma = 1 / math.sqrt(2 * self.m) и какую роль она выполняет?
                                                • +1
                                                  В этом месте кода вычисляется свертка activity с весовой функцией
                                                  Реализовывать такую операцию руками мне не хотелось, поэтому я представил ее в виде разности результатов двух сверток: с и с . В свою очередь, свертка с функцией по сути есть свертка с функцией Гаусса (с точностью до постоянного множителя):
                                                  Отсюда и берутся значения всех таинственных констант.
                                                • 0
                                                  А мне кажется, или подобный результат возможен вообще без сложной математики?

                                                  Вот просто задавать несколько раз N точек, их движение, следить чтобы не сближались, вероятность разветвления, постепенное изменение угла движения.

                                                  Кажется очень просто.
                                                  • +1
                                                    Так не интересно и не элегантно)
                                                    • 0
                                                      Зато так по идее можно гарантировать решаемость алгоритма и задавать его сложность.
                                                      • +1
                                                        Напишите алгоритм. Покажите нам. Посмотрим, сравним.
                                                  • +1
                                                    Мне, как гуманитарию, это разрывает мозг. Многое непонятно, но понятно, что это потрясающе. Не смотря на то, что по математике у меня была уверенная пятерка, сложные формулы заставили лицо скривить гримасу ужаса от шока непонимания!
                                                    • +10
                                                      Статья хорошая, но является классическим примером советского образования.

                                                      Сначала идет куча математики, которую даже я, чертов Магистр Математики, вечером за пивком решил пролистать. Хорошо, что не закрыл. Ведь дальше идет как раз интересная часть. И так везде. На протяжении шести лет университета было ровно так же. Три месяца скучнейшей абстрактной математики, которая совершенно не понятно зачем нужна. А к моменту, когда начинается реальное применение, 95% студентов уже отвалилось и ничего не понимают.

                                                      Должно быть совершенно наоборот: показать в начале классное применение, упуская объяснение сложных моментов, а уже потом постепенно разворачивать сложность и ввожить новые абстракции и формулы.
                                                      • +1
                                                        Мои 4 курса ММФ кончились 10 лет назад (хоть я все же и Магистр, но Других Наук), но я испытал удовольствие от формул, хотя вообще-то далеко не с первого раза врубился. Суть ведь не в программе, так же? А чтобы самим делать подобное. Абстракция нужна чтобы иметь не единственное применение, и этот пост тому пример. И еще и мотивация.
                                                        • 0
                                                          Вы комент-то прочитали?
                                                          • 0
                                                            Переформулирую. Мысль в том, что практическая реализация — это дело второго приоритета. Проработать идею важнее.
                                                            • 0
                                                              К сожалению многие так и остались детьми — им интересно как машинка катается, а не как она устроена что бы кататься. Им это просто скучно и хочется смотреть на катающуюся машинку. Собственно поэтому вам и рекомендуют сначала сделать привлекательную презентацию с картинками и видео для альтернативно одаренных, а потом уже пугать формулами и проработкой идеи.
                                                              Тем более что модель Коши изучают в технических ВУЗах и фактически здесь мы видим отличный пятерочный курсач второкурсника физтеха или ВМК по мат методам.
                                                      • 0
                                                        Спасибо за прекрасную статью. Вижу вы мучились с вставкой картинок с формулами. Советую стабильный онлайн сервис их генерации codecogs
                                                        • –3
                                                          Программирование великая вещь! Всего пару десятков строк кода и получается такая красотища. Мне этот метод генерации лабиринтов очень бы пригодился в одном проекте, но с python-ом я, к сожалению, не знаком. Если кто-нибудь возьмется портировать этот код на actionscript 3, то я буду не только благодарен, но и оплачу труды в размере 1000 руб. Кого это предложение интересует, пишите в личку.

                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.