descine Nov 16 2015 at 12:49

Как устроен Code Game Challenge

4 min

11K

Website development*System Analysis and Design*Ruby on Rails*

Введение

Code Game Challenge (CGC) — формат соревнований, в котором игроки практикуются в написании игровых стратегий, определяющих поведение подконтрольных им юнитов в неком игровом мире. Этот вид соревнований — вечный завсегдатай более — менее крупных олимпиад по программированию.

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

Словарик статьи

Стратегия — код игрока, определяющий поведение юнита.
Такт — время, за которое код всех стратегий выполнится ровно 1 раз.
Симулятор — система, моделирующая состояние игрового мира, основываясь на коде стратегий.
Список действий (намерения юнита) — список, содержащий действия, которые юнит «хотел» бы совершить на текущем ходу.

Содержание

О Симуляторах
- Тактовый
- Реального времени
AI — Project

О Симуляторах

Мною найдено 2 основных подхода к разработке подобных систем. С одним из них я непосредственно работал. Начну с него:

1) Тактовый

Особенность: Существует система, которая каждый такт обрабатывает код игроков:

Верхний уровень

Заключается в том, что код всех игроков каждый такт прогоняется через симулятор, который моделирует поведение юнитов и просчитывает состояние игрового мира. Далее запоминается состояние игрового мира и все начинается с начала. Так продолжается до тех пор, пока не будет нарушено условие продолжения игры (найден победитель или превышено ограничение по ислу тактов).

Нижний уровень

Код стратегии, как правило имеет доступ к 2 интерфейсам:

Для получения информации о состоянии игрового мира
Для управления подконтрольным юнитом

Анализируя состояние игрового мира и давая команды юниту, стратегия игрока заполняет список действий юнита. Симулятор используя эти списки и информацию об игровом мире, моделирует игровой такт (выполняет определенное число действий из списков), периодически фиксируя состояние игрового мира. И так по кругу до победного конца.

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

Варианты реализации

1) Формат стратегии

Функция

def move(информация о состоянии игрового мира, интерфейс для управления юнитом)
  if (что - то случилось)
    Что - то сделать
end

+ Относительная простота реализации
— А где стратегии хранить данные между тактами?

Класс

class Strategy
  def init()
    # Создаем переменные для наших нужд
    # Настраиваем интерфейс взаимодействия с юнитом и игровым миром
  end

  def move()
    # Анализируем состоние игрового мира и реагируем на это,
    # давая команды подконтрольному юниту
  end
end

+ Проще для понимания
+ Просто реализовать хранение данных между запросами (переменные объекта)

2) «Обертка» стратегии

Процесс

Код обворачивается в оболочку процесса. Сервер по мере надобности запрашивает данные у процесса — стратегии.

+ Этот подход позволяет относительно просто реализовать поддержку многих языков для написания стратегий
+ Уменьшает число способов нанесения вреда серверу
— Сложность реализации

Подключаемый код

Код подключается в обрабатывающую систему (подобно .h файлам в C++).

+ Простота релизации
— Усложняется поддержка сторонних языков (стратегия пишется на языке обрабатывающей системы)
(Возможное решение проблемы — использование трансляторов)
— Враг уже внутри (необходима сложная архитектура для защиты симулятора)

Особенности «Тактового» подхода

Сложность разработки скрипта обрабатывающей системы
Все стратегии, вне зависимости от времени выполнения имеют равные шансы на успех
Отлично подходит для матчевых игр

2) Реального времени

Особенность: существует ресурс, к которому код игрока может обращаться в процессе своего выполнения.

Стратегия выполняется в цикле на клиенте или сервере, запрашивая данные и отсылая команды по мере необходимости.

Пример стратегии:

class Strategy
  def initialize
    ...
  end

  def move
    while (true) do
      # То, что делает этот код стратегией
    end
  end
end

Особенности подхода

Время выполнения стратегии влияет на ее шансы победить
Основную сложность составляет решение проблем синхронизации

Плюсы

+ Относительно первого способа, игроку сложнее навредить серверу
+ Хорошая платформа для игровых сессий, не ограниченных временными рамками.

AI — Project

История

Пол года назад, я случайно наткнулся на пост о том, что в моем городе проходили соревнования формата Code Game Challenge. Они были разовыми и датировались 2010 годом. Это подтолкнуло к созданию приложения, в котором можно можно было бы поучаствовать в соревнованиях подобного рода где угодно и когда угодно.

Так появился на свет AI — Project.

Характеристики

Вид стратегии: Класс
Язык написания стратегии: Ruby
Способ задания положения в пространстве: (x, y)
Игровой мир: квадратное поле, маги и файерболы

Какие технологии использовались

PIXI.js для визуализации результатов работы симулятора
CodeMirror для удобного браузерного редактора кода. Разработчики этого чуда наделили его весьма удобным интерфейсом
JQuery для обмена кодом с сервером и различной мелочевки
Ruby on Rails для написания серверной логики и симулятора

Об архитектуре

О симуляторе

Вид: “Тактовый”

Одной из основных задач симулятора является моделирование игрового мира. Сложность этого модуля симулятора зависит лишь от конечной цели (учитывать физику или нет, насколько сложной должны быть эта физика и т.д.). В симуляторе AI — Project этот модуль реализован сравнительно просто. Ниже представлена упрощенная схема придуманного для этого алгоритма.

Об игровых сессиях

Похожий по функциональности механизм реализован почти во всех матчевых online играх. Нужно набрать игроков, создать игру под них, ограничить их по времени, выдать статистику в конце.

Игровая сессия реализована в виде модели, хранящей код игроков, состояние и статистику. Сессия активна, пока не истечет время и существует до тех пора, пока последний игрок не покинет ее.

Наибольшую сложность при реализации для меня имело создание игровой сессии. А именно — как объединить в игровую сессию N игроков и перенаправить их на свои игровые страницы.

Как сделать все это в одном экшене, я на тот момент представлял очень смутно. Мое решение для 2-ух игроков:

Выполнение кода игроков

Около недели назад, я, исправив последний мешавший работе баг, решил в очередной раз протестировать механизм игровых сессий. После запуска кода, содержащего в себе строку Game.delete_all что — то пошло не так. Не вдаваясь в детали скажу, что у Ruby есть средства для решения подобных проблем в виде 5 — 6 гемов и собственного механизма защиты ($SAFE).

Ограничение по времени

Задачка с ограничением по времени решилась при помощи помощи продвинутого таймера на JavaScript (отображение оставшегося времени клиенту) и самодельного Back Ground Workerа для Ruby on Rails. При создании игровой сессии, создается поток, которые по истечении времени, отведенного на игру, делает ее не активной. После этого клиент не может совершать некоторые действия (например отправка кода).

Happy end

AI_Project

Tags:

Hubs: