Як Мінковський під Flappy Bird грав


 
Багато пробували грати під Flappy Bird. Рідко кому вдається пролетіти за 50 труб, дуже небагато долітають до сотні-двох. Деякі пробували створити бота, в тому числі на Хабре . Дивно, але навіть у самого успішного бота, якого можна знайти на просторах інтернету, результати не дуже-то вражають — щось близько 160 очок . Виникає питання, а чи можна взагалі грати у Flappy Bird нескінченно довго? Або завжди з деякою, нехай і невеликий, ймовірністю може зустрітися послідовність перешкод, яку навіть досвідчений гравець / ідеальний бот не зможе подолати?
 
І тут на допомогу приходить математика. Давайте знайдемо виграшну стратегію для Flappy Bird.
 
 

Модель

Опишемо математичну модель гри. Наше ігрове поле — площину. Є пташка — квадрат зі сторонами довжини w, паралельними координатним осях. Є перешкоди — труби — вертикальні смуги ширини w tube з горизонтальними прорізами висоти h gap . Відстань між двома сусідніми перешкодами по горизонталі фіксоване і дорівнює Δ tube . Розташування горизонтального прорізу для кожної труби випадково (рівномірно в деякому діапазоні). Крім того є підлога — горизонтальна пряма f. Пол — це теж перешкоду. Картинка:
 
 
 
Швидкість пташки по горизонталі постійна і дорівнює v x . На пташку також діє гравітація, надаючи їй вертикальне прискорення g. Спочатку швидкість пташки по вертикалі дорівнює 0. У кожен момент часу гравець може зробити тап, тобто зробити так, щоб вертикальна швидкість пташки стала дорівнювати v jump . Крім того, на пташку діє якусь подобу опору повітря — її вертикальна швидкість обмежена знизу константою v fall . Фактично, це означає, що після кожного тапа пташка рухається по параболі, що переходить в якийсь момент в пряму. Траєкторію, по якій рухається пташка після тапа, будемо називати падаболой (парабола падіння). Виглядає це так:
 
 
 
Гра закінчується, коли пташка стосується перешкоди. Завданням гравця є максимізація пройденої відстані.
 
Перш ніж переходити власне до стратегії проходження зробимо один фокус. Аналізувати перетину квадратної пташки з перешкодами не дуже-то зручно. Але, виявляється, легко перейти до еквівалентної моделі, в якій пташка є точкою. Для цього достатньо «здути» пташку до розміру точки (центра вихідного квадрата), одночасно «роздуваючи» перешкоди. При цьому початковий квадрат перетинається з перешкодами тоді і тільки тоді, коли нова точкова пташка лежить в роздутому перешкоді. Картинка:
 
 
 
По-науковому результат «роздуття» перешкод називається сумою Маньківського.
 
 

Сума Маньківського

Вікіпедія повідомляє:
 
Сумою Маньківського двох підмножин 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 (v jump / v x ) — тобто промінь, спрямований вздовж швидкості пташки в момент відразу після тапа. Нехай пташка виявилася нижче променя AC. Тоді незалежно від дій гравця вона не зможе підніматися з вертикальною швидкістю більшою ніж v jump . З урахуванням постійної горизонтальної швидкості v x це призводить до неминучого зіткнення з перешкодою, тобто програшу. Розфарбуємо нижнє перешкоду і область нижче променя AC в червоний колір. Ось такі червоні гірки виходять:
 
 
 
Виходить, що при будь виграшної стратегії пташка не повинна потрапляти в червоні області. Більш того, якщо пташка знаходиться поза червоній області в деякий момент часу, то вона зможе залишатися поза неї як завгодно довго. Дійсно, завжди при наближенні до кордону червоній області гравець може починати тапа досить часто, щоб не опинитися в ній.
 
Додамо підлогу. Нескладно бачити, що підлога можна сприймати як ще одну червону область у формі нижньої півплощини.
 
Таким чином, якщо присутні тільки нижні перешкоди і підлогу, то вірно:
 
Затвердження . Якщо пташка в початковий момент часу знаходиться поза об'єднання червоних областей, то існують нескінченні виграшні стратегії. Усі виграшні стратегії можна сформулювати так: поза червоній області гравець може приймати будь-які рішення, при наближенні до червоній області гравець повинен тапа.
 
 

Всі перешкоди разом

Розглянемо загальну ситуацію. Нехай є і верхні половинки труб, і нижні, і підлогу. Цілком зрозуміло наступне:
 
Затвердження . Якщо об'єднання синіх областей не перетинається з об'єднанням червоних і пташка спочатку знаходиться поза синіх і червоних областей, то існують виграшні стратегії. Будь виграшна стратегія описується так: поза синіх і червоних областей можна приймати будь-які рішення, в синіх областях тапа не можна, при наближенні до червоних областям необхідно тапа.
Відсутність перетинів синіх і червоних областей для існування такої стратегії суттєво. Дійсно, може так вийти, що пташка пролітаючи через синю область впритул наблизиться до кордону червоної — в цьому випадку якщо гравець тапнет, то програє, якщо не тапнет, теж програє.
 
Виникає питання, а чи перетинаються сині та червоні області в реальній грі? Виявляється, іноді перетинаються. І відбувається це рівно в одному випадку: коли виникає досить великий перепад висот вниз між прорізами двох сусідніх труб.
 
 
 
Проаналізуємо дану ситуацію. Нехай пташка зуміла пролетіти через ці труби. Значить, в якийсь момент часу вона перетнула відрізок AB. Але це значить, що був здійснений тап в області між зворотними падаболамі, проведеними з точок A і B. У той же час даний тап не міг бути вироблений ні в синій області, ні в червоній. Залишається тільки область, зображена на малюнку жовтим кольором.
 
Тобто для існування виграшної стратегії потрібно вміти гарантувати потрапляння в жовту область. Далі залишиться тільки зробити тап і небезпечна ділянка буде подоланий. Для того, щоб зрозуміти, чи завжди ми зможемо потрапити в жовту область, складемо її зі зворотного падаболой — отримаємо область (на малюнку зелена), в яку достатньо потрапити, щоб за один тап долетіти до жовтої. Зауважимо, що якщо в якийсь момент часу буде здійснений тап в точці, що лежить вище лінії Г, в жовту область ми вже потрапити не зможемо. І навпаки, для будь-якої точки нижче цієї межі ми завжди можемо, тапнув достатню кількість раз поспіль, піднятися в зелену область, далі, тапнув один раз, потрапити в жовту і, відповідно, подолати перешкоду. Іншими словами, точки, що знаходяться вище лінії Г в нашій термінології варто пофарбувати в синій колір. Правда, здебільшого вони і так вже сині, за винятком криволінійного трикутника XYZ. Докрасіть XYZ в синій. Тепер для формулювання виграшної стратегії залишилося додати фразу: якщо пташка виявилася в жовтій області, необхідно хоч раз тапнути до того, як пташка цю область покине.
 
Зауважимо, що дораскрашіваніе трикутнички в синій колір не могло додати пересічний червоних і синіх областей, а тому не вплинуло на аналіз прохідності гри в цілому.
 
У підсумку, в загальному випадку отримуємо:
 
Затвердження . Нехай пташка в початковий момент часу знаходиться поза синіх і червоних областей. Тоді існують нескінченні виграшні стратегії. Всі такі стратегії можна описати так: поза синіх і червоних областей можна тапа в будь-який момент часу; в синіх областях тапа можна; при наближенні до червоних необхідно тапа; потрапивши в жовту область, потрібно тапнути хоч один раз до виходу з неї.
Цікаво, що стратегія виду почати політ вище деякої лінії і тапа, як тільки пташка до неї опускається (наприклад, в якості такої лінії логічно було б взяти верхню межу червоних областей, трохи зрушену вгору) виграшною мабуть не буде ні для якої лінії.
 
 

Практика

Все це добре, але хотілося б трохи практичних результатів. Хардварних ботів на Хабре вже бачили, так що ми вирішили зробити софтверний. Зовсім випадково під рукою виявився код нашого клона під назвою Tappinator, фізична модель якого досить близька до оригінальної гри — старалися, заміряли. У нас, правда, пташка кругла (хоча, може, вона й під Flappy Bird кругла, але різниця невелика, а з квадратною пояснювати простіше) і є додаткові перешкоди — похилі. Ось так «роздуваються» перешкоди для круглої пташки:
 
 
 
В результаті сині та червоні області у нас такі:
 
 
 
Що стосується жовтих областей, вони все також виникають для стандартних труб, але крім того виникають у разі похилих перешкод, спрямованих знизу вгору (зі своїми криволінійними синіми трикутниками і взагалі):
 
 
 
Ну і, власне, відео з ботами:
 
  
На відео можна побачити як 50 пташок цілком успішно долітають до 1000, як виглядають всякі кольорові області з точки зору бота і як би виглядала гра, якби одночасно летіло 1000 пташок. У незакрашенних областях боти поводяться випадковим чином: у кожного з них своя фіксована ймовірність прийняти рішення про стрибок в кожен момент часу. Можна помітити, що з точки зору бота кольорові області дещо більше, ніж з точки зору математики. Справа в тому, що бот має можливість приймати рішення тільки 60 разів на секунду, та й фізична модель оновлюється теж дискретно.
 
 

Висновок

Ось так, виявляється навіть у такій простій грі як Flappy Bird є де розгорнути математичну теорію. Причому насправді найцікавіше з цього моменту тільки починається. Далі виникає питання, як бути з перешкодами довільної форми — тут доводиться вводити такі поняття як фіолетова тінь, бордова межа, право-лінійно-зв'язкова область, право-лінійно-зв'язне замикання і т.д. Також цікаво, якою реакцією має володіти людина (тобто яка допустима помилка за часом при тапе у нього повинна бути), щоб він зміг грати до нескінченності. Між іншим, це вкрай нетривіальне питання, строгий відповідь на який нам досі не відомий.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.