In my 2d engine, this is how I chose to solve the problem:
First the interface for a generic spatial container ..
template <typename T>
class SpatialContainer {
public:
virtual bool insert(T item, const Range& boundingBox) = 0;
virtual bool remove(T item, const Range& boundingBox) = 0;
virtual void removeAll() = 0;
virtual int getNumEntries() const = 0;
virtual void getEntries(const Range& region, std::vector<T>& entries) const = 0;
virtual const Range& getBoundary() const = 0;
virtual ~SpatialContainer() {}
};
, where the Range class is just a rectangle, basically.
I made a Quadtree implementation, but you may prefer to use a simple grid instead.
template <typename T>
class Quadtree : public SpatialContainer<T> {
// (implements the interface defined by SpatialContainer)
};
Then there's the WorldSpace class, which listens for 'entity moved' events and updates its spatial container accordingly. It only manages entities that have first been registered via a call to trackEntity().
class WorldSpace {
public:
inline void init(std::unique_ptr<SpatialContainer<pEntity_t> > container);
inline void trackEntity(pEntity_t entity);
inline void untrackEntity(pEntity_t entity);
inline void untrackAll();
inline void insertEntity(pEntity_t entity);
inline void insertAndTrackEntity(pEntity_t entity);
inline void removeEntity(pEntity_t entity);
inline void removeAndUntrackEntity(pEntity_t entity);
inline void removeAll();
inline void removeAndUntrackAll();
inline void getEntities(const Range& region, std::vector<pEntity_t>& entities) const;
// ...
private:
static std::unique_ptr<SpatialContainer<pEntity_t> > m_container;
static std::set<pEntity_t> m_tracking;
// ...
};
Drawing all on-screen entities is then very simple:
vector<pEntity_t> visibleEnts;
m_worldSpace.getEntities(m_viewArea, visibleEnts);
for (uint_t i = 0; i < visibleEnts.size(); ++i)
visibleEnts[i]->draw();
, where m_viewArea is the rectangle defining the view area.
If you're curious how I implemented the event system, I've written about it here.
Hope this helps