CODEWITHSUNDEEP
c++mapscollision-detectiontiles2d-games
Dainius Kreivys
Dainius Kreivys

Reputation: 535

Finding a right" (fast and accurate) way for finding with what to check the collision for 2d games. c++

I am creating 2d rpg game. For maps I use 32x32 tiles. Objects like player and monsters have different sprite-mask width and height and they move not in tiles, but by x and y. So I am trying to find a "right" (fast and accurate) way for finding with what to check the collision, between player and tiles, player and monsters, monsters and tiles, monster and players.

For Collision detection I use: rectangle to rectangle, circle to circle(distance), rectangle to circle, and circle to rectangle collision check.

So for example I have a map: 1600x1600 width and height. Divide it by 32 and I have 50x50 tile map.

I made an 2d array of bool:

bool tile_area[50][50];

So for every non-collision-free tile, it will hold 1, and for collision-free tile it will hold 0.So for example, if the player is on tile_area[1][1] and wants to move right it checks the collision in tile_area[2][1], if tile is collision-free then it moves. Same goes for monster, everything is perfect here.

But this type of collision detection is different between moving objects like player and monsters, monster and monster. If in 1 map I have like 200-300 moving objects, its not very good idea to check the collision of main moving object with the rest of all the other objects every pixel it moves.

So I thought of an idea, of dividing the map of areas for the objects also, so now I got a 2d array of struct of obj_area[x][y]. This struct holds a vector of object structs "vector obj_list;", because not just 1 object can be in that area. 

struct obj_area{
vector<obj> obj_list;
};

obj_area o_Area[50][50];

I believe I could just make an 2d array of vector of structs :D Don't know for sure ;D

So when the player or monster moves, for example to x 210 and y 300 so it will be added to obj_area[210/32=7][300/32=9] and if it would want to move right, it would check first the tile_area[8][9] and if free, then with all the objects in the vector obj_area[8][9]. So if it is free also, it reallocates to obj_area[8][9] from obj_area[7][9] <- in this point I don't know if it is a good idea for reallocation, I would need to delete it from the old vector and add it to a new one, and that would be needed in every step of movement.

I have another idea, but I don't know if it would be better or possible, If I had a map of structs, and pair of x,y as its key value, so theoretically every time object moves, and needs to reallocate, I would just need to change the key value of that maps pair.

I would be very grateful for any of your thoughts and maybe better ideas :)

Upvotes: 0

Views: 475

Answers (1)

Grzegorz Herman
Grzegorz Herman

Reputation: 1915

First a few remarks regarding your ideas:

  • do not put your objects (are these the structs you are talking about?) into your lookup structure; using pointers is going to save you a lot of time copying data
  • only use vectors if you know the number of elements in a single one is going to be small; removing an item requires iterating over the whole vector (has linear time complexity)

And now a suggestion:

If most of your objects are small, you could attach to each its current bounding box. Then if you keep two maps (one for x- and one for y-axis), mapping coordinates of the corners of the bounding boxes to their respective objects, you can:

  • update the maps in logarithmic time (small even for thousands of objects) whenever an object moves
  • check only for collisions with object that intersect with the one you are currently dealing with on one of the axis (pick the one on which the range has fewer elements, lower_bound and upper_bound are your friends here)

Upvotes: 2

Related Questions