Алгоритмы генерации лабиринтов python

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

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

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

Введение

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

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

Модель Амари, в ее простейшем виде, представляет собой задачу Коши для одного интегро-дифференциального уравнения:

Здесь не обойтись без пояснений:

• — вещественное значение потенциала мембраны нейрона в точке в момент времени .
• — потенциал покоя (некоторая вещественная константа).
• — ступенчатая функция Хэвисайда:

— весовая функция.

— внешний раздражитель.

— распределение потенциала в начальный момент времени.

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

Частная производная по времени в левой части обозначает мгновенное изменение потенциала . Правая часть задает правило этого изменения.

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

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

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

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

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

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

Нам известно, что бамп-решение обращается в ноль на границах интервала активности (потому они и называются границами). Запишем это условие на правой границе:

А теперь продифференцируем последнее тождество по переменной :

Подставляя последнее выражение в уравнение для бамп-решения при , получим:

Теперь заметим, что частная производная по в левой части всегда отрицательна, так как слева от правой границы решение больше нуля, а справа от нее — меньше. Поэтому

Таким образом, направление сдвига границы зависит лишь от значения выражения в правой части. Если оно больше нуля, то область активности расширяется, если меньше — сужается. При равенстве нулю достигается равновесие.
Взглянем на возможные графики функции .

Очевидно, возможны два случая:

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

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

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

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

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

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(".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() 

Источник