После прочтения довольно любопытной исследовательской работы “Resource Entity Action: A Generalized Design Pattern for RTS games” я решил реализовать предложенную концепцию (в несколько упрощённом виде) на Haskell. Ниже пойдёт речь об идее подхода Resource-Entity-Action к проектированию RTS-игр (Command & Conquer, Age of Empires, StarCraft, …) и прочих симуляций, а также о том, как использовать библиотеку rea.

Подход Resource-Entity-Action⌗

Предложенная в статье выше идея довольно проста по своей сути: для описания логики некоторой RTS-игры мы используем трансферы абстрактных ресурсов между сущностями.

Resource⌗

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

Например, т.н. “юниты” на компьютерном поле боя обычно имеют позицию (координаты), запас снарядов, уровень повреждений, текущие приказы, текущий интервал перезарядки орудия, флаг “убит”/“живой” и т.д. В зависимости от задачей и механики игры, под ресурсом можно вообразить и более абстрактный компонент “юнита”: например, “система обнаружения, идентификации и отслеживания местоположения”.

Все параметры механики игры так или иначе обобщаются и представляются этими ресурсами.

Entity⌗

Сущность – это контейнер для одного и более типов ресурсов (не существует ресурса как такового в отрыве от сущности, в которой он находится). Например, самыми очевидными сущностями выступают юниты (армии, базы, космические корабли и т.п.).

В текущем дизайне rea я заложил одно важное ограничение: система допускает трансферы только между сущностями одного типа (то есть описание игры строится на описании одного типа Unit и его компонентов-ресурсов).

Action⌗

Под действием понимается одна инструкция по взаимному переносу ресурсов (обмену ресурсами) между двумя сущностями. Далее я буду использовать вместо “действия” слово “трансфер”. Итак, в исходной научной работе под трансфером довольно широко понимается конструкция, в которой указано:

1. В какую сущность
2. При выполнении каких условий
3. Из какой сущности
4. Переносить какие ресурсы и сколько (заметим, что перенос подразумевает взаимную мутацию сущностей: в одной прибыло, а другой убыло, - значит на выходе изменены обе сущности)
5. Дополнительно: если дан тест на “пороговое значение” (threshold) одного из ресурсов целевой сущности (например, урон достиг критического значения) и этот тест срабатывает
6. Что делать с сущностью при достижении данного порогового значения

Это я обобщил. На самом деле в работе описывается три трансфера:

• constant transfer (перенос в единственную сущность из константы, т.е. просто изменение значений ресурсов внутри одной сущности при выполнении данных условий)
• mutable transfer (полноценный обмен ресурсами между сущностями, состоящими в некотором отношении друг с другом)
• threshold transfer (два предыдущих трансфера с добавленным “пороговым тестом” и трансфером)

Решения при дизайне rea⌗

На мой взгляд, авторы понимают трансферы довольно широко и либерально, что может создать дополнительные трудности в проектировании и понимании мехиники игры: если один трансфер способен за раз изменить много ресурсов внутри сущности, то что мешает нам реализовать всю логику игры полностью в одном большом трансфере? Насколько сложным должен быть тест (предикат/отношение), который должен сработать или не сработать, если трансфер задействует множество ресурсов одновременно?

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

1. В rea существует четыре типа трансферов: constant, mutable, threshold constant и threshold mutable.
2. Все они не работают с наборами ресурсов, а используют только обособленные типы ресурсов (при создании трансферов для этой цели применяются линзы).
3. В интранзитивном случае (когда меняется одна сущность, т.е. constant и threshold constant) в качестве условия активации трансфера служит обыкновенный предикат над сущностью (а также некоторым environment)
4. В транзитивном случае, когда меняются обе сущности, условием активации служит простое отношение между сущностями (т.е. функция из квадрата сущностей в True/False).
5. В качестве “порогового теста” в threshold-трансферах применяется предикат строго над тем же ресурсом, что и был задействован в данном трансфере для целевой сущности.
6. При срабатывании “порогового теста”, система фактически исполняет обыкновенный constant-трансфер с предикатом True.

Библиотека rea⌗

Итак, пользоваться библиотекой намного проще, чем читать о её дизайне.

Интерфейс⌗

Для построения четырёх трансферов применяются четыре соответствующие функции, которым и передаются предикаты/отношения и линзы для доступа (из которых компилятор выводит типы и гарантирует корректность). Вот их сигнатуры:

-- | Constant resource transfer
cx :: (env -> e -> Bool)
      -> ASetter' e r
      -> (env -> e -> r)
      -> Transfer env e
cx pred sel rf = 
  ...

-- | Mutable resource transfer (exchange)
mx :: (env -> e -> e -> Bool)
                -> ASetter' e rsrc
                -> ASetter' e rdst
                -> (env -> e -> e -> (rsrc, rdst))
                -> Transfer env e
mx rel srcsel dstsel rf = 
  ...

-- | Constant resource transfer with a threshold transfer
tcx :: (env -> e -> Bool)
       -> Lens' e r1
       -> (env -> e -> r1)
       -> (r1 -> Bool)
       -> ASetter' e r2
       -> (env -> e -> r2)
       -> Transfer env e
tcx pred sel rf tpred tsel trf = 
  ...

-- | Mutable resource transfer with a threshold on first
tmx :: (env -> e -> e -> Bool)
       -> Lens' e rsrc
       -> ASetter' e rdst
       -> (env -> e -> e -> (rsrc, rdst))
       -> (rsrc -> Bool)
       -> ASetter' e r
       -> (env -> e -> r)
       -> Transfer env e
tmx rel srcsel dstsel rf tpred tsel trf = 
  ...

Как видно из сигнатур, всё довольно просто (мнемоники в именах параметров: rf - resource function, sel - selector).

Для выполнения трансферов используется монада Rea env e a (Reader над env, State над таблицей из a) и функция performTransfer (она возвращает количество произведенённых трансферов, т.е. количество запусков данного трансфера для данной в монаде таблицы) или sequenceTransfers:

performTransfer :: Eq e => Transfer env e -> Rea env e Int

sequenceTransfers :: Eq e => [Transfer env e] -> Rea env e ()

Монада Rea env e разворачивается в IO посредством runRea:

-- | Run a Rea computation (i.e. a game turn)
runRea :: Rea env e a -> env -> Database e -> (a, Database e)

То, что я называю здесь таблицей (где содержатся сущности e) имеет тип Database e и представляет собой IntMap из пакета containers.

Пример⌗

В качестве примера рассмотрим модель простенькой RTS-подобной игры, где юниты перемещаются к заданным в списке позициям (waypoints), атакуют соседей и перезаряжают орудия.

Преамбула⌗

Модули:

{-# LANGUAGE TemplateHaskell #-}
module Main where

import Rea

import Control.Monad
import Data.Maybe
import Linear
import Lens.Micro
import Lens.Micro.TH

Объявление типов данных, генерация линз⌗

Мы объявляем тип сущностей (юнитов), а также тип окружения (read-only environment типа игровой карты, которая затем передаётся во все предикаты и отношения). Для сущности мы обязательно генерируем линзы.

type Env = ()
data Unit
  = Unit
  { _unitName :: String
  , _unitPos :: V2 Double
  , _unitWps :: [V2 Double]
  , _unitAttack :: Int
  , _unitReloading :: Int
  , _unitDamage :: Int
  }
  deriving (Show, Eq)

makeLenses ''Unit

Описание логики игры в терминах трансферов⌗

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

move :: Transfer Env Unit
move =
  cx
    (\_ u -> not (u ^. unitWps . to null))
    unitPos
    (\_ u ->
       let wp = u ^. unitWps . to head
           pos = u ^. unitPos
           d = distance pos wp
           v = normalize $ wp ^-^ pos
       in
         if d <= 1 then wp else u ^. unitPos + v
    )


updateWps :: Transfer Env Unit
updateWps =
  cx
    (\_ u -> let mbwp = u ^. unitWps . to listToMaybe
             in
               case mbwp of
                 Nothing -> False
                 Just wp -> u ^. unitPos == wp
    )
    unitWps
    (\_ u -> u ^. unitWps . to tail)



fire :: Transfer Env Unit
fire =
  tmx
    (\_ u1 u2 ->
       distance (u1 ^. unitPos) (u2 ^. unitPos) < 3
       && u1 ^. unitAttack > 0
       && u1 ^. unitReloading == 0
    )
    unitAttack
    unitDamage
    (\_ u1 u2 ->
       (u1 ^. unitAttack - 1, u2 ^. unitDamage + 1)
    )
    talways
    unitReloading
    (\_ _ -> 3)


reload :: Transfer Env Unit
reload =
  cx
    (\_ u -> u ^. unitReloading > 0)
    unitReloading
    (\_ u -> u ^. unitReloading - 1)

Использование линз существенно упрощает код.

Компоновка “хода игры” в монаду Rea env e⌗

Далее мы компонуем трансферы в последовательность игрового хода, получая монаду Rea env e:

logic :: Rea Env Unit ()
logic = do
  sequenceTransfers [fire, reload, move, updateWps]

Запуск игровой логики⌗

И запускаем игру с некоторыми начальными значениями (таблица и окружение):

env = ()
db = fromList
  [
    Unit "unitA" (V2 0 0) [V2 10 10] 5 0 0
  , Unit "unitB" (V2 10 10) [] 5 0 0
  , Unit "unitC" (V2 0 0) [V2 10 10, V2 40 20] 5 0 0
  , Unit "unitD" (V2 1 1) [] 5 0 0
  ]

main :: IO ()
main =
    execRea logic env db

Производительность⌗

Вот производительность библиотеки rea для 1000 юнитов данной игры, постоянно находящихся рядом друг с другом для атаки и следующих вместе к одной локации.

  benchmarking 1000
  time                 1.774 s    (1.388 s .. 2.205 s)
                       0.989 R²   (0.988 R² .. 1.000 R²)
  mean                 2.021 s    (1.892 s .. 2.095 s)
  std dev              124.3 ms   (36.29 ms .. 166.8 ms)
  variance introduced by outliers: 19% (moderately inflated)

Замерено с помощью замечательного пакета criterion.