This post details the Copernicus ship collision algorithm, optimized for level travel. It's a bit long, but that's mostly description. The implementation should be relatively simple.
------------------------------
Separating Axis Theorem (SAT)
------------------------------
There is a good tutorial for how SAT works here. I would recommend looking at it.
http://www.metanetsoftware.com/technique/tutorialA.html
Essentially, SAT states that if you have two convex objects, they are overlapping if and only if their projections along every possible axis also overlap. If even one projection fails to overlap, the two object do not touch. Fortunately, we will only have to test a few of those axes. For a pair of oriented 3D bounding boxes, there are a total of 15 axes to test. However, since your ships only have one axis of rotation, we can use the 2D version of this algorithm, in which there are just four axes to test.
You can think of a projection as a shadow, cast onto a 1 dimensional line. The easiest way to produce a projection for a square is to use a dot product on each of its four points. In that case, one of the input vectors is the point in 2D space, and the other is a unit vector representing the axis of projection. By taking the max and min of those 4 projections, you can determine the position and size of that square's shadow. For collisions, all we care about is whether the projections overlap.
Figure 1: All four projection axes.
Here, only two of the projections overlap, indicating that the squares do not touch. Consider these projections the distance between the two objects from various perspectives. With a bit of foreknowledge of the problem, it's possible to decide ahead of time which of these perspectives are actually useful. We'll be taking advantage of that.
------------------
Setup
------------------
For this collision method, we will make the generalization that every collidable block has a standard cube hitbox. Since this method only applies to ship-terrain and ship-ship collision, this small loss of accuracy should go mostly unnoticed.
First step is creating an occupancy grid. This will be a 3 dimensional array sized to the size of the ship. Each element contains 16 bits. One bit is the "occupied" flag, which is 1 if that particular element in the array represents a collidable block. Another 8 bits are reserved to reflect the "occupied" bit of the 8 surrounding blocks in the Y plane. This is not necessary, but decreases the number of array lookups, which are kind of slow for 3D arrays. There could also be "9 above" and "9 below" flags, to indicate whether the set of 9 blocks on the Y plane above or below the current block have any occupied spaces. The occupancy grid should be updated whenever a ship block is added or removed.
Next is the coordinate system. For collision to work, we need to move one coordinate set into the other. In our case, we will be moving the world-coordinates into ship-coordinates. The reason for this is that it is much easier to produce a bounding box around a ship. Regardless of the actual position of the ship in the false world, the collision coordinate system will start with (0,0,0) in one of the bottom corners of the ship, with Y pointing up. This will simplify occupancy grid lookups. Because we'll be moving a lot of points from world-space into ship-space, we should use a 3x3 transformation matrix, with all rotations and translations for the XZ compiled into a single step. If need to know how to set that up, I can elaborate in a later post. Naturally, there should also be a Y modifier as well, but since ships stay level we can keep it separate to reduce the calculation cost. The transformation matrix should be updated once per tick.
Third is the bounding box around the ship. This box is axis-aligned to world-space and completely contains the ship entity. The fastest way to calculate this is to rotate a ship-space bounding box into world-space and use the corners as the outer edges of the world-aligned bounding box. If a terrain block is contained inside this box, then it is queued for collision testing. If there are no blocks inside the box (most of the time), then you can skip all testing that tick. Additionally, since Minecraft's AABB-based block collection is relatively slow, I would suggest testing your bounding box against Chunk.heightmap[] first. As zeppelins reside predominately in the air, this is an easy way to cull collisions quickly and effectively. This bounding box also should be updated once per tick.
Fourth, and most important, is the collision lookup table. This part is more elaborate, so I'll be putting it in its own section.
-----------------------------
Collision Lookup Table (CLT)
-----------------------------
The CLT is the heart of collision optimization. It takes everything we can assume about the scenario and uses it to reduce calculations as much as physically possible. Physically, it is a 3x3 grid representing a local set of blocks in ship-space. The 8 outer squares are potential locations for ship blocks, while the center square houses the foreign terrain block somewhere inside (the grid is centered over the terrain block, so the center of the terrain block must reside somewhere in the middle square. That will be important later on). For the sake of simplicity, the coordinates of the center block will be from (0,0) to (1,1), with the entire table ranging from (-1,-1) to (2,2).
Figure 2: Foreign block within the CLT grid.
Orientation of the foreign block is known, but the exact position is not. However, the center of the square will reside within the middle space on the grid.
The thing about SAT is that relative projections are globally invariant, meaning that relative to one another, all the blocks in the 3x3 grid are going to have the same projection results regardless of their position in the ship. Same for all foreign blocks sharing the same alignment. The only thing that will vary from block to block is exact location of the foreign block in ship-space.
To set up this lookup table, first we calculate the projections of the 8 surrounding squares. Since the grid is already aligned to the Shipe X and Z axes, those to projections are simply the X and Z coordinates. The World axes will need to be done with dot products, though. Second, find the offsets of the foreign block projections. This is simply the distance from the center point outward along the projection axis. Next, add the offsets to the projections of the other 8 squares. By expanding the footprint of the ship squares, you essentially shrink the footprint of the foreign square down to a single point. Because of this, we only have to project a single point per foreign block, rather than four. Additionally the Ship-axis projections are already done, so there are at most two dot products required per block test.
Figure 3: Region of collision 1.
This is for the upper-right square in the grid. If the center of the foreign square is inside the double shaded area, then the two blocks have collided. Note, only two of the four axis are shown. This is because those two are the only relevant axes in this scenario. The other world-axis will always overlap with the corner piece, and the other ship-axis will necessarily overlap before the diagonal axis, making it redundant. It turns out there are always two important axes per block (more on that in a moment).
Figure 4: Region of collision 2.
This is for the middle-right square in the grid. Note the red axis is tilting in the opposite direction from before
Each block has two relevant axes to test: one ship axis and one world axis. Which ones depends on the angle of the foreign block, as shown in figure 5.
Figure 5: Primary axis rules.
The angle of the the foreign block is easily determined from the input theta (make sure it is oriented correctly, though. Notch's theta is backwards). If theta is (-45, 0), use the left rule set. If theta is (0, 45) use the right rule set. If theta is out of range, adjust it by 90 degree increments until it is in range. This will also determine which axis is which. If theta = 0, then use only ship-space X and Z. If theta = 45, it doesn't matter which is used.
Once you have determined which rule set you are using, store the two augmented thresholds for each block in the CLT, and then you are done with setup.
---------------------
Execution
---------------------
If there are terrain blocks flagged from the world-aligned bounding box check, first build the CLT and then start passing block coordinates to the collision check.
First determine where the block is in ship-space, or more accurately, occupancy grid space. It should just take a vector-matrix multiplication then modify the Y. If the Y is between two integers, then you have to check two levels of the occupancy grid (this is what the "9 above/below" flags are for). First, if either layer's "occupied" flag is set, you can immediately return "collision". If "occupied" is cleared, all 8 of the "surrounding blocks" bits are cleared, and the "9 above/below" bit is cleared, you can immediately return "no collision" for that block. Those two occurrences will be the most common by far, so it makes sense to give them a short-cut. If either layer has some bits set in the "surrounding blocks" field, then you consult the CLT.
First you determine where the center of the terrain block is in the grid. Since it is between (0,0) and (1,1) you can just pull off the decimal part of the coordinates. Once that is done, start running one of the three predetermined rule sets mentioned in figure 5. You can mask the "surrounding blocks" bitfield to determine whether or not you need to calculate both projections. Most of the time you won't. Either way, once you project the center point into the relevant axes, compare them against the thresholds stored in the CLT. For optimization, it's probably best to hard-code each of these checks, since their outcomes are so predictable.
If both thresholds are crossed on any block, you can immediately return "collision".
--------------------------
Special Cases
--------------------------
Since we are going for optimization, we should handle special cases uniquely.
Y is aligned to world-grid: In this case, only check one layer of ship blocks instead of two.
Theta = 0: Only the X and Z of the ship space are used. All thresholds are set to 0.5 and the four cardinal blocks only need to test one axis each, rather than two.
X or Z is aligned: Probably not worth the extra effort, as it will go along with Theta = 0.
Note: there should be a small amount of slack to the threshold, like 0.0005, to allow for precision errors. Otherwise ships are going to end up getting stuck while aligned to the world grid.
Ship-Ship collision: Acts much like world-ship collision, except it takes some extra setting up. It would also be beneficial to have oriented bounding boxes on both ships, and first do collision on those, or better yet first the world-aligned bounding boxes, and then the oriented ones.
.
[/spoiler]
