Пусть компьютер сам принимает решение или пишем ИИ для игры вместе

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


Под катом gif-файлов мегабайт на 10.

Об игре

В игре вы управляете мотоциклом, который оставляет за собой стену из света. Игровое поле ограничено, а у соперников такие же мотоциклы. Мотоцикл едет постоянно, вы лишь можете поворачивать. Свободное место на поле кончается, и избегать препятствия становится сложнее. Побеждает тот, кто дольше всех продержится. Клон игры я сделал браузерным многопользовательским с использованием node.js и socket.io. Управление из двух кнопок – поворот влево и поворот вправо.

Интерфейс бота

Так как я использую socket.io, то обработка игроков на сервере у меня была в виде работы над массивом специальных объектов socket, которые создаёт socket.io. Из этих объектов я использовал только id, функции emit и broadcast. А значит безболезненно для самой игры можно реализовать интерфейс socket и использовать его в обработке, будто играет ещё один пользователь. Я назвал класс BotSocket.
Метод emit(event, data) у бота выполняет почти такие же действия что и у клиента при входящих данных от сервера, а именно:

1. Сохраняет данные обо всех играющих мотоциклах при их добавлении
2. Сохраняет ссылку на свой мотоцикл при его добавлении
3. Обновляет данные обо всех играющих мотоциклах
4. Сбрасывает состояния при перезапуске игры

Для передачи команд управления своим мотоциклом на сервер потребовалось сохранить ссылку на объект игры, который обрабатывает такие команды от обычных пользователей. Метод класса Game у меня назван onControl(socket, data), поэтому я добавил метод в BotSocket

BotSocket.prototype.control = function(data) {
  this.game.onControl(this, data);
};

При поступлении от сервера команды обновления данных мотоциклов (было совершено их передвижение) я проверяю, есть ли у меня вообще подконтрольный мотоцикл, не столкнулся ли он еще и был ли он перемещён, и, в случае успеха, я вызываю основной метод для работы ИИ — update().
Интерфейс готов, теперь можно добавить сам ИИ.

Искусственный интеллект

Как бы громко это не звучало, но в играх игроков, за которых играет компьютер, принято называть именно ИИ, либо ботами. Объект BotSocket обладает необходимыми данными об игре, чтобы принять решение. Вариантов решения может быть всего три:

1. Ничего делать, ехать прямо
2. Повернуть направо
3. Повернуть налево

Когда я решил написать бота, я понятия не имел, как это можно сделать. Я попробовал очень простой код:

BotSocket.prototype.update = function()  {
    var r = Math.random();
    if (r > 0.95) {
        this.control({'button': 'right'});
    } else if (r > 0.90) {
        this.control({'button': 'left'});
    }
}

Поведение было примерно таким:


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

Но хотелось, чтобы он жил как можно больше. Я стал искать информацию о том, как пишут ИИ к играм. Нашел статьи, которые описывали разные подходы. Но я искал что-то чрезвычайно простое. Я нашел на хабре в одной из статей про бота для игры вроде Zuma упоминание волнового метода. Он же алгоритм Ли. Мне он показался очень простым и подходящим. Это алгоритм поиска кратчайшего пути из одной точки в другую по полю, где клетки могут быть либо свободными, либо занятыми. Суть простая. Мы начинаем из точки назначения, присваиваем ей значение 1 и помечаем все соседние свободные клетки цифрой на единицу больше. Затем берём все соседние свободные помеченных и снова помечаем на единицу больше. Так расширяемся на всё поле, пока не дойдем до точки назначения. А путь строим поиском из соседних по уменьшению числа, пока не дойдем до 1. Я смотрел алгоритмы поиска кратчайших путей в графах, но этот мне показался наиболее подходящим.

Я перенёс алгоритм копипастой из страницы в вики, дал ему имя BotSocket.prototype.algorithmLee. Для поля я создал сначала объект battleground, в котором при каждом обновлении помечал занятые точки с их координатами. А в алгоритме Ли сводил это поле к такому же, но с шагом 1.

Нужно было как-то определять точку назначения. Я решил выбирать её случайно через определенные интервалы времени. Сделал метод для поиска случайной свободной точки на поле:

BotSocket.prototype.getDesiredPoint = function() {
  var point = [];
  var H = Object.keys(this.battleground[0]).length - 1;
  var W = Object.keys(this.battleground).length - 1;
  var x, y, i, j;
  var found = false;
  var iter = 0;
  do {
    i = this.getRandomInt(1, W);
    j = this.getRandomInt(1, H);
    x = i * this.moveStepSize;
    y = j * this.moveStepSize;
    if (this.battleground[x][y] === this.BG_EMPTY) {
      found = true;
    }
    iter++;
  } while (!found && iter < 100);

  point = [x, y];
  return point;
};

Теперь я мог переписать update:

BotSocket.prototype.update = function() {
  if (!this.desiredPoint || this.movements % this.updDestinationInterval === 0) {
    this.desiredPoint = this.getDesiredPoint();
  }

  if (!this.desiredPoint) {
    return;
  }

  var currentPoint = [this.myBike.x, this.myBike.y];
  var path = this.algorithmLee(currentPoint, this.desiredPoint);

  if (path && typeof path[1] !== 'undefined') {
    this.moveToPoint(path[1]);
  } else {
    this.desiredPoint = this.getDesiredPoint();
  }
};

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

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

Бот на стороне клиента

Я решил попробовать перенести бота на клиентскую часть. Так как проект на node.js, я могу использовать написанный код для бота и на стороне клиента. Для этого я расширил BotSocket отдельным клиентским файлом, который переопределял методы emit() и control(), чтобы правильно взаимодействовать с сервером без ссылки на объект game.
Локально всё работало отлично, а после деплоя на удалённый сервер была какая-то странная картина:


Долго думая, я понял, что дело в задержке. Бот отправлял команду поворота, но она доходила после обновления его позиции на сервере, отчего он часто не мог попасть на прямой путь к желаемой точке. Но я хотел нормального бота на клиентской стороне. Поэтому решил учитывать задержку. Для этого написал снова расширение BotSocket. Статья получается длинной, так что опишу основные решения. Перед вызовом алгоритма Ли вместо текущей точки я подставлял прогнозируемое положение с учетом текущего положения и направления, а так же множителя задержки. Множитель задержки – это число, во сколько раз превосходит задержка частоту обновления положения на сервере. Предсказание будущей точки мне еще понадобилось в методе moveToPoint().

Предсказание работало, если играл один. Но если были другие участники, то бот не учитывал это и направлял туда, где через некоторое время уже проехал другой игрок. Для решения этой проблемы я изменил метод, который помечает клетки поля занятыми. Я стал их помечать занятыми в некотором радиусе движения мотоциклов. Радиус зависит от множителя задержки.
Предварительно я снабдил бота функциями отладки, который рисовали на поле желаемую точку и занятые точки. Моя версия клиентского бота с учетом задержки теперь двигается так:

Мой красненький, остальные серверные.

Самое важное – попробуйте сделать бота сами

Основная цель этой статьи – пробудить интерес к написанию бота. Я сделал много, чтобы победить вашу лень. Для этого я добавил возможность подгружать свой собственный скрипт с ботом, который будет расширять мой базовый клиентский класс. Зайдите на проект и нажмите на текст «Show options for room with your own bot», а затем на кнопку «Create room for test your own bot». Будет создана комната, где можно легко применять ботов, по умолчанию вашим ботом будет бот без учета задержки. Теперь настало время для вашего кода.
Два простых варианта для использования вашего кода в деле, используйте любой:

1. Выкладывайте js-файл на любой сервер, который будет доступен вашему браузеру. Url к вашему скрипту вставляйте в игре рядом с кнопкой “Load your AI script”. После нажатия на эту кнопку будет создан и заполнен новый объект botSocket, у которого будет вызван метод start().
2. Используйте консоль браузера (Firebug – F12, Firefox — Ctrl+Shift+K, Chrome – Ctrl+Shift+J, другие – здесь).

Если вы определились с методом ввода вашего кода, попробуйте переопределить методы класса BotSocket. Для начала самое простое:

BotSocket.prototype.update = function()  {
    var r = Math.random();
    if (r > 0.95) {
        this.control({'button': 'right'});
    } else if (r > 0.90) {
        this.control({'button': 'left'});
    }
}

После этого пересоздайте объект botSocket, введя

botSocket = null;

При этом код на странице сам пересоздаст и заполнит объект. Этим вы измените стандартное поведение бота на случайное. А дальше уже дело для вашей фантазии или глубоких знаний.
Вы так же можете подключить скрипт моего улучшенного бота с учетом задержки, вставив в url для бота https://raw.github.com/rnixik/tronode-js/master/public/javascripts/MyBotSocketClient.js

Заключение

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

Исходный код на Github: github.com/rnixik/tronode-js

Если у вас нет под рукой node.js, вы можете воспользоваться развернутыми мной приложениями:

1) tronode.livelevel.net — самая дешевая VPS на DigitalOcean,
2) tronode-js.herokuapp.com — бесплатная виртуальная единица на Heroku.

Первый, скорее всего, первым может не справиться с нагрузкой, а второй на некоторых компьютерах сбрасывает socket.io-транспорт в xhr-polling, из-за этого игра очень сильно лагает.
Если вы хотите узнать больше, о том, как я программировал игровую логику, то можете прочитать здесь. Там же о развертке node.js и немного о графической части.

Если у вас нет аккаунта на хабре, то задать вопросы или прислать свои интересные предложения можете мне на почту dev@1i1.be.