How to pick proper sorted container?

Question

I'm developing a real-time game client C++. And wondering how to pick container correctly.

Server sends new game objects (monsters, players), their changes and their removal. All of them have to be stored in a single container called World identified by unique <int>ID. So the most common operations are getObjByID() to change something and push_back(), remove(). Besides that client have to dynamically sort that World by objects fields like Distance or Type to pick an object for clients needs. That sorting can be made very often like every 10ms, and objects values can be dynamically changed by incoming server info like player moves and all other objects distance changes.

My first intention was to use std::vector without alloc\free - reinit deleted objects, but reading internet made me thinking about std::map. The main reason I doubt about map is that values cannot be sorted.

Is there a performant way to sort and filter std::vector or std::map without copying elements? Something like c# linq:

var mons = world.Where(o=> o.isMonster()).OrderBy(o=> o.Distance);
foreach(var mon in mons){
//do smth
}

Answer 1

I recommend a different approach for two key reasons:

1. A single data structure is unlikely to satisfy your needs. Using an interlocked set of structures with one main index and multiple indices for specific query types will serve you better

2. Updating every entry when a single object moves is pretty wasteful. There is an entire set of spatial data structures that is designed to deal with looking up positions and finding objects in the vicinity. For my example, I'm using the R-Tree in Boost

Let's start with some basic type definitions. I assume 2D coordinates and use simple integers for object and type IDs. Adapt as necessary:

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>

#include <iterator>
// using std::back_inserter
#include <unordered_map>
#include <utility>
// using std::swap, std::pair
#include <vector>


namespace game {

using ObjectID = int;
using TypeID = int;

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
using Point = bg::model::d2::point_xy<float, bg::cs::cartesian>;
using PointEntry = std::pair<Point, ObjectID>;
using RTree = bgi::rtree<PointEntry, bgi::quadratic<16> >;

You want to query specific types, e.g. only monsters. So we need to keep track of objects per type and their positions. The way we set up the R-Tree, mapping a Point to an ObjectID, even allows us to iterate over all objects of a specific type by just using the RTree.

class TypeState
{
public:
    RTree positions;

    void add(ObjectID id, Point position)
    { positions.insert(std::make_pair(position, id)); }

    void erase(ObjectID id, Point position)
    { positions.remove(std::make_pair(position, id)); }

    void move(ObjectID id, Point from, Point to)
    {
        positions.remove(std::make_pair(from, id));
        positions.insert(std::make_pair(to, id));
    }
    RTree::const_iterator begin() const noexcept
    { return positions.begin(); }

    RTree::const_iterator end() const noexcept
    { return positions.end(); }
};

Next, we define the state per object. This needs to be linked to the type so that deleting the object will remove it from the RTree. Since I plan to keep all types in an unordered_map and these guarantee that pointers are not invalidated when elements are added or removed, we can simply use that.

using TypeMap = std::unordered_map<TypeID, TypeState>;
using TypePointer = TypeMap::pointer;

class ObjectState
{
    TypePointer type;
    ObjectID id;
    Point position;
public:
    ObjectState() noexcept
    : type(), id()
    {}
    ObjectState(TypePointer type, ObjectID id, Point position)
    : type(type),
      id(id),
      position(position)
    { type->second.add(id, position); }

    ObjectState(ObjectState&& o) noexcept
    : type(o.type), id(o.id), position(o.position)
    { o.type = nullptr; }

    ObjectState(const ObjectState&) = delete;
    ~ObjectState()
    {
        if(type)
            type->second.erase(id, position);
    }
    void swap(ObjectState& o) noexcept
    {
        using std::swap;
        swap(type, o.type);
        swap(id, o.id);
        swap(position, o.position);
    }
    ObjectState& operator=(ObjectState&& o) noexcept
    {
        ObjectState tmp = std::move(o);
        swap(tmp);
        return *this;
    }
    ObjectState& operator=(const ObjectState&) = delete;

    TypeID get_type() const noexcept
    { return type->first; }

    ObjectID get_id() const noexcept
    { return id; }

    Point get_position() const noexcept
    { return position; }
    /**
     * Changes position
     *
     * Do not call this directly! Call WorldState::move
     */
    void move(Point to)
    {
        type->second.move(id, position, to);
        position = to;
    }
};

Finally, we can put it all together. Since we may also want to query all objects regardless of type, we add a second R-tree for just that purpose.

This is also the place where we define our spatial queries. There are a lot of possibilities, such as K nearest neighbours, or all points within a range. See Predicates (boost::geometry::index::) There are also iterative queries that don't need temporary storage but I haven't used those for simplicity. Be careful about modifying data structures while queries are running.

class WorldState
{
    using ObjectMap = std::unordered_map<ObjectID, ObjectState>;

    TypeMap types;
    ObjectMap objects;
    RTree positions;
    /*
     * Warning: TypeMap must come before ObjectMap because ObjectState
     * borrows pointers to TypeMap entries. Therefore destructor order matters
     */
public:
    void add(TypeID type, ObjectID object, Point pos)
    {
        TypeMap::iterator typeentry = types.emplace(std::piecewise_construct,
                  std::forward_as_tuple(type),
                  std::forward_as_tuple()).first;
        objects.emplace(std::piecewise_construct,
              std::forward_as_tuple(object),
              std::forward_as_tuple(&(*typeentry), object, pos));
        positions.insert(std::make_pair(pos, object));
    }
    void move(ObjectID object, Point newpos)
    {
        ObjectState& objectstate = objects.at(object);
        positions.remove(std::make_pair(objectstate.get_position(), object));
        positions.insert(std::make_pair(newpos, object));
        objectstate.move(newpos);
    }
    void erase(ObjectID object)
    {
        ObjectMap::iterator found = objects.find(object);
        positions.remove(std::make_pair(found->second.get_position(), object));
        objects.erase(found);
    }
    /**
     * Calls functor for all objects
     *
     * Do not add or remove objects during the query!
     *
     * \param fun functor called with (ObjectID, const ObjectState&)
     */
    template<class Functor>
    void for_all_objects(Functor fun) const
    {
        for(ObjectMap::const_reference entry: objects)
            fun(entry.first, entry.second);
    }
    /**
     * Calls functor for all objects of given type
     *
     * \see for_all_objects
     */
    template<class Functor>
    void for_all_of_type(TypeID type, Functor fun) const
    {
        TypeMap::const_iterator foundtype = types.find(type);
        if(foundtype == types.cend())
            return;
        for(const PointEntry& entry: foundtype->second)
            fun(entry.second, objects.find(entry.second)->second);
    }
    /**
     * Calls functor for the K nearest objects around the given object
     *
     * The object passed to the functor can be manipulated, removed, or other
     * objects inserted during the functor call. But do not erase other
     * objects!
     *
     * \param fun functor called with (ObjectID, ObjectState&)
     */
    template<class Functor>
    void for_k_around_object(
            unsigned count, ObjectID object, Functor fun)
    {
        Point pos = objects.at(object).get_position();
        std::vector<PointEntry> result_n;
        positions.query(bgi::nearest(pos, count + 1),
                        std::back_inserter(result_n));
        for(const PointEntry& entry: result_n) {
            ObjectID found = entry.second;
            if(entry.second != object) // exclude itself
                fun(found, objects.find(found)->second);
        }
    }
    /**
     * K nearest objects of specific type around the given object
     *
     * \see for_k_around_object
     */
    template<class Functor>
    void for_k_of_type_around_object(
            unsigned count, TypeID type, ObjectID object, Functor fun)
    {
        TypeMap::const_iterator foundtype = types.find(type);
        if(foundtype == types.cend())
            return;
        const ObjectState& objectstate = objects.at(object);
        if(objectstate.get_type() == type)
            count += 1; // self will be returned by query
        Point pos = objectstate.get_position();
        std::vector<PointEntry> result_n;
        foundtype->second.positions.query(
              bgi::nearest(pos, count), std::back_inserter(result_n));
        for(const PointEntry& entry: result_n) {
            ObjectID found = entry.second;
            if(entry.second != object) // exclude itself
                fun(found, objects.find(found)->second);
        }
    }
};

} /* namespace game */