- PVSM.RU - https://www.pvsm.ru -
В этой статье я расскажу об одном необычном подходе к генерации лабиринтов. Он основан на модели Амари́ нейронной активности коры головного
Вас ждет много анализа и немного частных производных. Код прилагается.
Прошу под кат!
Многие из читателей уже сталкивались с задачей генерации лабиринта в той или иной форме и знают, что для ее решения зачастую используют алгоритмы Прима и Крускала нахождения минимального остовного дерева в графе, вершины которого являются ячейками лабиринта, а ребра представляют проходы между соседними ячейками. Мы же сделаем смелый шаг прочь от теории графов в сторону… вычислительной нейробиологии.
В течение XX века ученые строили математические модели одиночных нейронов (клеток нервной системы) и их взаимодействия между собой. В 1975 году С. Амари представил свету свою непрерывную модель коры головного
Модель Амари, в ее простейшем виде, представляет собой задачу Коши для одного интегро-дифференциального уравнения:
Здесь не обойтись без пояснений:
Зададимся вопросом: можно ли подобрать параметры модели так, чтобы ее стационарное решение (при ) было изображением некоторого лабиринта?
Для анализа решений модели Амари нам будет достаточно ограничиться рассмотрением одномерного случая. Для простоты будем полагать, что постоянна на всей прямой.
В первую очередь нас интересуют так называемые бамп-решения. Они замечательны тем, что положительны лишь на некотором конечном интервале с подвижными границами. Уравнение Амари для них записывается следующим образом:
Чтобы понять, как ведет себя его решение, введем функцию
Теперь то же уравнение можно переписать так:
Нам известно, что бамп-решение обращается в ноль на границах интервала активности (потому они и называются границами). Запишем это условие на правой границе:
А теперь продифференцируем последнее тождество по переменной :
Отсюда:
Подставляя последнее выражение в уравнение для бамп-решения при , получим:
Теперь заметим, что частная производная по в левой части всегда отрицательна, так как слева от правой границы решение больше нуля, а справа от нее — меньше. Поэтому
Таким образом, направление сдвига границы зависит лишь от значения выражения в правой части. Если оно больше нуля, то область активности расширяется, если меньше — сужается. При равенстве нулю достигается равновесие.
Взглянем на возможные графики функции .
Очевидно, возможны два случая:
К сожалению, в двумерном случае получить явное выражение для функции затруднительно, поэтому мы просто оценим ее:
Отсюда:
Собрав багаж необходимых знаний, мы можем приступить к, собственно, алгоритму генерации лабиринта.
Прежде всего, определимся с самим понятием «лабиринт». Под лабиринтом будем подразумевать бинарную функцию такую, что область связна. Значение 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 [2], 2005.
[2] Dequan Jin, Dong Liang, Jigen Peng, Existence and Properties of Stationary Solution of Dynamical Neural Field [3], 2011.
[3] Stephen Coombes, Helmut Schmidt, Ingo Bojak, Interface Dynamics in Planar Neural Field Models [4], 2012.
Автор: Thoughteer
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/35404
Ссылки в тексте:
[1] мозга: http://www.braintools.ru
[2] Dynamics, Stability and Bifurcation Phenomena in the Nonlocal Model of Cortical Activity: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.8688&rep=rep1&type=pdf
[3] Existence and Properties of Stationary Solution of Dynamical Neural Field: http://gr.xjtu.edu.cn/c/document_library/get_file?folderId=29529&name=DLFE-2974.pdf
[4] Interface Dynamics in Planar Neural Field Models: http://www.mathematical-neuroscience.com/content/2/1/9
[5] Источник: http://habrahabr.ru/post/181265/
Нажмите здесь для печати.