Collision and movement in RTS games

Collision detection is a fundamentally hard problem. Spheres are easy enough (y² = x² + r², iirc) but generally objects are knobbly.
A related issue is movement and pathfinding. Each step along the path involves collision detection and either halt or reroute.

Probably the oldest solution is to use a square board, a la chess. That isn't very good though, because a diagonal move is longer than an orthogonal. Pentagons don't tesselate well, so hexagons are the next step up. Hexagons offer 6-way movement with a pure grid, the famous isometric grid. This is good enough for most games and people have made east+west movement possible.

Octogons don't tesselate perfectly; they need squares along the diagonals. You get all 8 compass points though and the squares give you a little flexibility. You can choose to put units in them or not, you can choose whether a given item collides on squares as well as octogons (to make a slightly bigger tank). You could allow small units, like single Marines, to occupy a square.

Going back to hexagons, seven hexagons make a superhexagon (my name). They have supersides composed of 3 hexagon edges - happily, they have 6 of these. So by making each tank take up a superhexagon, you gain some freedom for irregular shaped units. That gives me a cool idea for super-units which are assembled from smaller units - like in cheesy anime.

By adding surrounding blocks, you can allow pixel-precise unit placement. A single square sized unit cannot overlap more than a four-square, wherever it's centred within that four-square. A foursquare sized unit needs a ninesquare. A hexagon needs a superhexagon. By doing collision detection on the containing area first, using coarse blocks, you save a lot of CPU compared to trying to make pixel-perfect collision detection between everything at once.

There is a tradeoff involved in how many blocks you use. Too many blocks and the memory requirement goes through the roof. The containing-block lists also get large and less useful. Too few blocks, and you get large blank spaces between units.

Incidentally, the blank-space effect can be substantially mitigated by combining buildings. This is often done for walls in RTS' but not bunkers. I've never seen production buildings built like this - maybe in Rollercoaster Tycoon? - it might be interesting to introduce vertical scaling to RTS'. (traditionally horizontal scaling is used, ie more factories not bigger ones)