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

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

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

В чём идея

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

Текст:

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

Редак­ту­ра:

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

Худож­ник:

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

Кор­рек­тор:

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

Вёрст­ка:

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

Соц­се­ти:

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