These weeks in PlanetKit #6: the joy of motion

Dec 30, 2016
11 minute read

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)              ↘


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:

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:

And my bonus criterion, which I think can be achieved easily enough once the others are met:

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
          \         /
      8   /         \   4
         /           \
        /             \
  9  --●       ◌       ●--  3
        \             /
         \           /
     10   \         /   2
          /         \
       11             1


Jumping back to pentagons for a minute, what happens when you...

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:

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:

  1. 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.
  2. Perform any movement or rotation pretending that the position is in root 0 at the north pole.
  3. 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:

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:

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.)


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.