@JoeJ My projectiles are spheres, but the graphics library I'm using allows easy testing for collision.

Yeah, let's take regular grid as example. There are some caveats, for example we do not want to insert one object into multiple grid cells, to avoid dynamic allocation if using containers like std::vector. This can be avoided easily if your objects have simliar size.

Usually you start with making a bounding rectangle (or box in 3D) for each object. The cell size of your grid should be larger or equal to the maximum width, height or length of your rectangles (or boxes). And ofc. the grid has to bound the whole level.

Then you bin your objects to grid cells by calculating the center of bounding box. Tho object goes into the cell where this center is located in.

There are two option of this binning process:

1. Linked list: Each cell has one pointer (or index) to the first object. This first object has another pointer to the next. The insertion is O(1) simply by making each new object to insert the first in this list. Only downside is that our objects are not spatially sorted in memory after that. To traverse all objects of a cell, we need to do pointer chasing which may become a performance problem later.
2. To improve this we can reorder the objects in memory while updating the grid. Easy method is to iterate all objects two times: During the first run we increase a counter per cell. After that we know how much memory each cell requires to store an array of all its objects. We do a prefix sum over all those counters of the grid to get final sorted indices of all objects to store them in one big global array, then we reorder the objects accordingly. (I don't think you need this, but worth to keep in mind)

Now we have all objects nicely binned to grid cells. But they are not guaranteed to be entirely inside their cells - only their centers are inside. The objects overlap with neighboring cells and we get a range of 2x2 (or 2x2x2 cells) adjacent cells we have to check. To make it easy at first, you can use a range of 3x3 cells (including all neighbors) at first and later optimize this down after it works.

A trivial collision check then looks like so, for example:

for each bullet 
{
	calculate line segment (x0, x1) from current position and thet from previous frame of the bullet.
	calculate bounding rectangle of x0 and x1
	calculate the range of cells this rectangle intersects // some line DDA would be faster if line segemts tend to be long in relation to grid resolution
	extend this range by one in each direction to make sure we do not miss overlapping objects
	for each cell in that range
	{
		iterate all objects linked to the cell and check for collision
	}
}

If your enemies have different sizes, you can use multiple grids, each having cells twice as large than the former. Similar to mip maps. That's a multi level grid then. Larger objects go into grids with larger cells.

If your world is too big to have such regular grids, the whole idea is quite easy to extend to ‘loose quadtree / octree’, where ‘loose’ means the property to insert objects only into one node but accepting overlaps.

If you don't want to rebuild such acceleration structures for all objects each frame, BVH becomes attractive because it allows refitting but keeping some tree structures static.

But a full quadtree rebuild can also be avoided if objects mostly move over short distances in comparision to cell size, which is mostly the case. If so, we can save a lot of processing for objects that remain in current cell or only move to a direct neighbour of it.

Kookies_N_Kareem said:
My projectiles are spheres, but the graphics library I'm using allows easy testing for collision.

Does not really make a difference, algorithms as above still work for that. Ofc. you get capsules instead line segments for their movement between frames, and bounding rectangle extends accordingly as well.

And ofc. things are easier if you just use std::vector per cell and insert objects into each cell they overlap. It's very slow in comparison, but you could optimize later.

JoeJ said:
calculate the range of cells this rectangle intersects // some line DDA would be faster if line segemts tend to be long in relation to grid resolution

Thanks, you're helping so much, I'm a little confused about this though. What are the cells? And what is DDA?

@JoeJ So like an array of lists containing all objects in each box, and for collision, I would only check other entities in the same box?

Kookies_N_Kareem said:
What are the cells? And what is DDA?

Cells are simply the rectangles of the grid. (Not to be confused with bounding rectangles of dynamic objects, thus calling them cells is better.)

Kookies_N_Kareem said:
So like an array of lists containing all objects in each box, and for collision, I would only check other entities in the same box?

Basically yes. But because dynamic objects span multiple adjacent cells, you need to include neighboring cells as well.

Easier to explain using a picture, where example is to find all collisions between all objects:

3 objects, and their bounding rectangles all span a range of 2x2 cells, which is the mostly case.

For the circle we know its bounds center is cell (1,1) To find the entire spanned range of cells we can floor the minimum bounding rectangle coordinate and ceil the maximum coord. Then we get the (yellow) range (1,1) - (2,2), including (1,2) and (2,1). located in cell

Then iterate all objects of all cells in that range to collide them with the circle.

Notice, this way we will not iterate the third object located in cell (0.3) with green drawn range, although its bounds intersect our yellow range. But we do not miss potential collisions - the other object will find them later.

Final problem is to prevent processing the same pairs of objects twice. You can skip over pairs if index (or memory address, ID, etc.) of object A is larger than object B. But only if their range overlap ensures A will find B, but b will also find A. (Maybe there is a better way to achieve this.)