STD :: Установить, что я должен использовать для организации объектов в иерархии?

Question

Я хочу организовать все мои объекты GameObjects в иерархическую структуру. Я бы предположил, что для этого было бы лучшим деревом. Я думал об использовании STD :: Set для обработки этого. Имеет ли это смысл? В принципе, GameObject может содержать переменное количество других GameObjects. Если я действительно обрабатываю его таким образом, тогда как лучше всего обращаться с обращением к объекту в дереве? Будет ли доступ к ним через ID достаточно быстрым? Полагаю, я мог бы также просто получить к ним доступ с помощью указателей, но передавать их вокруг звучит несколько опасно и утомительно, если вы попадете в ситуацию с большим количеством объектов.

Я также буду показывать эти данные, если это имеет какое-либо влияние.

EX:

-Hierarchy 
    -GameObject 
     -GameObject 
     -Gameobject 
    -GameObject 
     -GameObject 
      -GameObject 
    -GameObject 

Я ценю любые входные ребята. Благодарю.

Answer 1

Есть ли причина, по которой каждый «игровой объект» не может иметь массив игровых объектов в качестве переменной экземпляра? Возможно, ваш основной должен создать массив GameObjects, и каждый из этих игровых объектов может содержать продолжающиеся игровые объекты в переменной экземпляра массива. Вот как я думаю об этом, по крайней мере.

Answer 2

Для чего это стоит, я нахожу, что доступ к ним через «путь», немного как дерево каталогов на диске, работает достаточно хорошо. Это взято из некоторых C# код, который я пишу (обратите внимание, что я пропустил бит из ниже класса), но идея перевести прямолинейно на C++:

sealed class Entity : IEntity 
{ 
    private readonly IDictionary<string,IEntity> m_children = new Dictionary<string,IEntity>(); 

    private readonly IDictionary<string,dynamic> m_properties; 

    public string Name { get { return m_properties["Name"]; } } 

    public IEntity Parent { get; set; } 

    /// <summary> 
    /// Adds a child to this entity. 
    /// </summary> 
    /// <param name="child">The child to add.</param> 
    public void AddChild(IEntity child) 
    { 
     m_children.Add(child.Name, child); 
     child.Parent = this; 
    } 

    /// <summary> 
    /// Gets the absolute path of this entity in its tree. 
    /// </summary> 
    /// <returns>The entity's absolute path.</returns> 
    public string GetAbsolutePath() 
    { 
     IEntity cur = this; 
     var path = new LinkedList<string>(); 
     while(cur.Parent != null) 
     { 
      path.AddFirst(cur.Name); 
      cur = cur.Parent; 
     } 
     path.AddFirst("."); 
     return string.Join("/", path); 
    } 

    /// <summary> 
    /// Gets another entity in this entity's tree by its absolute path (i.e. its path relative to the root entity). 
    /// </summary> 
    /// <param name="path">The absolute path to the other entity.</param> 
    /// <returns>The other entity, if found, or null otherwise.</returns> 
    public IEntity GetEntityByAbsolutePath(string path) 
    { 
     return GetRootEntity().GetEntityByRelativePath(path); 
    } 

    /// <summary> 
    /// Gets another entity in this entity's tree by its absolute path (i.e. its path relative to the root entity). 
    /// </summary> 
    /// <param name="path">The absolute path to the other entity, as a list of path components.</param> 
    /// <returns>The other entity, if found, or null otherwise.</returns> 
    public IEntity GetEntityByAbsolutePath(LinkedList<string> path) 
    { 
     return GetRootEntity().GetEntityByRelativePath(path); 
    } 

    /// <summary> 
    /// Gets another entity in this entity's tree by its path relative to this entity. 
    /// </summary> 
    /// <param name="path">The relative path to the other entity.</param> 
    /// <returns>The other entity, if found, or null otherwise.</returns> 
    public IEntity GetEntityByRelativePath(string path) 
    { 
     return GetEntityByRelativePath(new LinkedList<string>(path.Split('/'))); 
    } 

    /// <summary> 
    /// Gets another entity in this entity's tree by its path relative to this entity. 
    /// </summary> 
    /// <param name="path">The relative path to the other entity, as a list of path components.</param> 
    /// <returns>The other entity, if found, or null otherwise.</returns> 
    public IEntity GetEntityByRelativePath(LinkedList<string> path) 
    { 
     IEntity cur = this; 

     while(cur != null && path.Count != 0) 
     { 
      switch(path.First()) 
      { 
       case ".": 
        break; 
       case "..": 
        cur = cur.Parent; 
        break; 
       default: 
        cur = cur.GetChild(path.First()); 
        break; 
      } 

      path.RemoveFirst(); 
     } 

     return cur; 
    } 

    /// <summary> 
    /// Gets the root entity of this entity's tree. 
    /// </summary> 
    /// <returns>The root entity of this entity's tree.</returns> 
    private IEntity GetRootEntity() 
    { 
     IEntity cur = this; 
     while(cur.Parent != null) 
     { 
      cur = cur.Parent; 
     } 
     return cur; 
    } 
} 

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

cityA.GetEntityByRelativePath("../city:B/building:1"); 

Answer 3

Я думал об использовании STD :: Set справиться с этим. Имеет ли это смысл?

Номер станд :: Комплект сделан для хранения коллекции уникальных объектов, где объекты упорядочены с использованием либо operator< или lessthan компаратора предоставленного пользователем. Нет смысла использовать std :: set для списка объектов.

Доступ к ним через ID будет достаточно быстрым?

Вот улов. Нет ID s в std::set. Есть объекты. Поэтому, если вы используете std :: set, вы не сможете получить доступ к объекту по ID без повторения всего набора (если только объекты не упорядочены по ID, но это еще одна история). Чтобы сопоставить что-то еще, вы используете std::map. std::set - для коллекций.

Если я действительно обрабатываю его таким образом, то каков наилучший способ обращения к объекту в дереве?

Лучшим способом, вероятно, будет использование списков или комментариев - в зависимости от того, как ваша игра будет обрабатывать объекты.

Нет никакого «лучшего» способа представления деревьев.

1. Вы можете хранить корневые объекты иерархии в списке И хранить дочерние объекты в родительских объектах.
2. Вы можете хранить все объекты в списке (как для детей, так и для родителей), для дочерних объектов хранить ссылку на родителя, а затем убедиться, что функция «update()» учитывает это.
3. Вы можете сохранить два списка: один для корневых объектов и другой для всех объектов. (например, вы вызываете обновление в первом списке и используете второй список для запросов на обнаружение конфликтов и т. д.)

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

но прохождение окружающих звуки несколько опасно

Да, это верный путь к краху игры, когда кто-то, кто выпустил ракету было вдребезги и ракета имеет указатель на владелец для дружественного огня проверить. Однако, поскольку ваш вопрос отмечен «boost», вы можете использовать boost::weak_ptr для решения этой проблемы. Также объекты могут быть сохранены как список shared_ptr в std :: list, std :: deque или even std :: vector - в зависимости от того, как ваша игра будет их использовать.

Answer 4

Я предполагаю, что вы хотите сделать что-то вроде этого:

class GameObject { 
    some_container<GameObject> nested_objects_; 
    .... 
} 

Если вы на самом деле не нужно O(log(n)) поиска и удаления в вашей коллекции объектов, я предложил бы использовать std::vector вместо этого, так что вы» ll избежать накладных расходов памяти, и (очень вероятно) некоторые издержки процессора тоже. Поэтому, если вам нужно хранить только несколько вложенных объектов на каждый объект, тогда обязательно выберите std::vector

Но если вам нужно быстро найти или удалить объекты или сохранить уникальность, то std::set может быть хорошим выбором. Чтобы использовать std::set, вам необходимо предоставить функцию сравнения, которая действует как оператор < (строго говоря, ваша функция сравнения должна быть strict weak ordering.) Вы можете просто определить operator < для вас GameObject класс. От этой функции зависит эффективность std::set, поэтому будьте осторожны.

Обратите внимание, что вы либо траверсы, весь набор или find индивидуальный GameObjects путем предоставления самого GameObject (строго говоря, вы можете предоставить его эквивалент - смотреть в функции сравнения). Поэтому, если вам нужно получить объекты по его идентификатору, лучше используйте std::map, он гораздо более подходит для такого типа работы. std::set reference. std::map reference

Я также предлагаю взглянуть на повышение :: unordered_set & повышающего :: unordered_map (или станд :: unordered_set & станд :: unordered_map, если вы можете использовать C++ 11).