Does the collision detection algorithm in a RTS game look different when you collide squares of different sizes?

Sorry that’s an incomplete question. What I mean is, does the CD algorithm in a RTS look different when you have rectangles of different sizes if you compare it with the situation when all rectangles have the same size and shape?

Calin said:
What I mean is, does the CD algorithm in a RTS look different when you have rectangles of different sizes if you compare it with the situation when all rectangles have the same size and shape?

Depends. I did some code example about it here: https://www.gamedev.net/forums/topic/713512-what-kind-of-coding-standard-do-you-prefer/5453677/?page=6​

The example does circles of different sizes, which would be easy to replace with rectangles. But of all shown algorithms, only BVH is ready to handle large difference in size. (The sorting method as well, but it was too slow to be interesting at least for larger numbers.)

The other examples, which simpler and faster, are based on a regular grid, similar to your path finding which also uses such grid. So that's likely what you want.

But this raises the question: What do we do if some objects are larger than grid cells? Do we put them into many cells?
That's an option, and the grid of std::vectors would support this with little changes. However, if we also want to solve the problem of dynamic allocations caused from using std::vectors, we would notice that's quite some work and performance is still suboptimal.

So what i recommend is using the fastest method from the examples, which is to use a single pointer per grid cell to just one object. The objects also have a next pointer which leads to the next object in the same cell.
This approach has constant memory requirements, no allocations are ever needed. Building the grid also has ideal performance.
But notice that all grid approaches set the grid cell size from the largest object we can have, to guarantee any object can be bound from 2x2 cells.

If we have just one object which is 10 times larger than all other objects, this causes large grid cells, thus we get many objects per cell, thus we get worse performance because we do much more collision checks.

That's the problem with different sizes but using a simple grid as acceleration structure.
To solve it, we can use multiple grids, a so called ‘multi level grid’. That's like mip maps of a texture. Each parent level has cells twice as large as the cells from the child level:

The red grid is the parent level of the black grid. (I've drawn them with a little offset, but they should align of course.)
Any object has to check up to 4 cells for collisions, but never more. I've colored those cells red and green per object.

Now we have two options of finding collisions across levels:

1. We have only few large objects:
   The red object, which is in a higher level, also has to check the black child cells it covers.
   But the green object does not need to check parenting red cells.
2. We have only few small objects:
   The green object also has to check the parent levels.
   But the red object does not need to check child levels.

Don't forget about the other options, which simply is to put large objects into multiple cells of just one level, or making the cells large enough for the largest objects.

The proper decision depends on your object count, expected dense spots, how much their size differs, and distribution of different sizes.
Ideally you can just do what i did for the simple code example, because complexity is very low.

Notice we talk about broad phase collision detection here, where we represent any object with an axis aligned bounding rectangle.
This gives us pairs of potentially colliding objects.
If we have something like tanks at an angle, you can make such axis aligned box for each tank and unit, do broad phase collision detection to find pairs, and then for each pair do a detailed test considering the actual orientation and shape of the objects ('narrow phase collision detection').

EDIT:

But of all shown algorithms, only BVH is ready to handle large difference in size.

That's not really correct. An ideal implementation of BVH would allow to store large objects in internal nodes, so at a higher level. So some changes would be needed as well for best performance.

Hi JoeJ. Thanks for your post. To be honest it took me a couple minutes to realize that what you are talking about has to be placed in the context of CD optimization tree. At this point I’m not aiming that far, I don’t have tons of units. Ten to twelve units is my goal for now so a quad tree would be an overkill.

Although the things you talk about in your post don’t represent an immediate need in my case I still find them useful, it will come handy a little bit further down the road

Calin said:
Ten to twelve units

Ok, then you can just test any vs. each other (brute force). Even a regular grid would be overkill for such low numbers.
It also does not matter if there is a difference in size. For an example rectangle collision check, you can look at AABox::IntersectsBox (const AABox &box) in my code. Pretty simple stuff. Oriented boxes is much harder.

Calin said:
a quad tree would be an overkill.

In 2D there almost never is a need for trees like quadtree or BVH. (Only if your world is really huge and well populated.)

But a regular grid is so easy to use, it's likely you need it sometime in the future. If units become more than something like 100.
If you have e.g. 300 small units, and only 10 big ships, you could put only the small units into the grid. Each ship can find nearby units using the grid, and for ship vs. ship you could use brute force again. Simple and fast.

This often keeps working for 3D too, if objects are mostly distributed over a horizontal plane or height map. Objects won't stack up above each other much, so the 2D grid still works good enough.

If units become more than something like 100

I’ll never reach that number I think. I could throw a large number of units on the map but that’s that, I have a large amount of units that do nothing or at best bump against each other while moving without purpose on the map. I want to get to a more complex behavior and I don’t need too many units for that.