Jump to content
  • Advertisement
Sign in to follow this  
BaneTrapper

Spatial partition 2d with 5 layers

This topic is 1503 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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;

Share this post


Link to post
Share on other sites
Advertisement

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);
 

Share this post


Link to post
Share on other sites

 

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.

Share this post


Link to post
Share on other sites

 

 

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.

Share this post


Link to post
Share on other sites

 

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 misunderstood this line, what you meant at least.
I thought you want me to hold pointer to the object in "Spatial partition", when you actually meant, to hold the object as a pointer in first place.

 

I will post what solution i came up with. Thank you on suggestion.

 

EDIT:: dropping the idea, sorry for no code tho :)

Edited by BaneTrapper

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!