У нас очередной разбор видео Эвана Code Bullet. На этот раз он рассказывает, как пытался написать алгоритм, который будет за него играть в игру. Если знаете английский — наслаждайтесь видео и австралийским юмором:
Если не знаете или сразу хотите самую суть — читайте наш разбор.
В чём идея
Обычно Эван делает алгоритмы для игр так: вместо того чтобы брать готовую игру, Эван пишет свой простой аналог и прикручивает алгоритм уже к нему. Но в этот раз идея была именно в том, чтобы:
- Взять уже готовую браузерную игру, например пинг-понг.
- Написать код, который мог бы управлять этой игрой самостоятельно, без того, чтобы самому нажимать на клавиши.
- Добавить к этому коду алгоритм для игры, чтобы выиграть.
Ищем подходящую игру
Первая проблема Эвана — найти браузерный пинг-понг, который бы выглядел более-менее нормально и имел простую графику. Через несколько попыток находится кандидат:
Получаем изображение с экрана
Следующий шаг — научиться получать изображение того, что происходит на экране и как-то это обрабатывать. Для этого Эван использует наработки другого программиста, который написал алгоритм для управления транспортом в игре GTA 5. Это самый простой и рациональный путь, чтобы быстро получить нужный результат: посмотреть, решал ли кто подобную задачу, и взять это решение.
Скопировав код со страницы того проекта, Эван добавляет в свою программу такую логику:
- Алгоритм может получать скриншоты любой области экрана, например, окна с игрой.
- После этого скриншот можно проанализировать и найти на нём ключевые детали: обе платформы и мячик.
Это нужно, чтобы алгоритм Эвана мог «видеть», что происходит на экране, анализировать это и выдавать какой-то результат. Минус такого решения в том, что на снятие скриншота и его обработку уходит какое-то время, за которое игровая ситуация может измениться. Но пока, кажется, этого хватит.
Управляем нажатием клавиш
Чтобы алгоритм сам управлял игрой, он должен уметь посылать туда нажатия клавиш. К счастью для Эвана, это тоже было реализовано в проекте с управлением транспортом в GTA, поэтому он просто копирует код оттуда, вставляет в свою программу и меняет клавиши на нужные для игры.
Первая версия: платформа просто движется вверх и вниз
Чтобы проверить код в деле, Эван делает первую версию своего алгоритма так: платформа движется вниз, доезжает до нижней границы, потом едет наверх до упора и всё повторяется. Для этого нужно:
- Сделать скриншот игры.
- Найти на нём свою платформу
- Посмотреть позицию верхних и нижних пикселей, где белый цвет платформы переходит в чёрный цвет фона.
- Понять, достигли мы верхней или нижней точки или нет.
- Если нет — послать нажатие соответствующей клавиши, а если достигли — отправить другую клавишу.
В жизни это выглядит так:
Видим, что всё работает как нужно: клавиши отправляются, код умеет находит границы платформы и управлять её движением. Можно двигаться дальше.
Отслеживаем движение платформы противника
Судя по движению платформы компьютера, разработчик сделал свой алгоритм так же, как и мы в своём непобедимом пинг-понге — платформа компьютера всегда движется за мячом, чтобы гарантированно его отбить.
Так как отслеживать движение мяча сложно, а платформы противника — просто, то Эван решает пойти на хитрость и сделать так:
- На каждом скриншоте Эван находит платформу противника.
- Анализирует её положение и сравнивает его с положением своей платформы.
- Если платформа Эвана ниже, то нужно её чуть приподнять и снова проверить положение. Если выше платформы противника — слегка опустить и тоже перепроверить положение обоих платформ.
В теории это должно сработать, потому что мы как бы точно копируем заведомо беспроигрышные движения. Но на практике это выглядит так:
Всё дело в том, что платформа противника получает данные напрямую из кода самой игры, поэтому её движения абсолютно точные. Нам же приходится анализировать скриншоты и всё время двигать платформу. Так как на оба этих действия уходит какое-то время, то наша платформа иногда опаздывает и не успевает отбить мяч.
Всё-таки нужно отслеживать положение мячика.
Отслеживаем положение мяча на экране
Чтобы знать положение мяча и двигать свою платформу в соответствии с этим движением, Эван пишет код, который:
- Определяет отдельно стоящий квадрат на экране определённого размера.
- Принимает его за мяч и двигает платформу в сторону текущего положения мяча.
- Делает новый скриншот и ищет там мяч. Если находит — повторяет всё заново, если нет — то ждёт следующего скриншота.
Не всегда удаётся определить точное положение мяча по пикселям, потому что когда мяч пересекает прерывистую линию центра или касается платформы противника, он перестаёт быть отдельным квадратом и сливается с другими элементами на экране. В этот момент программа не знает, как реагировать на такое, и просто ждёт следующего скриншота:
Оказывается, прямое отслеживание мяча тоже не помогает. Нужно другое решение.
Прогнозируем траекторию движения мяча
Эван решает подключить геометрию и снова схитрить — вместо того чтобы следить за каждым положением шарика, можно просто выяснять его траекторию и заранее ставить платформу в точку отскока. Поясним на рисунке:
Для этого Эван делает два скриншота, находит мячики, по первой и второй точке строит линию движения и понимает, куда нужно заранее поставить платформу. Это существенно улучшает качество игры алгоритма Эвана:
Кажется, что непобедимый алгоритм готов, но несколько минут спустя, когда скорость игры возрастает, случается такое:
Как же так, ведь алгоритм должен был просчитать траекторию заранее, а мы видим, что он ошибся, потом понял это, но было уже поздно. Как это могло произойти?
Всё дело в кадрах
На высокой скорости кадры игры могут не успевать за реальным положением дел. Может оказаться так, что за то время, пока менялись кадры, что-то произошло, а алгоритм Эвана этого не заметил.
Именно так и было: из-за низкой скорости отрисовки алгоритм Эвана не увидел момент отскока и думал, что его ещё не было:
Для решения этой проблемы Эван добавил проверку точки соприкосновения заранее, когда до неё ещё достаточно долго лететь. Как только мяч пересекает определённую точку невозврата, алгоритм временно перестаёт смотреть на кадры и надеется, что прогноз был точный. Это улучшило работу алгоритма, но не до идеала.
Но это не единственная проблема этого алгоритма: когда счёт меняется с 6 на 7, то алгоритм по непонятным причинам принимает семёрку за мяч и движется наверх, снова пропуская настоящий мяч. Что делать с этим Эван тоже не знает.
Выводы
Зачем выводы? Человек просто куражится, и мы с ним заодно.
