Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

Подробный разбор видео с канала Code Bullet.

У нас очередной разбор видео Эвана Code Bullet. На этот раз он рассказывает, как пытался написать алгоритм, который будет за него играть в игру. Если знаете английский — наслаждайтесь видео и австралийским юмором:

Если не знаете или сразу хотите самую суть — читайте наш разбор.

В чём идея

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

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

Ищем подходящую игру

Первая проблема Эвана — найти браузерный пинг-понг, который бы выглядел более-менее нормально и имел простую графику. Через несколько попыток находится кандидат: 

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

Получаем изображение с экрана

Следующий шаг — научиться получать изображение того, что происходит на экране и как-то это обрабатывать. Для этого Эван использует наработки другого программиста, который написал алгоритм для управления транспортом в игре GTA 5. Это самый простой и рациональный путь, чтобы быстро получить нужный результат: посмотреть, решал ли кто подобную задачу, и взять это решение.

Скопировав код со страницы того проекта, Эван добавляет в свою программу такую логику:

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

Это нужно, чтобы алгоритм Эвана мог «видеть», что происходит на экране, анализировать это и выдавать какой-то результат. Минус такого решения в том, что на снятие скриншота и его обработку уходит какое-то время, за которое игровая ситуация может измениться. Но пока, кажется, этого хватит.

Управляем нажатием клавиш

Чтобы алгоритм сам управлял игрой, он должен уметь посылать туда нажатия клавиш. К счастью для Эвана, это тоже было реализовано в проекте с управлением транспортом в GTA, поэтому он просто копирует код оттуда, вставляет в свою программу и меняет клавиши на нужные для игры.

Первая версия: платформа просто движется вверх и вниз

Чтобы проверить код в деле, Эван делает первую версию своего алгоритма так: платформа движется вниз, доезжает до нижней границы, потом едет наверх до упора и всё повторяется. Для этого нужно:

  1. Сделать скриншот игры.
  2. Найти на нём свою платформу
  3. Посмотреть позицию верхних и нижних пикселей, где белый цвет платформы переходит в чёрный цвет фона.
  4. Понять, достигли мы верхней или нижней точки или нет.
  5. Если нет — послать нажатие соответствующей клавиши, а если достигли — отправить другую клавишу.

В жизни это выглядит так:

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

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

Отслеживаем движение платформы противника

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

Так как отслеживать движение мяча сложно, а платформы противника — просто, то Эван решает пойти на хитрость и сделать так:

  1. На каждом скриншоте Эван находит платформу противника.
  2. Анализирует её положение и сравнивает его с положением своей платформы. 
  3. Если платформа Эвана ниже, то нужно её чуть приподнять и снова проверить положение. Если выше платформы противника — слегка опустить и тоже перепроверить положение обоих платформ.

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

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

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

Всё-таки нужно отслеживать положение мячика.

Отслеживаем положение мяча на экране

Чтобы знать положение мяча и двигать свою платформу в соответствии с этим движением, Эван пишет код, который:

  1. Определяет отдельно стоящий квадрат на экране определённого размера.
  2. Принимает его за мяч и двигает платформу в сторону текущего положения мяча.
  3. Делает новый скриншот и ищет там мяч. Если находит — повторяет всё заново, если нет — то ждёт следующего скриншота. 

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

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

Оказывается, прямое отслеживание мяча тоже не помогает. Нужно другое решение.

Прогнозируем траекторию движения мяча

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

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

Для этого Эван делает два скриншота, находит мячики, по первой и второй точке строит линию движения и понимает, куда нужно заранее поставить платформу. Это существенно улучшает качество игры алгоритма Эвана:

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

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

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

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

Всё дело в кадрах

На высокой скорости кадры игры могут не успевать за реальным положением дел. Может оказаться так, что за то время, пока менялись кадры, что-то произошло, а алгоритм Эвана этого не заметил. 

Именно так и было: из-за низкой скорости отрисовки алгоритм Эвана не увидел момент отскока и думал, что его ещё не было:

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

Для решения этой проблемы Эван добавил проверку точки соприкосновения заранее, когда до неё ещё достаточно долго лететь. Как только мяч пересекает определённую точку невозврата, алгоритм временно перестаёт смотреть на кадры и надеется, что прогноз был точный. Это улучшило работу алгоритма, но не до идеала.

Но это не единственная проблема этого алгоритма: когда счёт меняется с 6 на 7, то алгоритм по непонятным причинам принимает семёрку за мяч и движется наверх, снова пропуская настоящий мяч. Что делать с этим Эван тоже не знает.

Как написать алгоритм, который за вас сыграет в пинг-понг в браузере

Выводы

Зачем выводы? Человек просто куражится, и мы с ним заодно.

Текст:

Михаил Полянин

Редактура:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Мария Дронова

Соцсети:

Олег Вешкурцев

Алгоритмы — основа разработки
Изучите алгоритмы, чтобы легко проходить ИТ-собеседования и делать более совершенный софт. Старт — бесплатно. Дальше — помощь с трудоустройством.
Новый уровень тут
Алгоритмы — основа разработки Алгоритмы — основа разработки Алгоритмы — основа разработки Алгоритмы — основа разработки
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства и компенсация, если вы пойдёте работать в «Яндекс».
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Говори как разработчик
Тест: Говори как разработчик
Как писать код и сразу видеть результат

Обзор инструментов крутых программистов.

Четыре проекта, где Machine Learning приносит пользу

Кроме дип-фейков!

Тест: какой язык программирования выбрать для старта
Три признака программиста-сноба
Три признака программиста-сноба

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

Как писать код и сразу видеть результат

Обзор инструментов крутых программистов.

Тест: Взломать Пентагон и выйти из Матрицы: что реально, а что — выдумка?
Взломать Пентагон и выйти из Матрицы: что реально, а что — выдумка?
5 вещей с Али, которые стоит заказать сегодня, чтобы они приехали к концу карантина
5 вещей с Али, которые стоит заказать сегодня, чтобы они приехали к концу карантина

Собери их все.

5 полезных функций Excel для начинающих программистов
5 полезных функций Excel для начинающих программистов

Необязательно писать код только на языках программирования — Excel тоже подходит.

Выбираем компьютер для программиста

Как выбрать то, что действительно нужно.

Нестыдные вопросы об ИТ

С чего начать, на что не тратить время, кому уже поздно.

Полезные плагины для сайта на jQuery

Галереи, параллакс, меню и всплывающие уведомления — обзор проверенных jQuery-плагинов.

5 трекеров активности для того, кто сейчас за компьютером
5 трекеров активности для того, кто сейчас за компьютером

Чтобы не умереть.

easy