PlanetKit is a project aimed at creating a toolkit for making interactive virtual worlds. I'm writing it in the Rust programming language, which I'm finding delightful to work with, and a great fit for the task.
This week I'm going to figure out how to step entities around between cells in my voxel world.
Why is this a problem?
Maybe it is actually trivial, and I'm just missing some key simplifying insight. But let's pretend for now that I'm right, and it is legitimately a nontrivial problem.
Recall that the coordinate system in my world consists of 5 "root quads" wrapped around a sphere. Within each quad I use an axial coordinate system. (Scroll down a bit on this great Red Blob Games article for an explanation.)
I've highlighted all the hexagons in one of the root quads below. (Yes, those filled circles are hexagons. Try to suspend disbelief.)
● ◌ ◌ ◌ ◌ ● ● / \ / \ / \ / \ ● ● ● / \ / \ / \ / \ ● ● ● ● ◌ ◌ ◌ ◌ ● ● ● ● \ \ \ \ ● ● ● ● \ \ \ \ ● ● ● ● ◌ ◌ ◌ ◌ ● ● ● \ / \ / \ / \ / ● ● \ / \ / \ / \ / ● ◌ ◌ ◌ ◌
If we consider a single root quad in isolation, then all we need is a tiny bit of modular arithmetic for turning to face each of a hexagonal cell's six neighbors, and a similarly tiny lookup table for the (x, y) offsets of each neighbor.
If we number hexagonal cell edges from 0 through 5, then the (x, y) offsets to reach each neighbouring hexagon are:
(-1, 0) \ 3 / \ / (0, -1) ●-------● (-1, +1) 4 / \ 2 / \ / \ -----● ◌ ●----- \ / \ / 5 \ / 1 (+1, -1) ●-------● (0, +1) / \ / 0 \ y (+1, 0) ↘ x ↓
That'd be about 15 lines of code all told. Simple.
Unfortunately we have a few complications to address on account of our world being a globe rather than a flat earth:
- The world is not one giant coordinate space. There are five separate coordinate spaces that connect along various edges.
- Orientation r is often not the same in one quad as in its neighbor. Look at the net above and imagine how it folds into a sphere. Quads to the left and right at the north and south poles have their coordinate systems rotated with respect to each other. This is even more extreme when crossing the north or south poles.
- Our world isn't just hexagons. There are also 12 pentagons, and so moving through a pentagon isn't as simple as entering through one side, and then leaving through the opposite side — in a pentagon, it's a vertex opposite each side! And even if you arbitrarily pick one of the sides adjacent to that vertex, what is its index? Which of the six hexagon edges is the pentagon "missing"? 0? 5? One of the edges between those?
So I've created quite the mess for myself.
What do we need?
Before diving into implementing a solution, I need to nail down a list of minimal criteria that any solution must meet. Here's what I came up with:
- Entities can face towards the center of any immediately adjacent cell. For hexagonal cells, this means that they can face any of the six edges of the current cell. For each of the 12 pentagonal cells, it's five edges.
- Any movement or turning must result in facing a valid direction for further movement — i.e. toward an immediately neighboring cell, not toward a vertex between two neighbors.
- Moving k steps forward and then k steps backwards will return an entity to its original cell, with its original orientation.
- Moving across boundaries between root quads must translate the entity's original orientation into something equivalent in the adjacent quad. Crossing at a pentagon must at least do something consistent with these other criteria.
And my bonus criterion, which I think can be achieved easily enough once the others are met:
- If last time you moved into a pentagon you were reoriented to the side slightly left of where you were originally facing, then the next time you will be reoriented slightly right, and vice versa. This isn't really important, but feels nice to me for balance.
Basic orientation
From above, "entities can face towards the center of any immediately adjacent cell. For hexagonal cells, this means that they can face any of the six edges of the current cell."
Well, that seems straightforward enough. We'll just number the orientations from 0 through 5 like in the diagram above.
However, "for each of the 12 pentagonal cells, it's five edges".
If I stick with numbering orientations from 0 through 5 then what happens when you move into, for example, the pentagon at the north pole?
↘ ● ↘ .' `. ↘' `. .' ↘ `. ●' ● `●-------◌ \ / \ \ / \ \ / \ ●-------● ◌ ◌ / \ / / \ / / \ / ◌ ◌ ◌-------◌ \ / \ / \ / ◌-------◌
Until we arbitrarily decide whether to nudge your orientation a little to the left or a little to the right, you're clearly facing a vertex, not an edge. If we can't represent that with the direction type then we'll be forced to handle that kind of correction to a direction you can move in before we'd naturally want to.
So what if we approach this differently? Instead of just numbering sides, we could also include the vertices in our numbering scheme. Then we can at least represent the idea that at least in some intermediate states we might be pointing at a vertex, even though we'll clean it up before the user or even most higher-level code sees it.
Our numbering on ordinary (hexagonal) cells now looks like this:
7 5 6 \ / ●-------● 8 / \ 4 / \ / \ 9 --● ◌ ●-- 3 \ / \ / 10 \ / 2 ●-------● / \ 0 11 1 x ↓
Pentagons
Jumping back to pentagons for a minute, what happens when you...
- Walk forward across the north pole?
- Do the same thing backwards?
- Sit on a pentagon and rotate?
- Walk into a pentagon from a direction that doesn't require leaving the current root?
- Leave a root through one of the pentagons near a tropic?
- Northern hemisphere?
- Southern hemisphere?
- Moving east?
- Moving west?
- In each orientation you could cross from?
I'd love to be able to say something like, oh, you just reorient based on the difference in orientation between the two root quads at the point you crossed. And that actually works pretty well until pentagons come into the mix. But then I couldn't for the life of me figure out any neat pattern to how I'd need to change the orientation in all the possible combinations of the ways above that you can come across pentagons.
I was about to end up with a whole lot of logic to handle arbitrary special cases.
Embrace the arbitrary
As soon as I accepted that the way the roots quads snuggle up next to each other when wrapped around a sphere is far from neat or convenient to my needs here, it opened me up to thinking about solutions that embrace those arbitrary relationships and find generalisation elsewhere instead.
Each of the pentagons in a root quad sits at one vertex of a triangle covering part of that quad. And every point in the root quad can be covered by a triangle associated with the closest pentagon to that point, like so:
● / \ / 0 \ / \ / \ / 1 2 \ ●-----------● \ 5 4 / \ \ / 6 \ \ / \ \ 3 / \ \ / 7 8 \ ●-----------● \ 11 10 / \ / \ / \ 9 / \ / ●
From here, if we completely ignore the apparent natural relationship between some of the triangles there, we need to store a constant array of the following to fully define each triangle and its relationship to all the others around it:
- Its defining pentagon's position in cell-space
- The direction of its local x-axis; i.e. the first edge leading away from that pentagon travelling anti-clockwise
- A descriptor for each neighboring triangle:
- The index of the triangle in same array
- Which root the triangle is in: same, next to the west, or next to the east
Wait, but why?
We've now got enough information to do something really neat. Instead of trying to write special logic for all the special cases, we can instead:
- Transform whatever point and orientation we're dealing with into triangle-local coordinates for whatever triangle is based on the closest pentagonal cell. Recall that we store an x-axis for each triangle, so we can use that to orient the coordinate space.
- Perform any movement or rotation pretending that the position is in root 0 at the north pole.
- Transform back to global space.
This significantly simplifies matters. If you look over a couple of the diagrams above, you'll see that the north and south poles are special, because if you move either east, west, or straight through the pole, you'll end up in the same triangle, just in a different root. This keeps each movement and rotation case pretty simple.
And it also means we're down to a small handful of movement cases:
- Moving around within the same quad
- Moving east around the north pole
- Moving west around the north pole
- Moving through the north pole
The final case is the blessedly simple "stepping backward anywhere", which can be implemented as "turn around, step forwards, and then turn around again".
When moving through a pentagon, I'm tracking per cell dweller which direction, left or right, did we nudge you in last time? And we do the opposite next time.
And similarly for turning, the only cases are:
- Turning without ending up pointing outside the current root
- Ending up pointing into the next root to the east
- Ending up pointing into the next root to the west
And the neat bit about doing all the actual stepping or turning at a virtual north pole is that when dealing with pentagons you'll always be facing direction 0, 1, or 2 in whatever new quad you end up in; there's no need to figure out what side is "missing" on the other side of the pentagon.
And "just" like that, we have movement — and my stubborn determination to do this on a globe only added about a factor of about 100 over the equivalent code for a flat world! (Neep.)
Testing
This is getting a little long, but a final word on testing before we part: fuzz testing is great for this sort of thing.
I knew I was going to need to break this down into a bunch of small functions I could easily unit-test if I was going to retain my sanity. So of course I did that, and it certainly helped.
But my confidence that I haven't typoed part of one of the triangle definitions or something comes from a different pair of tests that take long random walks around a tiny globe. One test then turns around and retraces all steps by walking forwards, and then asserts that we're back where we started. The other retraces all steps by walking backwards. And yes, these tests have already paid for themselves by finding the one error I did originally have in the triangle definitions!
What's next?
I now have everything I need for a character (currently in the form of red, green, and blue axes) to run around the world pointing at things. The next step is to let the character manipulate its environment.
So the next functionality I build will be to let you pick up a block, move around carrying it, and finally put it back down. If that sounds exciting to you, then tune in next week(-ish) for more hexagonal fun!
As always, the source for everything I'm talking about here is up in the planetkit repository on GitHub.