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.
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.
My first few years of university, I spent a lot of time working on a 2D space
shooter called Abendstern. It ultimately didn’t end up going much of
anywhere, and not for lack of it functioning well as a game. In the hopes of
being able to try this again, I look back on why Abendstern ultimately failed.