Эволюция гоночных автомобилей на JavaScript

    Возможно, вам доводилось видеть игру Box Car 2D — автогонки машинок, сгенерированных с помощью генетического алгоритма. Игра работает на платформе Flash и использует физический движок box2d. За тем, как из бесформенных уродцев через несколько десятков поколений развиваются вполне приличные гоночные автомобили, можно наблюдать часами. Игра существует уже несколько лет, а её фанаты соревнуются в выведении новых «пород» машинок на разных типах трасс. Недавно в сети появился клон этой игры под названием Genetic Cars, написанный на HTML5 и JavaScript. Хотя в нем ещё многого не хватает (например, редактора машинок), некоторые вещи сделаны гораздо лучше, чем в оригинале. Например, есть возможность наблюдать заезд всех машинок одновременно. И самое главное — можно ковыряться в исходниках!



    JavaScript-версию написал с нуля Рафаэль Мацунага. Кроме открытых исходников и одновременного заезда всех машин в его версии есть возможность отключить рендеринг — в этом случае просчитывается только физика, и эволюция идёт в несколько раз быстрее. В отличие от Box Car D2, поведение машинок не полностью детерминировано — одна и та же машинка на одной и той же трассе может показывать слегка разные результаты, поэтому иногда новое поколение показывает худший результат, чем предыдущее. Тем не менее, трасса, генерируемая псевдослучайно на основе строки, которую может задавать пользователь, всегда одна и та же для одной и той же строки, так что возможность соревноваться есть.

    В Genetic Cars также несколько меньше первоначальное генетическое разнообразие — у всех машин по два колеса. Всего геном автомобиля состоит из 14 генов — гораздо меньше, чем в Box Car 2D. 8 из них регулируют длину каждой вершины «тела», и по 3 на каждое колесо — расположение, размер и вес.

    Пока я писал эту статью, в фоновом окне Chromium на трассе, сгенерированной на основе строки «habrahabr.ru» успели посоревноваться уже три десятка поколений машинок. Рекордный результат — 178,87 метра.

    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 52
    • +30
      Отпусти меня чудо программа!
      • +4
        Пишу наверх, потому что полезный лайфхак :) Если нажать следующую последовательность кнопок, то можно запускать машинки в режиме Surprise то есть быстрее, и все равно их видеть.

        Surprise--->Go!--->Surprise--->Surprise
      • 0
        Супер комбинация :)
        eNqzfx85sWazsbEDk95vhtPGxvZvG6dsBPGZZ04zDjlz1v7CjbY2HyD91nLGuWVpafZP3rUEeM6cZf9F8K9TjouL/f7bz3MlgfwfR+0Mw9LS7V87cWqvBPI/6vcpvgHqeyy6sCMYaO6T5A1ekTNn2n9gAAP7rwFc0ZUzZwGZ7A6Cd/fnrOLeZ//ZY82uY2lpQDFGBx6ng2dk0n/af3GaxrYMLMbiwHYmNWtSRqv9N8nSI5+NjYFibA4Crcc3F713s394dWrSs7S0/0DgwCe2srzySYX9tSVzPLaXl4HFBI0O5/icaLL/tq95PhvYPFYHvq65PtInLtvvvjJtC8RZbA6i+gG1Vidu2z9+Zqo0c+ZMhjrRVQxhUy6C8ZQZu+BsEM5jKmWQYfYGsyfZm4Ppc6aKKGoYGJgB9uuWsg==
        • +16
          За что?
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            На 201-м — 180,84.
            • 0
              На 215-м — 188,25.
              • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  А, я думал вы на «habrahabr.ru» играете…
                • 0
                  #1: 197.22 d:192.62 h:0/13.1m (gen 12)
                  ;)
                  • 0
                    Пишите seed, без него эти цифры лишены смысла.
                    • 0
                      Черт, думал, что ввел «habrahabr.ru», а на самом деле ввел «harbahabr.ru» :(
                  • 0
                    #1: 188.45 d:185.12 h:-4.45/8.91m (gen 78)
                    seed:habrahabr.ru
                    • 0
                      #1: 187.56 d:184.89 h:-4.23/6.68m (gen 39)
                      С тем же семенем
                      • 0
                        #1: 189.63 d:185.23 h:-4.69/8.66m (gen 424)
                        • +1
                          Задрот :)
                          • 0
                            #1: 227.63 d:222.59 h:-4.75/7.74m (gen 188)
                            Но там дальше трасса превращается практически в забор.

                            Есть! Только что трасса пройдена:
                            #1: 281.46 d:277.89 h:-2883.67/7.07m (gen 205)

                            Внезапно трасса закончилась и машинка еще долго падала в бездну — вот так и закончилась судьба лучшей машнки.
                            • 0
                              А seed у вас точно «habrahabr.ru»?
                              • –1
                                Эмм… Нет. Ааа, т.е. там мир на базе строки генерируется? Не знал :)
                                Оставлю на ночь с новым seed — посмотрим что будет.
                                • 0
                                  #1: 189.35 d:185.56 h:-3.91/10.24m (gen 1112)

                                  Дааа, там дальше трасса превращается практически в вертикальную гору.
                            • 0
                              #1: 190.15 d:185.24 h:-3.84/8.85m (gen 113)
                              seed:habrahabr.ru
                              • 0
                                Оставлял на ночь. Прошло 1500 поколений. Таблица лидеров выглядит так:

                                #1: 190.31 d:187.42 h:-4.66/9.52m (gen 480)
                                #2: 190.24 d:187.57 h:-4.37/11.04m (gen 466)
                                #3: 189.9 d:187.62 h:-5.11/9.56m (gen 1382)
                                #4: 189.86 d:184.97 h:-5.05/8.26m (gen 937)
                                #5: 189.66 d:185.32 h:-4.86/9.28m (gen 1262)
                                #6: 189.63 d:185.23 h:-4.69/8.66m (gen 424)
                                #7: 189.49 d:185.33 h:-4.02/6.48m (gen 1420)
                                #8: 189.48 d:185.31 h:-4.75/9.14m (gen 236)
                                #9: 189.47 d:185.34 h:-4.31/6.4m (gen 1478)
                                #10: 189.43 d:184.98 h:-4.64/8.35m (gen 1209)
                        • –1
                          #1: 188.56 d:185.07 h:-4.66/8.74m (gen 44)
                          #2: 188.12 d:184.93 h:-4.82/7.49m (gen 31)
                          #3: 179.67 d:176.63 h:-4.87/6.2m (gen 15)
                          habrahabr.ru

                          Кто быстрее (в поколениях)? :)
                          (из настроек только Elite clones:2)

                          ps: Писал как-то свой генетический аквариум еще на паскале (лет 10-15 назад). Тогда идеи интересной визуализации не было и сутками по экрану бежали текстовые цепочки хромосом с результатами фитнес-функции. Матрица отдыхает :]
                    • +2
                      Интересно. Если взять вместо дороги реальный график работы оборудования и адаптированную машинку, то можно систему диагностики забабахать. Машинка забуксовала, с оборудованием что-то не то…
                      • 0
                        Думаю, при проектировании Curiosity не обошлось без долгих часов подобной симуляции.
                    • +5
                      У меня дальше всех заезжает красный трактор, похожий на «Беларусь». Генетический алгоритм на что-то намекает. :)
                      • 0
                        А у меня единороги какие то… Наверное алгоритм тоже на что то намекает?
                      • 0
                        почти три года назад, iOS, примерно два часа времени.
                        http://www.youtube.com/watch?v=Yjy4yPmMet8
                        • +12
                          Оставил на ночь — рекорд у машинки, у которой одно колесо на старте застряло в земле, а потом ее выстрелило и она пролетела 1037 :)
                          • +3
                            Читер!
                            • +2
                              У меня такая же машинка улетела на 2736 =)
                              #1: 2736.99 d:2704.37 h:-7818.21/122.38m (gen 152)
                            • +3
                              А после 4-х милиардов лет симуляции, машинки превратятся в разумных существ :)
                              • НЛО прилетело и опубликовало эту надпись здесь
                              • 0
                                Нельзя такие вещи с утра выкладывать. Людям работать же надо. А у меня вообще дедлайн!
                                • 0
                                  Хабр притягателен, даже во время дедлайна его почитывают.
                                • 0
                                  Под саундтрек из rock n roll racing смотрится эпичненько)
                                  • 0
                                    Оставил на ночь на первоначальной трассе:
                                    #1: 233.72 d:230.29 h:-11.54/1.55m (gen 117)
                                    #2: 233.16 d:229.83 h:-11.59/1.7m (gen 81)
                                    Дальше проехать почти не вероятно, крутой подъём машинка не заезжает и возможности перепрыгнуть тоже нет.
                                    Немного менял параметры: сначала несколько трасс — уровень мутации 75%, что дало очень разные машинки в лидерах.
                                    Потом 4 клона и мутация 30%
                                    • 0
                                      #1: 2313.75 d:2286.51 h:-7261.82/411.94m (gen 1149)

                                      Машинка нашла баг в движке. Она на старте застревает, а потом подпрыгивает в небо на вот такое расстояние.
                                      • 0
                                        Top Scores:
                                        #1: 2790.87 d:2757.49 h:-7678.36/231.57m (gen 2678)

                                        тот же самый баг (страничка висит в фоном режиме уже 5 дней, ~3800 поколений)
                                      • 0
                                        В результате должно получиться все внутри одного колеса?
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                          • 0
                                            чтобы не переворачивалась :)
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                              • 0
                                                Форма идеальной машины зависит от трассы
                                        • 0
                                          А есть какой-нибудь seed, который реально проходится до финиша?
                                          • +2
                                            А этот финиш вообще существует?
                                          • 0
                                            Похоже только конец.

                                            Промазал.
                                            • 0
                                              А зачем у вас слово «seed:» в поле seed? =))
                                              • 0
                                                Копипаст )
                                                Ну и так получилось что именно так осталось на ночь.
                                            • 0
                                              Проверил на FireFox 22.0 и выяснил, что симуляция идёт только в несвёрнутом окне браузера, при этом держать его на переднем плане не обязательно. Правда, пока до финиша так и не добрался, хотя уже прошло больше 8800 поколений.

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