4

我想将我所有的游戏对象组织成一个层次结构。我认为一棵树是最好的主意。我考虑过使用 STD::Set 来处理这个问题。这有任何意义吗？基本上，一个游戏对象可以容纳可变数量的其他游戏对象。如果我确实以这种方式处理它，那么处理访问树中对象的最佳方法是什么？通过 ID 访问它们是否足够快？我想我也可以通过指针访问它们，但是如果遇到有很多对象的情况，传递它们听起来有点危险和乏味。

如果有任何影响，我也会显示这些数据。

前任：

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

我感谢任何输入的家伙。谢谢。

4

4 回答 4

3

我假设你想做这样的事情：

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

如果您真的不需要O(log(n))在您的对象集合中搜索和删除，我建议std::vector您改用，这样您就可以避免内存开销，并且（很可能）也会避免一些 CPU 开销。因此，如果您只需要为每个对象存储几个嵌套对象，那么一定要选择std::vector

但是如果您需要快速查找/删除对象或保持唯一性，那么std::set可能是一个不错的选择。为了使用std::set你需要提供一个比较函数，它的作用就像一个<运算符（严格来说，你的比较函数必须是严格的弱排序。）你可以operator <为你定义一个GameObject类。的效率std::set取决于这个函数，所以这里要小心。

请注意，您可以通过提供自身来遍历、整个集合或find个体（严格来说，您可以提供其等价物 - 查看比较函数）。所以如果你需要通过它的 id 来获取对象，更好地使用它，它更适合这种类型的工作。 参考。 参考GameObjectsGameObjectstd::mapstd::setstd::map

我还建议研究 boost::unordered_set 和 boost::unordered_map（或 std::unordered_set 和 std::unordered_map 如果你可以使用 C++11）。

于 2012-04-08T02:07:56.867 回答
1

每个“游戏对象”不能将游戏对象数组作为实例变量是否有原因？也许您的 main 应该创建一个 GameObjects 数组，并且这些游戏对象中的每一个都可以将正在进行的游戏对象保存在一个数组实例变量中。至少我会这么想。

于 2012-04-08T01:27:31.783 回答
1

我考虑过使用 STD::Set 来处理这个问题。这有任何意义吗？

不，std::set 用于存储唯一对象的集合，其中对象使用用户提供的任何一个operator<或lessthan比较器进行排序。没有理由将 std::set 用于对象列表。

通过 ID 访问它们是否足够快？

这就是问题所在。中没有IDs std::set。有物体。因此，如果您使用 std::set，您将无法在ID不遍历整个集合的情况下访问对象（除非对象按 ID 排序，但这是另一回事）。将某些东西映射到您使用的其他东西std::map。std::set用于收藏。

如果我确实以这种方式处理它，那么处理访问树中对象的最佳方法是什么？

最好的方法可能是使用列表或双端队列——这取决于你的游戏处理对象的方式。

没有代表树木的“最佳”方式。

  1. 您可以将层次结构的根对象存储在列表中，并将子对象存储在父对象中。
  2. 您可以将所有对象存储在列表中（子对象和父对象），子对象存储对父对象的引用，然后确保“update()”函数将其考虑在内。
  3. 您可以存储两个列表 - 一个用于根对象，另一个用于所有对象。（例如，您在第一个列表上调用更新，并使用第二个列表进行碰撞检测查询等）

所有这些方法都是有意义的，并且对于某些场景很有用。

但是绕过那些听起来有些危险

是的，当发射导弹的人被炸成碎片并且导弹指向所有者进行友军射击检查时，这肯定会导致游戏崩溃。但是，由于您的问题被标记为“提升”，您可以使用它boost::weak_ptr来处理这个问题。对象也可以存储为shared_ptrstd::list、std::deque 甚至 std::vector 中的 ' 列表 - 取决于您的游戏将如何使用它们。

于 2012-04-08T02:06:06.050 回答
0

对于它的价值，我发现通过“路径”访问它们，有点像磁盘上的目录树，效果很好。这取自我正在编写的一些 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");
于 2012-04-08T01:44:25.560 回答