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

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

Я уже реализовал базовую систему конвейера задач на Javascript (потому что это упростило мою жизнь), но мне хотелось чего-то более надёжного и масштабируемого, поэтому этот проект я написал на C++. На это меня сподвиг конкурс по реализации процедурного сада в сабреддите /r/proceduralgeneration (отсюда и соответствующая тема).

В моей системе симуляция состоит из трёх компонентов: мира, населения и связывающих их набора действий. Следовательно, мне нужно было создать три модели, о которых я расскажу в этой статье.

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

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

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

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


Пример карты. Вода приняла форму реки совершенно ненамеренно. Все другие элементы расположены случайно, в том числе и муравейник, который в этом seed смещён слишком далеко к краю (но река выглядит красиво).

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

Я подробнее хочу описать структуру систем задач и памяти, а также показать, как создавалась сложность из (в основном) примитивных базовых функций. Также я хочу показать некоторые забавные «утечки памяти муравьёв», с которыми можно столкнуться, когда муравьи начинают безумно бегать кругами в поисках травы или стоять на месте и заставлять программу тормозить.

Общая структура

Я написал эту симуляцию на C++, а для рендеринга использовал SDL2 (раньше я уже написал небольшой класс представления для SLD2). Также я использовал реализацию A* (слегка изменённую), которую нашёл на github, потому что моя реализация была безнадёжно медленной, и я не мог понять, почему.

Карта — это просто сетка 100?100 с двумя слоями — слоем почвы (используется для поиска путей) и слоем заливки (для выполнения задач взаимодействия и поиска путей). Класс мира также обрабатывает различные косметические функции, например, рост травы и растительности. Я говорю об этом сейчас, потому что это единственные части, которые не будут описаны в статье.

Население

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

Самыми важными здесь были вспомогательные величины, определяющие поведение. А именно: вектор, содержащий их текущий путь A*, чтобы его не нужно было пересчитывать в каждом такте (это экономит время вычислений и позволяет симулировать больше ботов), и очередь памяти, определяющая интерпретацию существами их окружения.

Очередь памяти

Очередь памяти — это простая очередь, содержащая набор объектов памяти, ограниченных по размеру свойством бота. При каждом добавлении новых воспоминаний они выталкивались вперёд, а всё, что выходило за границы сзади, отрезалось. Благодаря этому одни воспоминания могли быть более «свежими», чем другие.

Если бот хотел вспомнить информацию из памяти, то он создавал объект памяти (запрос) и сравнивал его с находившимся в памяти. Затем функция вспоминания возвращала вектор воспоминаний, соответствующих любому или всем критериям, указанным в запросе.

class Memory{
  public:
    //Recall Score
    int recallScore = 1;

    //Memory Queryable? Array
    bool queryable[4] = {false, false, false, false};

    //Memory Attributes
    std::string object;
    std::string task;
    Point location;
    bool reachable;

Воспоминания состоят из простого объекта, содержащего несколько свойств. Эти свойства памяти считаются «ассоциированными» друг с другом. Также каждому воспоминанию задаётся величина «recallScore», которая итерируется каждый раз, когда воспоминания вспоминаются функцией recall. Каждый раз, когда бот вспоминает воспоминания, он выполняет сортировку в один проход по очереди, начиная сзади, меняя порядок воспоминаний, если recallScore более старого воспоминания выше, чем у нового. Благодаря этому некоторые воспоминания могут быть более «важными» (при больших размерах памяти) и дольше сохраняться внутри очереди. Со временем они будут вытеснены новыми.

Очереди памяти

Также я добавил в этот класс несколько перегруженных операторов, чтобы можно было выполнять прямые сравнения между очередью памяти и запросом, сравнивая «любые» или «все» свойства, чтобы при перезаписи памяти переписывались только указанные свойства. Благодаря этому у нас может быть память объекта, связанная с каким-то местом, но если мы заглядываем в это место снова и объекта там нет, мы можем обновить память, перезаписав её памятью, содержащей новый тайл заливки, с помощью запроса, соответствующего этому месту.

void Bot::updateMemory(Memory &query, bool all, Memory &memory){
  //Loop through all existing Memories
  //"memories" queue is a member of Bot 
  for(unsigned int i = 0; i < memories.size(); i++){
    //If all matches are required and we have all matches
    if(all && (memories[i] == query)){
      //We have a memory that needs to be updated
      memories[i] = memory;
      continue;
    }
    //If not all matches are required and any query elements are contained
    else if(!all && (memories[i] || query)){
      //When overwriting, only overwrite specified quantities
      memories[i] = memory;
      continue;
    }
  }
}

В процессе создания кода этой системы я многому научился.

Система задач

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

В этом разделе я объясню два взгляда на структуру системы задач, предназначенной для противодействия этому эффекту.

Структура «снизу вверх»

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

Примеры таких примитивных действий:

//Primitives
bool wait(Garden &garden, Population &population, int (&arguments)[10]);
bool look(Garden &garden, Population &population, int (&arguments)[10]);
bool step(Garden &garden, Population &population, int (&arguments)[10]);
bool swap(Garden &garden, Population &population, int (&arguments)[10]);
bool store(Garden &garden, Population &population, int (&arguments)[10]);
bool consume(Garden &garden, Population &population, int (&arguments)[10]);
bool move(Garden &garden, Population &population, int (&arguments)[10]);

//Continue with secondaries here...

Заметьте, что эти действия содержат ссылки и на мир, и на население, позволяющие изменять их.

• Wait заставляет существо ничего не делать в этом цикле.
• Look парсит окружение и записывает в очередь новые воспоминания.
• Swap берёт предмет в руке существа и заменяет его на лежащий на земле.
• Consume уничтожает предмет в руке существа.
• Step берёт текущий вычисленный путь в точку назначения и выполняет один шаг (с кучей проверок на ошибки).
• … и так далее.

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

//Secondaries
bool walk(Garden &garden, Population &population, int (&arguments)[10]);
bool idle(Garden &garden, Population &population, int (&arguments)[10]);
bool search(Garden &garden, Population &population, int (&arguments)[10]);
bool forage(Garden &garden, Population &population, int (&arguments)[10]);
bool take(Garden &garden, Population &population, int (&arguments)[10]);

//Species Masters
bool Ant(Garden &garden, Population &population, int (&arguments)[10]);
bool Bee(Garden &garden, Population &population, int (&arguments)[10]);
};

В этих вторичных функциях мы конструируем функции, просто соединяя в цепочки другие задачи:

• Задача walk — это просто несколько шагов (с обработкой ошибок)
• Задача take — это задача look и swap (она необходима из-за обработки памяти муравья, которую я объясню позже)
• Задача idle — это выбор случайного места и движения туда (с помощью walk), ожидание в течение нескольких циклов (с помощью wait) и повторение этого цикла в течение заданного количества раз
• … и так далее

Другие задачи более сложны. Задача search выполняет запрос к памяти для поиска любых воспоминаний о местах, содержащих объект «пища» (съедобного для данного вида ботов). Она загружает эти воспоминания и обходит их все, «ища» пищу (в случае муравьёв это трава). Если воспоминаний о пище нет, задача заставляет существо случайно бродить по миру и оглядываться. Смотря и изучая (выполняя “look” с viewRadius = 1; т.е. смотря только на тайл под собой), существо может обновлять свою память информацией об окружениях, разумно и целенаправленно ища пищу.

Более обобщённая задача forage состоит из поиска пищи, подбирания это пищи, осматривания (для обновления памяти и поиска пищи по соседству), возврата домой и складирования пищи.


Можно заметить, что муравьи выбираются из муравейника и ищут пищу целенаправленно. Из-за инициализации первоначальный путь муравьёв направлен к случайной точке, потому что их память в t = 0 пуста. Затем им отдаётся приказ подбирать пищу в задаче forage, также они осматриваются, убеждаясь, что пищи уже нет. Время от времени они начинают блуждать, потому что у них заканчиваются места, в которых они видели пищу (зловещая недальновидность).

И, наконец, у бота есть «вид», определяющий род задаваемого ему ИИ. Каждый вид связан с одной управляющей задачей, задающей всё его поведение: она состоит из каскада всё более мелких задач, с лёгкостью определяемых набором очередей памяти и примитивных задач. Это задачи наподобие «Ant» и «Bee».

Структура «сверху вниз»

Если смотреть сверху вниз, то система состоит из класса «task-master», который координирует управляющие задачи и их исполнение для каждого отдельного бота на карте.

Taskmaster имеет вектор управляющих задач, каждая из которых связана с ботом. Каждая управляющая задача, в свою очередь, имеет очередь из подзадач, которые загружаются при первой инициализации объекта задачи связанной с ним функцией-задачей.

class Task{
  public:
    //Members
    std::stack<Task> queue;
    bool initFlag = true;
    int args[10];
    bool (Task::*handle)(Garden&, Population&, int (&)[10]);
    int botID;
    std::string name;

    //Constructor
    Task(std::string taskName, int taskBotID, bool (Task::*taskHandle)(Garden&, Population&, int (&)[10])){
      name = taskName;
      botID = taskBotID;
      handle = taskHandle;
    }

    //Launch a Task
    bool perform(Garden &garden, Population &population);

    //Continue with primitives here...

Каждый объект задачи в очереди хранит массив аргументов, который передаёт связанному обработчику функции. Эти аргументы определяют поведение этих примитивных задач, созданных как можно более общими. Аргументы передаются по ссылке, поэтому объект задачи в очереди может хранить свои аргументы и позволять изменять их своим подфункциям, поэтому можно реализовывать такие вещи, как итерации для ожидания в течение определённого количества тактов или запросов на сбор определённого количества предметов, и т.д. Подфункции изменяют значение итератора (argument[n]) родительской функции по ссылке и делают своё условие успеха зависимым от её значения.

В каждом такте taskmaster проходит по списку управляющих задач и выполняет их, вызывая их метод perform. Метод perform, в свою очередь, смотрит на верхний элемент очереди внутри задачи и выполняет его с аргументами из задачи. Таким образом можно каскадно спускать вниз очереди задач, всегда выполняя самую верхнюю задачу. Затем возвращаемое значение задачи определяет завершённость задачи.

//Execute Task Function
bool Task::perform(Garden &garden, Population &population){
  //Debug Message
  if(debug){std::cout<<"Bot with ID: "<<botID<<" performing task: "<<name<<std::endl;}
  //Change the Name and Execute the Task
  population.bots[botID].task = name;
  return (*this.*handle)(garden, population, args);
}

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

Задача, содержащая очередь задач, возвращает true после опустошения очереди. Благодаря этому можно создавать сложные задачи со структурой очередей и подочередей, в которых постоянно вызываются одинаковые функции, но каждый вызов на один шаг итерирует состояние игры и состояние задачи.

Наконец, управляющие задачи используют простую структуру — они вызываются в каждом цикле, загружают задачу, только если пусты, а в противном случае выполняют задачи, загруженные в их очередь.

//Species Functions
bool Task::Ant(Garden &garden, Population &population, int (&arguments)[10]){
  //Initial Condition
  if(initFlag){
    Task forage("Search for Food", botID, &Task::forage);
    forage.args[0] = population.bots[botID].forage; //What are we looking for?
    queue.push(forage);
    initFlag = false;
  }

  //Queue Loop
  if(!queue.empty()){
    //Get the Top Task
    Task newtask = queue.top();
    queue.pop();

    //If our new Task is not performed successfully
    if(!newtask.perform(garden, population)){
      queue.push(newtask);
      return false;
    }
    //If it was successful, we leave it off
    return false;
  }

  //Return Case for Mastertask
  initFlag = true;
  return false;
}

С помощью моего цикла очереди (см. код) я могу многократно выполнять одну функцию и каждый раз выполнять верхний элемент в её очереди, выталкивая из неё элементы, если вызов их метода perform возвращает true.

Результаты

Всё это обёрнуто в libconfig, поэтому параметры симуляции изменять очень легко. Можно без проблем закодировать множество управляющих задач (я создал муравьёв и пчёл), а определение и загрузка новых видов с помощью libconfig удивительно просты.

//Anthill General Configuration File
debug = true;

//World Generation Parameters
seed = 15;
water = true;

//Species that the simulation recognizes
Species: {
  //Ant Species
  Ant: {
    masterTask = "Ant";
    color = (0, 0, 0);
    viewDistance = 2;
    memorySize = 5;
    forage = 2;
    trail = true;
    fly = false;
  }
  Bee: {
    masterTask = "Bee";
    color = (240, 210, 30);
    viewDistance = 4;
    memorySize = 30;
    forage = 4;
    trail = false;
    fly = true;
  }
  Worm: {
    masterTask = "Bee";
    color = (255, 154, 171);
    viewDistance = 1;
    memorySize = 5;
    forage = 3;
    trail = true;
    fly = false;
  }
}

Population: (
  {species = "Ant"; number = 40;}//,
  //{species = "Bee"; number = 12;},
  //{species = "Worm"; number = 5;}
)

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


Одновременная симуляция 40 муравьёв, собирающих траву. Создаваемые ими в песке пути возникают благодаря повышенному весу, назначаемого «неутоптанной» земле. Это приводит к созданию характерных «муравьиных шоссе». Также их можно интерпретировать как феромоны, но это больше походило бы на правду, если бы муравьи на самом деле обменивались воспоминаниями.

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

Отладка воспоминаний муравьёв

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

Вот три особенно сложных багов памяти, которые заставили меня переделать подсистемы:

Бегающие по кругу муравьи

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

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

Я исправил это следующим образом: данные объекта просто переписываются в старых воспоминаниях, если мы видим то же место и объект при этом изменился (например, существо видит, что там больше нет травы, но не помнит, что там раньше была трава). Возможно, в будущем я просто добавлю к воспоминаниям свойство «invalid», чтобы боты могли запоминать старую информацию, которая может быть важной, но больше не действительная информация «проявлялась» («здесь я видел медведя, но теперь его нет»).

Муравьи подбирают предметы под другими муравьями

Время от времени (особенно при большом количестве муравьёв и высокой плотности травы) два муравья могут попасть на один тайл травы в один такт и попытаться подобрать его. Это означало, что первый муравей входил на тайл, оглядывался и брал предмет за 3 шага. В свою очередь, второй муравей делал то же самое, только прямо перед поднятием предмета другой муравей выхватывал его из под носа. Он спокойно продолжал свои задачи, осматривая то же самое окружение, что и другой муравей в предыдущем такте, и обрабатывал свою очередь памяти аналогичным образом (потому что на этом этапе их воспоминания идентичны). Это приводило к тому, что второй муравей копировал первого, никогда не подбирая предметы и следуя за первым, который на самом деле выполнял всю работу. Я заметил это, потому что в симуляции из пяти муравьёв видно было только трёх. На обнаружение причины ушло много времени.

Эту проблему я решил, сделав задачу swap примитивной и создав задачу take, которая сначала смотрит на землю, чтобы увидеть, есть ли там предмет. Если он есть, она «обменивается» (swap), а если нет, то она «ждёт» (wait) два хода, чтобы другой муравей точно ушёл с места. В одном случае это действие на два такта, в другом — на один такт.

Недостижимые локации

Ещё один неприятный баг, заставивший меня переделать обработку памяти, заключался в том, что некоторые места, которые мог видеть муравей, были для него недостижимы. Они возникали из-за моего ленивого размещения «крестиков травы» на суше, которые иногда нависали над водой. Это заставило меня обобщить задачу step.

При передаче запроса на поиск пищи у муравьёв часто возникали воспоминания о местах, до которых они на самом деле не могли добраться (они видели траву над водой и безумно хотели её собрать). Если она не была помечена в их памяти (например, булевой переменной «reachable»), то они продолжали вспоминать это и записывать в очередь, пока это действие не оставалось единственным. Это вызывало сильное торможение, потому что они постоянно выполняли в каждом такте операции поиска пути, пытаясь добраться туда, и терпели неудачу.

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

Система в общем

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

Созданная мной система надёжна не на 100%, и я до сих пор замечаю некоторые артефакты. Например, в качестве направления для парсинга действия look используется вверх-вниз и влево-вправо, то есть последнее воспоминание находится в нижнем правом углу. При вспоминании информации для выполнения поиска предметов это означает, что существа будут склонны двигаться на юго-восток. Особенно это заметно на больших симуляциях, когда, трава растёт быстро и чуть-чуть склоняется в сторону юго-востока вне зависимости от seed.

Улучшения

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

В том числе и увеличение надёжности функций обработки памяти, а также добавление новых примитивов, например «think», и производных высокоуровневых задач, например «decide» или «dream». «think» может быть примитивным действием запроса к памяти. «dream», в свою очередь, может состоять из нескольких вызовов «think»: выбор случайной памяти, получение случайного свойства и многократное повторение для подкрепления частых тем или важных ассоциаций.

На будущее я планирую три конкретных дополнения:

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

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

Общение между сущностями, вероятно, состоит из одной или двух примитивных задач для обмена воспоминаниями или осуществления запросов к воспоминаниям других ботов (например, «say» или «ask»). Таким образом можно передавать информацию, например, расположение пищи или других ресурсов.

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

Будущее

Важнейшей функцией для симуляции сообществ будет добавление групповых структур и наделение этих групп макроуровневыми свойствами, например, их общими «целями и обязанностями». Это даёт нам своего рода «seed», из которого мы можем получать высокоуровневые задачи, которые делегируются вниз по иерархии групповых структур до «нижних» высокоуровневых задач, непосредственно влияющих на мир. Также это позволяет создать форму политической структуры.

Такая система довольно самодостаточна, а визуализация просто наложена поверх неё. Очень просто будет заменить насекомых на гуманоидов, собирающих ресурсы и складирующих их в каком-то месте, чтобы оно росло в размерах. Природа роста их жилища может, например, очень зависеть или полностью быть независимой от действий ботов. У разных видов могут быть разные племена с разными характеристиками и тенденциями.

Кроме того, я могу скомбинировать эту систему с созданными ранее генераторами карт (расширив класс мира), чтобы мир стал более реальным.

В заключение

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

Ждите следующей статьи. А пока вот видео с пчёлами, ищущими пыльцу в цветах; они закодированы с помощью той же основы.


Я выбрал этот seed, потому что начальная точка расположена на небольшом острове. Однако пчёлы не запрограммированы возвращаться в улей, а просто постоянно собирают пыльцу. Можно заметить, что их дальность зрения выше и иногда они очень намеренно движутся к цветку, который только что увидели.

… а вот функция-член Bee Task:

bool Task::Bee(Garden &garden, Population &population, int (&arguments)[10]){
  //Just Search for Flowers
  if(initFlag){
    //Define our Tasks
    Task take("Take Food", botID, &Task::take);
    Task eat("Eat Food", botID, &Task::consume);
    Task search("Locate Food", botID, &Task::search);
    search.args[0] = population.bots[botID].forage;
    queue.push(eat);
    queue.push(take);
    queue.push(search);
    initFlag = false;
  }

  //Work off our allocated queue.
  if(!queue.empty()){
    //Get the Top Task
    Task newtask = queue.top();
    queue.pop();
    //If our new Task is not performed successfully
    if(!newtask.perform(garden, population)){
      //Put the Task back on
      queue.push(newtask);
    }
    //If it was successful, we leave it off
    return false;
  }
  initFlag = true;
  return true;
}