Космики: моделирование эволюции многоклеточных организмов

    Здравствуй, Хабр!

    Несколько лет назад в прикладных целях я реализовал обычный Force-based визуализатор графов.

    На меня произвело впечатление, как простые итеративные преобразования могут производить субъективно сложные и интересные вычисления, формируя нетривиальные визуально-кинетические модели.

    Со временем возникло несколько идей, что интересного можно смоделировать.

    Вот что получилось с одной из них (в кадре мелкие объекты, смотреть в HD):




    За основу я взял тот самый визуализатор графов: потрогать.



    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 (UPD: добавил в архив ещё один dll, теперь должен и без SDK стартовать). На 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'а. Начислять энтузиастам очки за время, которое их железо крутило космос, показывая им процесс в виде заставки. Очки можно будет тратить в конструкторе особей, которые будут вбрасываться в распределённый космос, мутировать и эволюционировать — «демиург» сможет отслеживать успехи своей популяции и количество материи, подконтрольной его особям на просторах глобального космоса.

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

    Надеюсь, удастся его реализовать.

    Пока всё, спасибо за внимание!

    P.S. Энтузиасты, автономно запустившие модель — просьба написать — что за железо и какой FPS в консоли (консоль на заднем плане вторым окном)

    UPD: Часть 2: Моделирование эволюции многоклеточных организмов. 7 лет

    UPD: блог проекта на Patreon
    UPD: демо движка космиков 2013, с soft-body физикой

    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 71

      +4
      Плесень эволюционировала?

      А так, да, очень понравилось ) Напоминает начало игры S.P.O.R.E и ей подобных.

      Теперь вы в ответе за сотворённый вами мир и не имеете права его забросить )
        +5
        Вообще-то, как порядочный Бог, может. Предварительно наделив их свободой воли :)
          +8
          Я понял, откуда берётся свобода воли. Это когда задолбанный Бог говорит своим созданиям: «Блин, да делайте уже, что хотите, надоели!»
            +1
            Вы мыслите в верном направлении ;-)
        +1
        Кто не хочет ставить себе SDK, скопируйте файлик в папку с программой.
        www.mediafire.com/?uk4hh2e4jc1gch9
          0
          спасибо, добавил файл в архив
          +1
          Это прекрасно!
          0
          Не смог запустить под маком(
            0
            И кстати сэмплы с дропбокса в сафари тормозят сильнее, чем в хроме.
            0
            Очень понравилось, всегда привлекали такие штуки.
            А если сделать клеткам разные параметры, а не только энергию (и разные типы клеток — допустим, одни могут поглощать, другие на скорость движения влияют), то можно будет вообще наблюдать великолепную эволюцию в духе генетического алгоритма.
              +6
              Следующим этапом будет введена потеря энергии на рывок и индивидуальные параметры рывка для клеток (% энергии, который она готова потратить и параметры жертвы, при которых она это сделает). Эти данные будут передаваться генетически. Визуализировать будем красным — агрессивных, синим — трусливых, зелёным — пофигистов. Энергию — размером.

              Дальше будет динамический морфологический метаболизм, когда энергия перекачивается по склейкам не строго от большей к меньшим, а по некоторой генетической карте особи. В совокупности со сложными (недревовидными) скелетами это должно дать эволюционный потенциал к образованию органов (пасть, некое подобие матки, щупальца, лапы для собирания планктона и т.п.).

              Отдельная плюшка — переход к 3D, но там нужно больше материи сразу…
                0
                Великолепно, именно об этом я и говорил.
                Жду следующих версий.
                  0
                  Где то я подобное встречал…
                  что то вроде тыц

                  И это довольно интересная система.
              0
              А что тут служит источником энтропии?
              Рандом только один раз используется, при генерации положения начальных клеток?
                +2
                да. если проект доживёт до распределённой screensaver версии, однозначность развития ситуации исходя из начальных параметров будет использоваться для контроля за невмешательством в вычислительные процессы конечных пользователей двойным просчётом каждого сценария на разных машинах облака. (очевидно, может появиться соблазн вмешаться в вычисления, чтобы помочь своей популяции в рамках своего участка распределённого космоса)
                  0
                  А я еще один рандом углядел у вас)
                  Если не ошибаюсь, клетки, которые «выстреливают» из центра (реинкарнации сожранных) — выстреливают под рандомным углом.
                  Или она просто появляется в центре, а дальше ее растаскивает внешнее воздействие?
                    0
                    они выстреливают в случайных точках, и, соответственно, ускоряются под случайными углами, но делают это в соответствии с изначальными параметрами инициализации рандомайзера, поэтому повлиять на ход эксперимента можно, только вмешавшись в него slidebar'ами, в целом он должен быть стабилен
                      0
                      Понятно. Успехов в реализации, надеюсь, проект не загнется, выглядит очень интересно.
              0
              Гипнотизирует!

              Успехов в дальнейших эволюциях =)
              0
              В какой-то момент у меня начинают плавать натуральные медузы из десятков клеток, пожирающие все на своем пути.

              Может быть, сделать так что новорожденные источником и большинство стартовых клеток жизни клетки будут пассивны и не будут «обращать внимание» на остальных, или создавать связи поглощения с остальными, двигаясь только относительно источника жизни? Это разгрузит часть ресурсов/на клетку.

              Более простой способ разгрузит систему: клетка реагирует только на те клетки вне своего космика, которые находятся на определенном расстоянии от нее. Тогда зависимость не квадратична.

                0
                Проблема в том, что чтобы выяснить, на каком расстоянии находится клетка — уже нужно вычислить расстояние между клетками, т.е. выполнить это действие N^2 раз. В целях оптимизации можно сегментировать пространство, это и есть алгоритм Барнса-Хата. Но, по инопланетным для меня причинам, он даёт выигрыш на видеокарте только после 50K частиц.

                Пассивные клетки тоже ничего не дадут, т.к. каждая активная клетка всё равно должна взаимодействовать с каждой пассивной, т.е. пара взаимодействий и N^2 сохраняются, просто импульс получает только клетка погони, а импульс уклонения обнуляется.

                Технически, учитывая архитектурные особенности CUDA, это даст не прирост производительности, а её потерю на ветвлении.
                0
                Должен сказать, что эти ваши Космики весьма и весьма жестокие твари :( Они свергли своего короля (образно говоря): i.imgur.com/aPKNc.png, мне его даже как-то жаль стало, т.к. он теперь стоит и ничего не делает, к нему кто-то периодически подлетает и в спешке отлетает, но сам он не двигается, обиделся очень :(
                  0
                  А у меня таких «королей» штук 5 было, был лютый ппц, когда они крепились к кому-либо. Весь организм нахрен разрывало во все стороны
                • UFO just landed and posted this here
                    +2
                    На этот счёт у меня особое мнение, а именно: нейронные сети — не самый лучший способ реализации разума на аппаратной платформе. Впрочем, не хочу быть голосоловным, поговорим об ИИ после того, как я его реализую :-)

                    Это будет как минимум позже создания эмулятора эмоций и инстинктивных движений для анимации виртуальных настольных нимфоманок
                      0
                      Я думаю надо подождать квантовых компьютеров.
                        0
                        Впрочем, есть у меня мнение, что мозг тоже каким-то образом в процессе мышления опирается на некоторые квантовые эффекты.
                        Вот правда как проверить эту догадку? Современной измерительной аппаратуры видимо будет недостаточно.
                  +1
                  Эх, жаль, что не кросспатформенно =(
                  Нельзя ли адаптировать под Linux и Mac?
                    0
                    Думаю, будет с течением времени.

                    Если есть энтузиаст, который перекомпилит исходник в другой среде — я с удовольствием поделюсь кодом сегодня же.
                      0
                      Мне бы на ATI запустить :( Видюха то очень мощная стоит, Radeon 5870, но блин она CUDA не умеет.
                        0
                        если много энтузиазма, там нужно только переписать CUDA процедуру на OpenCL, и она очень простая. в основном, как всегда, возиться придётся с тем, чтобы разобраться, куда запрягать лошадей в новой среде
                          0
                          Хорошо, будет время поковыряю :) Я думаю если что, то могу поспрашивать о том что да как в личке?
                  0
                  А как их покормить? %-)
                    +1
                    Пока максимум, что я могу предложить, нажать s, уменьшить foodtemp и увеличить foodk. Они будут очень быстро расти

                    Возможность кормить руками любимчиков сделаю позже ;-)
                    0
                    Я не очень понял, два здоровых «индивида» могут слиться друг с другом? При каких условиях?

                    А то я вот смотрю — есть двое, но они пролетают друг мимо друга, и как будто бы, наоборот, отдирают мелкие «запчасти», а не присоединяются.
                      0
                      Я бы еще предложил прикрутить расход энергии на импульсы в разные стороны, а то два гиганта любят сходиться друг с дружкой и метаться друг к дружке с дикой скоростью, иногда, правда, они разлетаются с такой же огромной скоростью, но не все :)
                        0
                        Промахнулся веткой, извините :)
                          0
                          да, хорошая идея. расход энергии на импульс и принятие решений, совершать ли импульс — в todo есть
                          +1
                          Да, да, секс, где же секс? Размножение, ревность, измена, беспорядочные половые связи…
                            0
                            в производстве :-)
                          0
                          А кто автор музычи в самом первом ролике? :)
                            0
                            Shpongle: Shiva Space Technology
                            0
                            Думаю вам понравится книга «Электрические методы обогащения», Автор: Павел Черкашин. Там в основной сюжетной линии разработка на базе ботнета информационного проекта «Аквариум», «населенного» программами с искусственным интеллектом.

                            А еще хотелось бы в будущем увидеть у космиков размножение на базе генетических алгоритмов (эволюционных), отбор по всем правилам Дарвина и все такое =)
                              0
                              А вообще жутко круто!
                                0
                                спасибо! генетические алгоритмы уже в разработке, ради них всё и затевалось
                                0
                                клёвая книжка, спасибо!
                                +1
                                Есть алгоритм рассчёта взаимодействия, более эффективный, чем Barnes-Hut — работает за O(N) вместо O(N logN). Два года назад, когда я с ним столкнулся, его ещё не распараллелили. Однако, с тех пор, возможно, с этим уже что-то сделали.
                                  0
                                  Спасибо, был не в курсе!
                                  +1
                                  Это, наверное, круто, но моя 9800 GTX+ с CUDA 1 не позволяет мне оценить наверняка. Это возможно как-то исправить, кроме как покупкой новой видеокарты?)
                                    +2
                                    я постараюсь сделать вариант для ранних версий CUDA
                                    0
                                    GPU Device 0: «GeForce GTX 560» with compute capability 2.1

                                    STEP: 2 FPS: 75.046906

                                    Потом опустилось до 70-ти.

                                    Хотелось бы больше ползунков для всяких параметров :)
                                      0
                                      Очень интересный проект! Мне он вдвойне интересен, потому что давно хочу написать нечто очень похожее. Есть много теоретических наработок, но до реализации так и не дошёл. Как мне кажется, в вашей модели не хватает простора для эволюции. Пока не очень понятно как будет происходить размножение и мутации. Если вы планируете развивать проект в направлении моделирования эволюции, то с большим интересом присоединюсь. Можно будет всё перенести на более кроссплатформенные рельсы в виде Qt или аналогов и OpenCL вместо Cuda.
                                        0
                                        Спасибо! Это было бы здорово! Вопрос «простора для эволюции» ключевой, на эту тему много мыслей и экспериментов, которые нужно проверять в лоб, воображением я не осиливаю просмотреть пространство вариантов. Напишите, пожалуйста, мне в skype
                                          0
                                          Ну кстати если взять SceneGraph из Qt5, то на нем вполне шуструю и красивую визуальную обертку можно сделать, а сами вычисления переписать на openCL. В принципе тоже готов поучаствовать.
                                            0
                                            напиши мне в skype: pavel-kudinov, пожалуйста
                                              0
                                              Случилось ли что-нибудь интересное в мире космиков с тех пор?
                                                0
                                                да, с самого момента написания этого поста и до сегодняшнего дня мы с группой энтузиастов активно разрабатываем скажем так «космики 2.0». впрочем, идея совершенно другого масштаба (поэтому и ушло уже столько времени) — мы с нуля создаём физическую реальность (свой специфический движок, в первую очередь в целях оптимизации под как можно больший объём материи, чтобы космос был велик), виртуальные органические тела (тела у которых есть чётко выделенные органы и которые не «пролетают друг сквозь друга») и помещаем в эти тела примитивную форму сознания на базе продвинутых модификаций различных нейросетей.

                                                т.е. мы создаём полную триаду 1 мир + N * ( тело + сознание )

                                                детали не публикуем до альфы, но если интересно — пишите в skype: pavel-kudinov, могу показать как это выглядит на сегодня :-)

                                                  0
                                                  Может сделаете страничку для подписки на новости проекта по почте — раз альфа таки будет для интересующихся? Спасибо!
                                                    0
                                                    я пока не готов распространять информацию по проекту в кругу людей, с которыми я не знаком лично хотя бы заочно. будет очень жаль, если кто-то возьмёт относительно примитивную по объёму и качеству часть уже достигнутых результатов, и выложит на всеобщее обозрение.

                                                    у меня есть представление о той планке качества, начиная от которой я готов буду показать результаты многолетнего развития проекта сообществу. надеюсь, это произойдёт в течение ближайших 1-2 лет.

                                                    говоря короче, я считаю, что ранняя публичность в любой форме может негативно сказаться на судьбе проекта в целом.
                                          0
                                          Вы не читали Дэна Симмонса, тетралогию «Гиперион»? Там была интересная идея, откуда возник искусственный интеллект — развился из подобных программ симуляции эволюции, поставленных в ограниченные условия.
                                          P.S. Кстати, очень достойная книга! Рекомендую любителям фантастики.
                                            0
                                            Все же как клеточный автомат система не совсем удачно построена. Первый недостаток — нет оттока энергии, только накачка. Гаснущие клетки по определению содержат меньше энергии чем новорожденные, поэтому сумма энергии системы постоянно растет.
                                            Второе — клетки ядра крупных космиков почти бессмертны, самая крупная из них — бессмертна полностью, ничто не может ее поглотить. Разве что вырастет еще более крупная клетка, но тогда ничто не сможет поглотить уже ее.
                                              0
                                              Прежде всего, спасибо за конструктивную критику!

                                              Теперь обороняюсь ;-)

                                              Система вообще не является клеточным автоматом, она не содержит регулярную решётку ячеек.

                                              Сумма энергии постоянно растёт по аналогии с накачкой экосистемы планеты Земля солнечной энергией (имеется ввиду не то, что планета постоянно нагревается, а то, что планета имеет постоянный приток структурирующей энергии, осваиваемый фотосинтезом и аналогичным процессами, что постоянно приводит к усложнению макрохимии биосферы).

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

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

                                              В общем-то следующая версия в совокупности будет иметь столько изменений, что вряд ли будет сильно походить на текущую ходом развития событий; именно по этой причине была опубликована текущая версия, которую планируется считать каноничной.
                                                +1
                                                Всё является клеточным автоматом. ;-)
                                                Наша планета постоянно излучает в тепловом диапазоне, отдавая полученную энергию. У вас есть накачка в виде белой точки, рождающей новые клетки, заполненные энергией, но нет (в svg по крайней мере) оттока энергии. Это не открытая а полу-открытая энергетическая система, которая способна на сложное, но не бесконечное развитие (и в конце обычно остается одна-единственная очень жирная клеточная сеть, повисшая прямо по центру вокруг источника и непрерывно подсоединяющая к себе все вылетающее именно поэтому — иначе эту сеть бы убила необходимость отдавать энергию).

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

                                                Кстати уже в который раз вижу интересный баг (а может фичу?) в svg. Когда время жизни вселенной подходит к концу и остается одна-единственная крупная сеть с очень-очень жирной клеткой ядра, сидящая на источнике жизни и пожирающая все, что из него вылетает, она через какое-то время своей жизни… ммм… превращается в черную дыру, коллапсирует, встасывая в себя всю свою сеть и источник жизни заодно. Я думаю, что вы специально написали такое поведение, но если нет, то это самый поразительный баг, который мне приходилось видеть.
                                              0
                                              Есть игра с похожей идеей — Osmos
                                                0
                                                Знаю, играл. В Она в числе прочих выступила вдохновителем

                                              Only users with full accounts can post comments. Log in, please.