Of Groups and Other Things

My goal is to make a grid-based cube world, not unlike Minecraft. However, I don't want it to appear outright as boxy as that, so I'm going to include other shapes, not just cubes. Here's how I can to decide on which shapes to use.

The first shape that came to mind, other than a cube, was a slope. Naturally this led to corner slopes as well, both inner and outer. I then decided I wanted slabs, blocks that are only a portion of the height of a full block. This led to the idea of scaled slopes as well. I decided to divide the shapes into four possible heights. Not content to favor the vertical direction, I decided to include all rotations and reflections of these shapes.

At this point, the number of shapes had already climbed into the thousands. It became evident that if I wouldn't be able to handle each shape by hand on a case by case basis. I needed to to use math!

So I started thinking of mathematical ways to organize the different shapes. The easiest thing to do was to categorize each block by which slices you'd have to make to carve it out of a cube. For the slopes, that meant cutting diagonally. For the slabs, cutting flat across the middle.

Because I wanted four levels to my shapes, I just had to figure out all the slices that only cut across fourths on each edge. That way, there would be no awkward shapes that wouldn't match up with any other shape.

This actually turned out to be quite challenging. In 2D, the idea is pretty simple. You just pick any two points on the outside and draw a line through them. It's doesn't work out so nicely in 3D. There are lots of ways you can pick three points that don't result in a valid cut.

I spent a long time on that, but it seemed that no matter which way I organized the shapes, there'd be a couple of gaps full of invalid cuts. After many hours of trying to make that work out, I went with a somewhat simpler approach. I start with a tetrahedron made by slicing through three of the cube's corners. Then, I take that and scale it on each axis. Then I take those shapes and extrude them along each axis. Then, I also include the inversions of all those shapes.

When all is said and done, I end up with 54,000 different combinations. This way of doing it also has some nice properties. I can arrange the whole thing in a 30x30x30x2 grid, which allows me to look things up easily. I can encode the position of a shape within this grid using 5 bits for each axis and a bit for inversion (encoding each axis separately allows me to discern qualities of a shape easily). This is exactly 16 bits, which allows me to use 2 bytes per block rather than more, and doesn't waste them. I can also tell whether two shapes cover the same cross section along an axis by checking if they're in the same line in that grid.

To sum up a long story, here is a picture taken from within that grid of possibilities.