What data structure to use for storing a 2D cell-based map of GameObjects?

Question

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.

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

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

• 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].

• 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.

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:

#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://stackoverflow.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;
}

Answer 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.

• 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<>>>.

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<>.

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.

---

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.

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

Answer 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.