Здравствуй!
Несколько лет назад в прикладных целях я реализовал обычный Force-based визуализатор графов.
На меня произвело впечатление, как простые итеративные преобразования могут производить субъективно сложные и интересные вычисления, формируя нетривиальные визуально-кинетические модели.
Со временем возникло несколько идей, что интересного можно смоделировать.
Вот что получилось с одной из них:
За основу я взял тот самый визуализатор графов: потрогать.
shift+click, shift+drag, alt+click.
потрогать лучше всего получится в Chrome или Safari по причине V8 javascript.
Я начал с того, что добавил инерцию вершинам графа, что сделало поведение объекта более сложным. В определённый момент модель стала ассоциироваться с чем-то средним между моделью химического соединения и многоклеточного организма: потрогать
Эксперименты выросли в желание обеспечить взаимодействие множества таких объектов по некоторым принципам, так, чтобы за этим было интересно наблюдать:
- объект считаем моделью тела многоклеточного организма, кодовое название «космик»
- космики состоят из клеток (cell) и склеек (stick)
- клетки имеют собственную энергию, с ростом энергии меняется размер и цвет
- склейки имеют энергию, определяющую её упругость, равную минимальной из энергий склеенных клеток
- клетки космика отталкиваются друг от друга с силой, пропорциональной энергии клеток
- склейки клеток препятствуют процессу отталкивания клеток с силой, пропорциональной энергии склеек
- головной клеткой космика считается клетка с наибольшей энергией
- космики стремятся поглотить (присоединить к себе) других космиков
- космик поглощает другого космика, приблизившись к его головной клетке любой собственной клеткой, обладающей большей энергией, чем головная клетка поглощаемого космика
- космики стремятся уклониться от поглощения другими космиками
- ускорение космика формируется суммой ускорений его клеток
- каждая клетка ускоряется в направлении всех клеток, которые она способна поглотить, с силой, пропорциональной её собственной энергии
- каждая клетка ускоряется в направлении от всех клеток, которые способны её поглотить, с силой, пропорциональной её собственной энергии
Позже была добавлена возможность разрыва склейки в случае чрезмерной нагрузки на неё. Вот что получилось в итоге: потрогать
Следующим шагом было реализовано пищеварение в пределах одного организма: каждая склейка каждый фиксированный отрезок времени отнимает энергию у меньшей клетки и передаёт её большей. В случае, если энергия меньшей клетки оказывается меньше определённого минимума, клетка исчезает, а в пространстве появляется новая ничейная клетка с базовым зарядом энергии, служащая пищей для эволюционирующих вокруг организмов. Так же было введено ограничение — клетка может поглотить только клетку, составляющую не меньше 61.8% от её собственной энергии. Это исключило формирование уродцев, когда огромные клетки присоединяют непосредственно к себе мелкие. Вместо этого, теперь они стали вынуждены формировать для этого разветвлённые щупальца: потрогать
На этом этапе возникло желание поделиться прогрессом с друзьями, был подготовлен скринкаст:
Дальнейшие планы подразумевали переход от SVG прототипа к CUDA модели. Очевидно, стало хотеться больше активной материи. Перенос модели на GPU дал возможность использовать 8-16K частиц вместо 250 в браузерном прототипе.
Это то, что есть на сегодняшний момент. Имеющие CUDA 2.0 совместимые устройства, могут потрогать модельку лично: потрогать.
В архиве, кроме прочего, ссылка на SDK для Win7 x64, который нужно установить перед запуском exe. На XP 32bit тоже работает, ссылку можно взять здесь: Cuda SDK.
p — снять с паузы
s — показать slidebar'ы
r — смена режима отображения
h — пометить головные клетки
f — fullscreen
Немного о дальнейших планах:
Конечно, хочется больше клеток. После оптимизации GTX 580 считает 16K клеток на частоте 30 FPS, в видео участвуют 8K клеток на частоте 120FPS.
Сказывается квадратичная сложность алгоритма, так как все клетки влияют на все клетки. Применение алгоритма оптимизации Barnes-Hut'а на CUDA, судя по прочитанным научным статьям от тех, кто это уже переносил на GPU, даёт эффект только за пределами порога в 50K частиц, что вне realtime порога :-( Впрочем, мне это всё ещё кажется сомнительным. Кроме того, порядок межклеточных взаимодействий значительно сложнее гравитационного.
Теоретически есть возможность считать одновременно 256K частиц на тех же 30FPS независимыми «галактиками» по 1K частиц (отображать на экране как сетку 16x16). С точки зрения эволюции, 256K частиц, пусть и сегментированных в независимые галактики, может оказаться значительно более полезным, чем непосредственное взаимодействие 16K клеток в пределах одной галактики. Обмен особями можно устраивать по раундам, обеспечивая межгалактический mortal kombat ;-)
По тому же принципу можно реализовать распределённую версию модели, например, в виде симпатичного screensaver'а. Начислять энтузиастам очки за время, которое их железо крутило космос, показывая им процесс в виде заставки. Очки можно будет тратить в конструкторе особей, которые будут вбрасываться в распределённый космос, мутировать и эволюционировать — «демиург» сможет отслеживать успехи своей популяции и количество материи, подконтрольной его особям на просторах глобального космоса.
Ключевую роль в дальнейшем развитии проекта должен сыграть морфогенетический алгоритм, который при столь скромных топологических возможностях (количества клеток / особь) сумеет обеспечить видовое многообразие особей.
Надеюсь, удастся его реализовать.
Пока всё, спасибо за внимание!
Автор: pavel_kudinov
