要使用什么数据结构来存储基于2D单元的游戏对象映射?

I know you're probably thinking 2D array or 2D vector, but hear me out.

我知道你可能在想二维数组或二维矢量，但听我说。

I'm actually already using a 2D array for tilemaps, which works great. However, I'm trying to develop a data structure that can store game objects positioned on top of such a tilemap.

实际上我已经在用2D数组来表示tilemaps了，效果很好。然而，我正在尝试开发一种数据结构，它可以存储位于这样一个tilemap之上的游戏对象。

My requirements are as follows:

我的要求如下:

• The object map must allow many objects to be positioned at the same cell

  对象映射必须允许在同一单元格中放置许多对象

• The object map must be iterable by rows and columns, so that I can cull the iteration space to certain coordinates (this is so I can render only the objects that are actually on-screen, among other things)

  对象映射必须通过行和列来迭代，这样我就可以将迭代空间裁剪到特定的坐标(这是这样的，我只能渲染实际屏幕上的对象，以及其他的东西)

• Preferably, the object map should also offer fast lookup to determine 1: What objects are at a given cell, 2: Whether a given object is currently on the object map somewhere and 3: The position of a given object on the object map

  最好的情况是，对象映射还应该提供快速查找，以确定1:给定单元格中的对象是什么，2:给定对象当前是否在对象映射的某个位置，3:给定对象在对象映射中的位置

I have drafted up a basic data structure that uses two STL containers:

我起草了一个使用两个STL容器的基本数据结构:

• A 3D std::map<int, std::map<int, std::vector<Object*>>> is used to provide an iterable, easily culled container. The std::vector is used so that many objects can be contained at the same cell. A cell can also be accessed via _map[x][y].

  一个3D std::map >>，用于提供一个可迭代的、容易被过滤的容器。使用std::vector可以在同一个单元格中包含许多对象。单元也可以通过_map[x][y]访问。 ,>

• Additionally, I am using a 1D std::map<Object*, Vec2<int>*>, which contains the very same objects as the 3D std::map, except I think it will allow faster searching since it is 1D. The reason Vec2<int>* is a pointer is so that a GameObject may ask the ObjectMap for its position on the map, possibly save it, and then in future immediately access it without the need for a search.

  另外，我使用的是1D std::map *，>

Given my requirements, are there more suitable containers available than the ones I've used?

根据我的要求，有比我用过的更合适的容器吗?

If it helps, I've pasted my code for the ObjectMap below:

如果有帮助的话，我粘贴了下面ObjectMap的代码:

#pragma once
#include <vector>
#include <map>

template<typename T>
struct Vec2 {
    Vec2() { x = 0; y = 0; }
    Vec2(T xVal, T yVal) : x(xVal), y(yVal) {}
    void Set(T xVal, T yVal) { x = xVal; y = yVal; }
    T x, y;
    Vec2& operator+=(const Vec2& rhs) { x += rhs.x; y += rhs.y; return *this; }
    Vec2 operator+(const Vec2& rhs) { return Vec2<T>(x + rhs.x, y + rhs.y); }
};

/// <summary>
/// Represents a map of objects that can be layered on top of a cell-based map
/// Allows for multiple objects per map cell
/// </summary>
template <typename Object>
class ObjectMap {
public:
    /// <summary>
    /// Gets the objects located at the given map cell
    /// </summary>
    /// <param name="row">The row of the cell to inspect</param>
    /// <param name="column">The column of the cell to inspect</param>
    /// <returns>
    /// A pointer to a vector of objects residing at the given cell.
    /// Returns a nullptr if there are no objects at the cell.
    /// </returns>
    std::vector<Object*>* At(int row, int column);

    /// <summary>
    /// Checks whether the ObjectMap contains the given object
    /// </summary>
    /// <param name="object">A pointer to the object to check for</param>
    /// <returns>True if the ObjectMap contains the object</returns>
    bool Contains(Object* object);

    /// <summary>
    /// Adds the given object to the ObjectMap at the given cell
    /// </summary>
    /// <param name="object">The object to add to the map</param>
    /// <param name="row">The row of the cell to add the object to</param>
    /// <param name="column">The column of the cell to add the object to</param>
    /// <returns>True if successful, false if the object is already in the ObjectMap</returns>
    bool Add(Object* object, int row, int column);

    /// <summary>
    /// Moves the given object by some number of rows and columns
    /// </summary>
    /// <param name="object">The object to move</param>
    /// <param name="rows">The number of rows to move the object by</param>
    /// <param name="columns">The number of columns to move the object by</param>
    /// <returns>True if successful, false if the object does not exist in the ObjectMap</returns>
    bool MoveBy(Object* object, int rows, int columns);

    /// <summary>
    /// Moves the given object to the given cell
    /// </summary>
    /// <param name="object">The object to move</param>
    /// <param name="row">The row of the cell to move the object to</param>
    /// <param name="column">The column of the cell to move the object to</param>
    /// <returns>True if successful, false if the object does not exist in the ObjectMap</returns>
    bool MoveTo(Object* object, int row, int column);

    /// <summary>
    /// Gets the position of the given object
    /// </summary>
    /// <param name="object">A pointer to the object to check the position of</param>
    /// <returns>
    /// A pointer to the position of the object.
    /// Returns a nullptr if the object does not exist in the ObjectMap.
    /// </returns>
    Vec2<int>* GetPosition(Object* object);
private:
    /// <summary>
    /// A 3D container allowing object access via cell positions
    /// Provides the ability to iterate across sections of the map
    /// Useful for object culling and rendering
    /// Useful for object lookup when the position is known
    /// Example: _map[a][b] is a vector objects positioned at the map cell (x=a,y=b)
    /// </summary>
    std::map<int, std::map<int, std::vector<Object*>>> _map;

    /// <summary>
    /// A 1D container of all objects and pointers to their positions
    /// Useful for quickly checking whether an object exists
    /// Useful for quickly getting the location of an object
    /// </summary>
    std::map<Object*, Vec2<int>*> _objects;
};

/// 
/// ObjectMap.tpp
/// The implementation has not been separated into a .cpp file because templated 
/// functions must be implemented in header files.
/// 
/// See http://*.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file
/// 
#include <algorithm>

template <typename Object>
std::vector<Object*>* ObjectMap<Object>::At(int column, int row) {
    // Checks whether a key exists for the given column
    if (_map.find(column) != _map.end()) {
        // Checks whether a key exists for the given row
        if (_map.at(column).find(row) != _map.at(column).end()) {
            // Return the objects residing in the cell
            return &_map.at(column).at(row);
        }
    }
    return nullptr;
}

template <typename Object>
bool ObjectMap<Object>::Contains(Object* object) {
    return _objects.find(object) != _objects.end();
}

template <typename Object>
bool ObjectMap<Object>::Add(Object* object, int column, int row) {
    if (!Contains(object)) {
        _objects[object] = new Vec2<int>(column, row);
        _map[column][row].push_back(object);
        return true;
    }
    return false;
}

template <typename Object>
bool ObjectMap<Object>::MoveBy(Object* object, int columns, int rows) {
    Vec2<int> newPosition = *_objects[object] + Vec2<int>(columns, rows);
    return MoveTo(object, newPosition.x, newPosition.y);
}

template <typename Object>
bool ObjectMap<Object>::MoveTo(Object* object, int column, int row) {
    if (Contains(object)) {
        // Get the position reference of the object
        Vec2<int>* position = _objects[object];

        // Erase the object from its current position in the map
        auto *oldTile = &_map[position->x][position->y];
        oldTile->erase(std::remove(oldTile->begin(), oldTile->end(), object), oldTile->end());

        // Erase any newly-empty keys from the map
        if (oldTile->size() == 0) {
            _map[position->x].erase(_map[position->x].find(position->y));
            if (_map[position->x].size() == 0) {
                _map.erase(_map.find(position->x));
            }
        }

        // Add the object to its new position on the map
        _map[column][row].push_back(object);

        // Set the position of the object
        position->Set(column, row);

        return true;
    }

    return false;
}

template <typename Object>
Vec2<int>* ObjectMap<Object>::GetPosition(Object * object) {
    if (Contains(object)) {
        return _objects[object];
    }
    return nullptr;
}

2 个解决方案

#1

You left one important part of the question unspecified: What percentage of your map cells won't ever get to hold an object?

您留下了一个重要的问题:您的映射单元格中有多少百分比不会保存一个对象?

• If that percentage is very high (95% at the very least), your map<int, map<int, vector<>>> approach looks fine.

  如果这个百分比非常高(至少是95%)，那么您的map >>方法看起来很好。 ,>

• If that percentage is just high, a vector<map<int, vector<>>> would be better.

  如果这个百分比很高，那么向量

• If that percentage is modest (anywhere in the proximity of 50% or lower), you should go for a vector<vector<vector<>>>.

  如果这个百分比是适中的(接近50%或更低的地方)，你应该选择一个向量 <向量<向量<> >>。

The reasoning behind this is, that std::vector<> is vastly more efficient than std::map<int, > in the case that most elements are actually used. Indexing into an std::vector<> means just a bit of pointer arithmetic and a single memory access, whereas indexing into an std::map<> means O(log(n)) memory accesses. That's already a factor of 7 for just 128 entries. The std::map<> only has the advantage of reducing memory consumption in the presence of unused indices, which may bloat a sparsely used std::vector<>.

这背后的原因是，如果实际使用了大多数元素，那么std::vector<>要比std::map 高效得多。向量<>表示指针算法和一个内存访问，而索引std::map<>表示O(log(n))内存访问。对于128个条目，这已经是7的因数了。std:::map<>只具有在未使用索引的情况下减少内存消耗的优点，这可能会导致使用较少的std::vector<>。 ，>

Now, if your count of unused cells is not very high, you have to expect pretty much every line of your 2D array being filled with something. Accordingly, the container holding the lines should be a vector<>. The same argument goes for using vector<> for the lines themselves if you expect a decent density of entries.

现在，如果未使用单元格的计数不是很高，那么就必须期望几乎每一行2D数组都被填满。因此，保持线条的容器应该是一个向量<>。同样的论点也适用于向量<>对于直线本身，如果你想要一个合适的密度的条目。

---

If your objects can only ever be at a single position within the map at any given time, you might also consider of just linking them up in an intrusive linked list. In that case, you would drop your map container from 3D to 2D, and then iterate through a linked list of objects that happen to be within the same bin.

如果您的对象在任何给定时间只能位于映射中的单个位置，那么您也可以考虑将它们链接到一个入侵链接列表中。在这种情况下，您可以将映射容器从3D拖到2D，然后遍历碰巧位于同一bin中的对象的链接列表。

Of course, that is only a valid option as long as the linked lists of objects are expected to be very small on average.

当然，这只是一个有效的选择，只要对象的链接列表平均来说是很小的。

#2

You might want to look into Binary Space Partitions, which offer very fast lookup times eg for objects on screen.

您可能想要查看二进制空间分区，它为屏幕上的对象提供了非常快的查找时间(例如)。

For a grid, a good spacial structure is QuadTrees.

对于网格来说，一个好的空间结构就是四叉树。