Posts tagged “Micro-optimisation“

Efficient Bounding Rhombi

A bounding box generally refers to an axis-aligned rectangular region of space used as a first, coarse step of collision detection. Every object is given a bounding box which covers all space the object could possibly occupy. If the bounding boxes of two objects overlap, the simulation needs to do a more precise but expensive collision check; but if they do not overlap, they certainly do not collide and the pair can be skipped.

Since Hexeline uses an oblique coordinate system, the same approach results in bounding rhombi instead of boxes, though that distinction is not particularly interesting here. What is interesting is how bounding boxes/rhombi can be handled extremely efficiently with SIMD. I fully expect that this technique has been discovered by someone else previously, but it’s still worth discussing.

Hexagonal coordinate representations in Hexeline

One of the central design principles in my still extremely early space shooter Hexeline (read: has neither space nor shooting) is that spacecraft will be defined in terms of a hexagonal grid, rather than cells of varying shape, which simplifies things for both the software and the player while still allowing more interesting shapes than a square grid.

A useful property of regular grids is that they are directly addressable; i.e., you can put the elements of an array and immediately access an element just by knowing its coordinate. Ideally, it’s also efficient to go from continuous spatial coordinates to a grid coordinate. This is trivial in a square grid: depending on how you define your coordinates, you can usually just divide spatial coordinates by the cell size to get the coordinate of the cell a point falls within.

In effort to get a similar property for hexagonal grids, I’ve taken the unusual step of basing a Newtonian physics engine on non-cartesian coordinates. It turns out this is not as bad as it sounds, and quite a few useful properties fall out of it.

Note: This post is going to be comparatively math-heavy and assumes some familiarity with linear algebra.