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

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

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

В чём идея

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

Алгоритмы — основа разработки

Изучите алгоритмы, чтобы легко проходить ИТ-собеседования и делать более совершенный софт. Старт — бесплатно. После обучения — помощь с трудоустройством.

Новый уровень тут