Handling collision in a uniform grid

Question

So currently I'm trying to dev a 2D game where I have different objects that are of different sizes. For performance, I decided to use a uniform grid for the collision.

I understand that for each object, we store them in the corresponding cell of the grid to check for collision. But since our object is not a point but actually a rectangle, we need to store the objects in multiple cells on some occasions (like when object overlapped multiple cells).

The problem arises when I try to implement this data structure using a Linked List. For a uniform grid array that contains linked lists of objects, each object holds a pair of pointers to the previous and next objects that are within the same cell. This means that if I have Object A, B, C in Cell 1, I can't make Object B to be in multiple cells if it were to overlap, because Object B already point to object A and C in cell 1 and it can't no longer point to any other object in Cell 2.

A straightforward solution would just be to use an vector or array, but are there better solutions?

Answer 1

Use an element wrapper, something like this:

class Wrapper {
public:
  Object *obj;
  Wrapper *next, *prev;
}

and then store Wrapper in the grid instead of an Object.