Пользователь
0,0
рейтинг
31 марта 2014 в 11:36

Разработка → Как Минковский во Flappy Bird играл из песочницы



Многие пробовали играть во Flappy Bird. Редко кому удается пролететь за 50 труб, очень немногие долетают до сотни-двух. Некоторые пробовали создать бота, в том числе на хабре. Удивительно, но даже у самого успешного бота, которого можно найти на просторах интернета, результаты не очень-то впечатляют – что-то около 160 очков. Возникает вопрос, а можно ли вообще играть во Flappy Bird бесконечно долго? Или всегда с некоторой, пусть и небольшой, вероятностью может встретиться последовательность препятствий, которую даже опытный игрок/идеальный бот не сможет преодолеть?

И тут на помощь приходит математика. Давайте найдем выигрышную стратегию для Flappy Bird.

Модель


Опишем математическую модель игры. Наше игровое поле — плоскость. Есть птичка — квадрат со сторонами длины w, параллельными координатным осям. Есть препятствия — трубы — вертикальные полосы ширины wtube с горизонтальными проемами высоты hgap. Расстояние между двумя соседними препятствиями по горизонтали фиксировано и равно Δtube. Расположение горизонтального проема для каждой трубы случайно (равномерно в некотором диапазоне). Кроме того есть пол — горизонтальная прямая f. Пол — это тоже препятствие. Картинка:



Скорость птички по горизонтали постоянна и равна vx. На птичку также действует гравитация, придавая ей вертикальное ускорение g. Изначально скорость птички по вертикали равна 0. В каждый момент времени игрок может сделать тап, то есть сделать так, чтобы вертикальная скорость птички стала равна vjump. Кроме того, на птичку действует некое подобие сопротивления воздуха – ее вертикальная скорость ограничена снизу константой vfall. Фактически, это означает, что после каждого тапа птичка движется по параболе, переходящей в какой-то момент в прямую. Траекторию, по которой двигается птичка после тапа, будем называть падаболой (парабола падения). Выглядит это так:



Игра заканчивается, когда птичка касается препятствия. Задачей игрока является максимизация пройденного расстояния.

Прежде чем переходить собственно к стратегии прохождения сделаем один фокус. Анализировать пересечения квадратной птички с препятствиями не очень-то удобно. Но, оказывается, легко перейти к эквивалентной модели, в которой птичка является точкой. Для этого достаточно «сдуть» птичку до размера точки (центра исходного квадрата), одновременно «раздувая» препятствия. При этом исходный квадрат пересекается с препятствиями тогда и только тогда, когда новая точечная птичка лежит в раздутом препятствии. Картинка:



По-научному результат «раздутия» препятствий называется суммой Минковского.

Сумма Минковского


Википедия сообщает:
Суммой Минковского двух подмножеств A и B линейного пространства V называется множество C, состоящее из сумм всевозможных векторов из A и B: C={c|c=a+b,a∈A,b∈B}

С бытовой точки зрения можно считать, что сумма Минковского фигур A и B есть фигура, получаемая, если к каждой точке B приложить фигуру A – см. правый рисунок.



Обратная падабола


Решим вспомогательную задачу: где должна находиться птичка, чтобы после тапа она пролетела через заданную точку A? Точнее говоря, требуется найти геометрическое место точек, таких что падаболы, проведенные из них, проходят через фиксированную точку A. См. средний рисунок. Пусть v⃗ – произвольный вектор, соединяющий начало падаболы с одной из ее точек. Легко видеть, что после тапа в точке A-v⃗ птичка пролетит через точку A. То есть A-v⃗ принадлежит искомому геометрическому месту точек. Более того, взяв всевозможные вектора v⃗, мы получим все искомые точки. Но чем является множество точек вида A-v⃗, где v есть радиус вектор до одной из точек падаболы? Это путь, центрально-симметричный падаболе после отражения относительно точки A. С картинкой, кстати, понятнее:



Можно обобщить задачу: где нужно тапнуть, чтобы пролететь через заданную область S? Исходя из всего вышесказанного ответом является сумма Минковского области S и обратной падаболы:



Верхние препятствия


Перейдем, наконец, к основной задаче – нахождению выигрышной стратегии. Только сначала решим ее в упрощенном случае. Пусть в модели отсутствуют нижние половинки труб и пол. То есть у нас имеются только верхние части препятствий. Рассмотрим отдельно стоящую верхнюю половину трубы. Пусть птичка начала свой путь где-то далеко слева от этого препятствия. Допустим, в какой-то момент времени птичка врезалась в трубу. Как мы знаем по предыдущему параграфу, это означает, что был совершен тап в области, получающейся путем прибавления к препятствию обратной падаболы. Раскрасим получившуюся область синим цветом. Рисунок:



Заметим, что если игрок тапнул в какой-либо точке синей области, то соответствующая падабола сначала пересекается с препятствием и только потом покидает синюю область. Другими словами игрок будет вынужден либо проиграть, либо еще раз тапнуть в синей области. Ну а поскольку отдельно взятая синяя область ограничена справа, лететь в ней до бесконечности не получится, и, в конце-концов, птичка умрет. Таким образом, тап в синей области всегда приводит к поражению. Более того, тапы вне синей области не могут привести к проигрышу – без тапа в синей области нельзя врезаться в верхнее препятствие, а больше нечему помешать птичке лететь.

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


Нижние препятствия


Теперь рассмотрим случай, когда в модели присутствуют только нижние половинки труб. То есть нет верхних половинок и пола. Опять же рассмотрим отдельно стоящее нижнее препятствие. Проведем через его верхний левый угол (точку A) луч AC, угол наклона которого составляет atan(vjump/vx) — то есть луч, направленный вдоль скорости птички в момент сразу после тапа. Пусть птичка оказалась ниже луча AC. Тогда независимо от действий игрока она не сможет подниматься с вертикальной скоростью большей чем vjump. С учетом постоянной горизонтальной скорости vx это приводит к неминуемому столкновению с препятствием, то есть проигрышу. Раскрасим нижнее препятствие и область ниже луча AC в красный цвет. Вот такие красные горки получаются:



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

Добавим пол. Несложно видеть, что пол можно воспринимать как еще одну красную область в форме нижней полуплоскости.

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


Все препятствия вместе


Рассмотрим общую ситуацию. Пусть есть и верхние половинки труб, и нижние, и пол. Вполне понятно следующее:
Утверждение. Если объединение синих областей не пересекается с объединением красных и птичка изначально находится вне синих и красных областей, то существуют выигрышные стратегии. Любая выигрышная стратегия описывается так: вне синих и красных областей можно принимать любые решения, в синих областях тапать нельзя, при приближении к красным областям необходимо тапать.

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

Возникает вопрос, а пересекаются ли синие и красные области в реальной игре? Оказывается, иногда пересекаются. И происходит это ровно в одном случае: когда возникает достаточно большой перепад высот вниз между проемами двух соседних труб.



Проанализируем данную ситуацию. Пусть птичка сумела пролететь через эти трубы. Значит, в какой-то момент времени она пересекла отрезок AB. Но это значит, что был совершен тап в области между обратными падаболами, проведенными из точек A и B. В то же время данный тап не мог быть произведен ни в синей области, ни в красной. Остается только область, изображенная на рисунке желтым цветом.

То есть для существования выигрышной стратегии нужно уметь гарантировать попадание в желтую область. Дальше останется только сделать тап и опасный участок будет преодолен. Для того, чтобы понять, всегда ли мы сможем попасть в желтую область, сложим ее с обратной падаболой – получим область (на рисунке зеленая), в которую достаточно попасть, чтобы за один тап долететь до желтой. Заметим, что если в какой-то момент времени будет совершен тап в точке, лежащей выше линии Г, в желтую область мы уже попасть не сможем. И наоборот, для любой точки ниже этой границы мы всегда можем, тапнув достаточное число раз подряд, подняться в зеленую область, дальше, тапнув один раз, попасть в желтую и, соответственно, преодолеть препятствие. Другими словами, точки, находящиеся выше линии Г в нашей терминологии стоит покрасить в синий цвет. Правда, по большей части они и так уже синие, за исключением криволинейного треугольника XYZ. Докрасим XYZ в синий. Теперь для формулировки выигрышной стратегии осталось добавить фразу: если птичка оказалась в желтой области, необходимо хоть раз тапнуть до того, как птичка эту область покинет.

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

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

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

Практика


Все это хорошо, но хотелось бы немного практических результатов. Хардварных ботов на хабре уже видели, так что мы решили сделать софтверный. Совершенно случайно под рукой оказался код нашего клона под названием Tappinator, физическая модель которого достаточно близка к оригинальной игре – старались, замеряли. У нас, правда, птичка круглая (хотя, может, она и во Flappy Bird круглая, но разница невелика, а с квадратной объяснять проще) и есть дополнительные препятствия – наклонные. Вот так «раздуваются» препятствия для круглой птички:



В результате синие и красные области у нас такие:



Что касается желтых областей, они все также возникают для стандартных труб, но кроме того возникают в случае наклонных препятствий, направленных снизу вверх (со своими криволинейными синими треугольниками и вообще):



Ну и, собственно, видео с ботами:



На видео можно увидеть как 50 птичек вполне успешно долетают до 1000, как выглядят всякие цветные области с точки зрения бота и как бы выглядела игра, если бы одновременно летело 1000 птичек. В незакрашенных областях боты ведут себя случайным образом: у каждого из них своя фиксированная вероятность принять решение о прыжке в каждый момент времени. Можно заметить, что с точки зрения бота цветные области несколько больше, чем с точки зрения математики. Дело в том, что бот имеет возможность принимать решение только 60 раз в секунду, да и физическая модель обновляется тоже дискретно.

Вывод


Вот так, оказывается даже в такой простой игре как Flappy Bird есть где развернуть математическую теорию. Причем в действительности самое интересное с этого момента только начинается. Дальше возникает вопрос, как быть с препятствиями произвольной формы – тут приходится вводить такие понятия как фиолетовая тень, бордовая граница, право-линейно-связная область, право-линейно-связное замыкание и т.д. Также интересно, какой реакцией должен обладать человек (то есть какова допустимая ошибка по времени при тапе у него должна быть), чтобы он смог играть до бесконечности. Между прочим, это крайне нетривиальный вопрос, строгий ответ на который нам до сих пор не известен.
@s3r4f1m
карма
75,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (32)

  • +98
    Yeah Science, Bitch
    • +3
      It works, bitches!
      xkcd
      Дополнительные очки тому, кто сможет объяснить при чем тут наука.
  • +17
    Походу автор этой игры сделал самый гениальный PR-ход в истории мобильной разработки: удалил ее. Теперь и клоны, и боты, и даже математический анализ игры появился. Даже в Angry Birds такого не было.
    • +4
      Было :) А ход действительно гениальный. Лично я не верю в то, что там обычный программист, которому случайно подвернулась удача.
    • +14
      Саус-парк, Картман и парк аттракционов, куда никому нельзя.
    • +4
      А что теперь имеет с этого автор?
      • +3
        Автор зарабатывал деньги не на продажах игры, а на показах рекламы в момент проигрыша. После удаления игры из стора уже установленные экземпляры никуда не девались, реклама показывается дальше.
      • 0
        А я узнал об игре и скачал ее на 4pda только потому что все новостные ресурсы написали про то что он ее удалил. Вот так. И я не один. И мы тоже смотрим ту же рекламу. А автор считает денежки =)
  • +1
    Действительно, здорово!
    Хочется знать, какие физические ограничения у человека и какие сочетания препятствий можно считать непроходимыми.
  • +16
    Вот это статья, а хабр всё ещё торт, да ещё какой!
  • +16
    Вот преподавали бы мне так в былые времена алгебру, матан, прогу и остальные предметы =(
    • +10
      Абсолютно согласен. В свое время, я не понял большую часть курса математики в университете, потому что преподаватели излагали сухую теорию, без перенесения этой теории на реальную жизнь. Наверное, если у тебя страсть к математике и склад ума нужный, ты все поймешь из такого изложения. Но я считаю, что для среднестатистического студента (к которым я себя относил) нужно все объяснять именно на примерах.

      Меня первый раз поразила математика, когда я прочитал несколько статей на хабре про распознавание образов и работу с изображениями пару лет назад. Именно тогда я подумал о том, ну почему же нам не рассказывали в вузе, что за всеми этими сухими формулами прячется такое интересное и наглядное применение.
      • +3
        Эх, ваша правда!

        upd: А может быть, есть и кто-нибудь знает онлайн-курсы матана, функана и проч. с наглядными примерами?
        И я, и многие другие были бы очень благодарны.
        На английском — тоже хорошо.
        • 0
          Присоединюсь к вопросу. Или книгу?
        • 0
          Из онлайн-курсов – www.khanacademy.org объясняют весьма наглядно и упражнения там отличные. Но иногда строгость хромает.
          Из книг – по матану можно посоветовать Calculus: Early Transcendentals — James Stewart.
          Если хочется что-то более оригинальное чем матан/функан, гляньте книгу Эдельсбруннера Computational Topology: An Introduction ( www.ee.oulu.fi/research/imag/courses/Vaccarino/Edels_Book.pdf тут текст, возможно, не полный, но начало точно есть). Там весьма актуальные темы, связанные, в частности, с компьютерным зрением, рассказываются с нуля и, насколько это возможно, простым языком.
        • 0
          В этом курсе есть практические примеры: Calculus: Single Variable.
      • +2
        О, а у меня была удивительная учительница по физике. Ей удалось оторвать физику от реальной жизни, хотя казалось бы физика описывает мир вокруг нас.
      • 0
        Мой преподаватель матанализа (и смежных дисциплин) почти для каждой из выведенных теорем приводил примеры использования, за что я ему очень благодарен. Другое дело, что примеры-то не всегда увлекательные, поэтому многие их пропускали мимо ушей. А сейчас появляются посты вконтакте типа: «мне эти ваши интегралы совсем не нужны в жизни».
  • +1
    Это гениально!
  • +2
    Спасибо вам большое за исследование! Люблю, когда доказывают, что за любым идиотизмом на самом деле лежит целая математическая теория.
  • +2
    Математика — царица наук!
    Еще в школе учительница так говорила, с каждым случаем ее такого применения все больше убеждаюсь в этом! Круто!:)
  • 0
    Надо на парах говорить вот это вам потребуется для прохождения того, а вон то для прохождения сего. И тогда через 5лет мы выиграем все киберспортивные соревнования, а через 15 покорим космос!:)

    P.S. Автор молодец!
  • +3
    И всё же автор так и не ответил на поставленный в самом начале вопрос.
    В оригинальной Flappy Bird может встретиться теоретически проигрышная комбинация труб или нет?
    • +7
      В оригинальной игре не может возникнуть непроходимой ситуации. Об этом говорит последнее утверждение. Это так, поскольку в оригинальной игре пересечения синих и красных областей возникает только при резком перепаде вниз. И даже при максимальном таком перепаде (порядка 200 пикселей на неретина iPhone) возникают стандартная желтая область и синий криволинейный треугольник.
      Есть правда один момент, который вероятно стоило упомянуть в статье: для понимания выигрышной стратегии (точнее всей совокупности выигрышных стратегий) игроку/боту более чем достаточно видеть на два препятствия вперед (ближайшее и следующее за ним) – что выполняется.
  • +4
    На заставку в фон главного меню Flappy Bird бы такого бота.
    • +8
      Ага, и со счётчиком очков. Чтобы все осознавали свою ничтожность.
  • +2
    Вот он! Вот он ответ всем тем, кто спрашивает в учебных заведения «Зачем мне это?».
    PS
    Большинство тех, кто такое спрашивает, задают риторический вопрос. Они оказались в учебном заведении случайно и их удел совершенно другой.
    • +2
      И какой ответ? Чтобы написать бота к игре Flappy Bird?
      • +2
        Чтобы уметь объяснить свои действия: те люди, которые самостоятельно набирают в Flappy Bird по 50-150 очков играют по той же методике, которая описана в статье, но они не могут это объяснить. Их мозг понимает что делает, а они сами — нет.
        • 0
          Я извиняюсь, но «зачем платить больше»?
          Т.е. если «они» и без этих знаний справляются, то зачем они им? Только чтобы объяснить другим? В чём профит?
          • +1
            В том, что когда ты понимаешь, что ты делаешь, ты можешь:
            • Намеренно совершенствовать свои умения в желаемом направлении
            • Обучать других
            • Переносить умения в другую сферу, частный случай чего — написание бота
            • 0
              Я к тому, что ваши аргументы работают только для «особых» (заинтересованных) людей, а обычным пользователям они не интересны, увы.

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