Hello.
I want to implement Spatial partition like http://gameprogrammingpatterns.com/spatial-partition.html

And all is good, but i have a question, i cannot decide on design cause i feel its going to be slow, so i need help.

I have objects that will represent anything in my game

class Object
{
public:
    Object();
    Object(sf::Vector2f & Position, sf::Vector2f & Size, glob::Layer Layer, CollisionBase & CollSett, EntityBase & EntitySetting, bool IsInUse = false);
    sf::Vector2f pos;
    sf::Vector2f size;
    glob::Layer layer;

    CollisionBase collSett;
    EntityBase entitySetting;

    bool isInUse;
    int myVecID;//For finding this object, comparing not actual ID
};

Each object has EntityBase and CollisionBase, entityBase is used for drawing, while collisionBase is used for collision and the class looks like this

class CollisionBase
{
public:
    CollisionBase(bool IsColideWith = false, std::vector<Collision> & ListCollision = std::vector<Collision>{});

    bool isColideWith;
    std::vector<Collision> listCollision;
};

class Collision
{
public:
    Collision(sf::Vector2f & PosOffset, sf::Vector2f & Size);
    sf::Vector2f posOffset;
    sf::Vector2f size;
};

So implementing spatial partition would mean i have references to objects in vectors that are small areas, or do i put the main data of objects in those small containers?

If i want to hold references i have a issue, each object is in vector that often resizes, meaning the reference will be invalid after resizing occurs

My question would be, how do i store references of the objects CollisionBase object, because that is all i need in the Spatial partition.

The objects are stored in this way

std::vector<Object> listObject;

If you're going to use a known # of cells in the grid, then I would have an array of vectors, the vectors holding pointers to objects within that cell. For example, if you have a world that is 1000x1000 tiles, you might want to break it up into 16 cells (each cell covering 250x250 tiles). Every time you move an object, you could call SpatialUpdate(), which would handle adding and removing your object from the SpatialGrid lists. Realize, an object can live in multiple cells at once, so it could be referenced from multiple vectors. The SpatialUpdate() could return the list of grid cells the object is in, and you use that value when you check collisions. Something like this

(pseudo-code)

 
// the array of vectors holding object's locations
std::vector<TRectangle> SpatialGrid[16];
 
.
.
.
// handle moving player
Player.Update();
 
// handles placing object in grid, returns list of cells the object lives in
std::vector<int> gridList = SpatialUpdate(Player.GetSizeAndLoc());
 
// Check if this object has intersected anything within the objects in the gridList cells it occupies
CheckCollision(Player.SizeAndLoc(), gridList);
 

If you're going to use a known # of cells in the grid, then I would have an array of vectors, the vectors holding pointers to objects within that cell.

I stressed out i cannot hold pointers, cause when adding elements at some point the vector reaches maximum capacity and needs to resize, possible reallocation.

Each pointer would then turn invalid in such case, additionally I manually will resize vector down if its bellow <33% of max capacity.

I thought about holding the references in linked list, since when objects move they will eventually go out of the partial vector, assuming amount of moving objects i have, vector would be worse pick in my case.

But the problem is still, i cannot hold pointers or references to objects cause reason above.

If you're going to use a known # of cells in the grid, then I would have an array of vectors, the vectors holding pointers to objects within that cell.

I stressed out i cannot hold pointers, cause when adding elements at some point the vector reaches maximum capacity and needs to resize, possible reallocation.

Each pointer would then turn invalid in such case, additionally I manually will resize vector down if its bellow <33% of max capacity.

I thought about holding the references in linked list, since when objects move they will eventually go out of the partial vector, assuming amount of moving objects i have, vector would be worse pick in my case.

But the problem is still, i cannot hold pointers or references to objects cause reason above.

Is it too difficult to store the Objects as a vector of smart pointers? If you're doing any kind of polymorphism, you'll need those objects to be pointers to use the virtually defined functions underneath anyway.

That's my suggestion if you want to reference objects in another list beside your main object list. I don't know another easier way.