Мультиагентная система в дизайне кода C++

У меня есть симуляция, написанная на C++, в которой мне нужно поддерживать переменное количество агентов, и мне трудно решить, как ее реализовать. Каждый агент выглядит примерно так:

class Agent{
public:
    Vector2f pos;
    float health;
    float data[DATASIZE];
    vector<Rule> rules;
}

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

  1. Желательно, чтобы количество агентов не ограничивалось сверху.
  2. Я могу легко добавить агента
  3. Я могу легко удалить любого агента при некоторых условиях (скажем, здоровье‹0)
  4. Я могу легко перебрать всех агентов и что-то сделать (скажем, здоровье--)
  5. Желательно распараллелить работу с помощью openMP, т.к. многие обновления несколько затратны, но совершенно не зависят от других агентов.
  6. (редактировать) порядок агентов вообще не имеет значения

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

Спасибо


c++ containers openmp design-patterns multi-agent
person karpathy    schedule 30.08.2010    source источник
comment
Вы профилировали свой код? Если нет, то я бы пока не стал указывать пальцем на std::vector.   -  person Sam Miller    schedule 30.08.2010

Ответы (4)


arrow_upward
3
arrow_downward

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

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

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

Мой общий совет — продолжать использовать std::vector (при условии, что он соответствует остальной части вашего дизайна), если только вы действительно не ожидаете значительного числа смертей агентов за шаг по сравнению с общим количеством агентов.

person TheUndeadFish    schedule 30.08.2010
comment
вы правы, иногда для одной смерти может потребоваться несколько сотен итераций - person karpathy; 31.08.2010

arrow_upward
5
arrow_downward

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

foreach Agent {
    if (agent.health > 0) // skip dead agents
        process rules
person Graham Perks    schedule 30.08.2010
comment
Спасибо, я рассматривал это решение, но я делаю циклы для каждого агента во многих местах кода, и много раз я также делаю вложенные циклы агента для проверки расстояния и т. д., поэтому это решение, возможно, будет очень подвержено ошибкам в будущем. , где я мог случайно вовлечь мертвых агентов в различные расчеты. - person karpathy; 31.08.2010
comment
+1 за идею стека указателей. Я довольно эффективно использовал этот шаблон для пакетов связи в системе телеметрии с высокой пропускной способностью. Стек многократно используемых агентов был бы лучше, чем очередь, потому что вы с большей вероятностью будете повторно использовать агенты, которые все еще находятся в кеше. - person Emile Cormier; 31.08.2010
comment
Мне нравится идея с отдельным стеком указателей, я тоже попробую, спасибо! - person karpathy; 31.08.2010
comment
... конечно, в моем случае время жизни моих пакетов было очень коротким, и время выделения/освобождения памяти, вероятно, было бы непомерно высоким. - person Emile Cormier; 31.08.2010

arrow_upward
0
arrow_downward

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

Если вам не нужен обратный обход, slist так же хорош, как список, и немного быстрее.

Если вам не важен порядок элементов, используйте set.

person Beta    schedule 30.08.2010

arrow_upward
0
arrow_downward

Используйте дерево квадрантов, как в видеоиграх. Тогда поиск по pos будет быстрым, и удаление тоже будет быстрым. (Кроме того, вы можете распараллелить дочерние узлы).

person amwinter    schedule 30.08.2010