Traversal in Four Bits

Isles of the Cloud Realm is a grid-locked isometric game. It's drawn in 2D, but the world underneath is 3D: every tile has an x, y, and z coordinate. Tiles stack into layers, and sloped tiles connect one layer to the next, so walking up a slope takes you up a layer.

The third dimension makes traversal more complicated. If the world were one flat layer, I could decide whether you can step onto a tile by checking what it is: grass you can walk on, water you can't. With layers, a step depends on the geometry of both tiles, the layers they sit on, and which way you're walking. You can walk onto a slope from the flat ground at its top or bottom, but not from the flat ground beside it. A flat tile one layer above yours is a ledge you can't climb unless a slope leads up to it.

That complexity is worth it. With height, the world has mountains to climb and winding paths to work out. Finding the way up this one takes some exploring:

The game checks whether a step is allowed every time something takes one. Client-Server Architecture walks through the checks the server runs on a move request. One of them asks whether the edge geometry between the two tiles allows passage. That check runs far more often than players take steps, so it has to be cheap.

A player's step only needs one check, so it barely matters how fast that check is.

Pathfinding is where the checks pile up. Thousands of entities on the server will be walking around at once, and when one of them heads off on its own, such as an enemy patrolling or chasing you, the server runs A* (opens in new tab) to find the shortest route. Range checks use it too: when you try to chop a tree or open a chest, A* measures how far you'd actually have to walk to reach it, and the action is allowed only if that walk is within range.

A* works outward from the start. It repeatedly picks the most promising tile it hasn't explored yet, and runs a traversal check on each of that tile's four neighbors.

Every tile A* explores costs four checks. A long walk across a map can mean exploring a hundred or so tiles, which is about 400 checks. When the destination can't be reached, A* has to keep going until it has explored every tile it can reach, so on a map with about 1,300 walkable tiles, that's over 5,000 checks, all to return "no path."

These are all nine surface shapes in the game: one flat tile, four cardinal slopes, and four ordinal slopes. A slope is named for the direction it descends, so the cardinal slopes descend north, east, south, or west, and the ordinal slopes descend toward a diagonal, like south-west.

Every one of them is the same flat square with some of its corners dropped down a layer. A cardinal slope drops the two corners on the side it descends toward, so the east slope drops its two eastern corners. An ordinal slope drops three corners, keeping only the one opposite the diagonal it descends toward.

So each corner has two states: raised (1) or dropped (0). Four corners means four bits: half a byte, or a nibble (opens in new tab). I read the corners like lines on a page, the north side first and then the south side, each from west to east:

• north-west is 1000
• north-east is 0100
• south-west is 0010
• south-east is 0001

A flat tile is 1111. The east slope is 1010: its two western corners stay raised, and the two eastern ones drop. The server keeps all nine shapes in one array:

var grassCorners = [9]uint8{
	0b1111, // none
	0b1010, // east
	0b1100, // south
	0b0101, // west
	0b0011, // north
	0b0100, // south west
	0b0001, // north west
	0b0010, // north east
	0b1000, // south east
}

Each tile's position in the tileset is its index into that array, so reading a tile's shape is one lookup. The client has the same nine values in GDScript.

When you step east, the east edge of your tile touches the west edge of the next one. Each edge has two corners. Your north-east corner touches their north-west corner, and your south-east corner touches their south-west corner.

An edge is a straight line between its two corners. If both pairs of corners sit at the same height, the two edges are the same line, and the surfaces meet. If either pair is off, there's a step or a gap between the tiles, and you can't walk across.

Take a step east from a flat tile onto the top of the east slope:

Your north-east and south-east corners are both raised, and so are their north-west and south-west corners. Both pairs match, so you can take the step.

Now put the south slope there instead:

The northern pair still matches. But your south-east corner is raised and their south-west corner is dropped, so the edges pull apart toward the south. You'd be stepping onto the side of the slope, so the game blocks the step.

The rule is the same in all four directions: compare the two corners on the edge you're leaving through against the two corners on the neighbor's opposite edge, paired by which ones touch. Only those two pairs go into the check.

To compare corners with bitwise operations (opens in new tab), the corners that touch have to sit in the same bit position. Stepping east, your north-east corner is 0100, but the corner it touches, the neighbor's north-west, is 1000.

That's why the bits go in this order. Each eastern corner sits one position to the right of the western corner beside it: north-east is right of north-west, and south-east is right of south-west. So shifting the neighbor's nibble right by one moves both of its western corners into the positions of the eastern corners they touch.

Take the east slope, 1010:

North-west lands on north-east, and south-west lands on south-east. The other two corners end up where they don't mean anything: north-east slides into south-west's position, and south-east falls off the end. A mask of 0101 keeps the east edge and clears the rest:

1010 >> 1       = 0101
0101 & 0101     = 0101    the west corners are now in the east corners' spots

A west step is the same move in the other direction, a left shift by one.

North and south steps move a whole side, which is two positions. Stepping north, your north corners touch the neighbor's south corners, so a left shift by two lines them up. Here it is on the north slope, 0011:

The neighbor's north corners spill past the fourth bit, and a mask of 1100 keeps only the north edge. A step south is the reverse, a right shift by two.

With the bits lined up, only the two corners on the shared edge matter. You mask each edge so the other two corners go to zero: a 1 in the mask marks a corner on the shared edge, and ANDing clears everything else.

Both edges are masked now, so the question is whether they match corner for corner. With everything else cleared to zero, that's a plain equality check: fromEdge == toEdge.

You're on from, stepping onto to. The diagrams below use the same names.

Here are the two east steps from earlier. The dashed corners are the ones the east mask leaves out.

The north-east corners match, but the south-east slot doesn't: the from tile's south-east corner is raised, and the to tile's south-west corner shifted into that slot is dropped.

On the server, a switch on the direction picks the mask and the shift:

var edgeMask, toCorners uint8
switch direction {
case math.North:
	edgeMask = 0b1100 // north-west, north-east
	toCorners = to.Corners() << 2
case math.South:
	edgeMask = 0b0011 // south-west, south-east
	toCorners = to.Corners() >> 2
case math.East:
	edgeMask = 0b0101 // north-east, south-east
	toCorners = to.Corners() >> 1
case math.West:
	edgeMask = 0b1010 // north-west, south-west
	toCorners = to.Corners() << 1
}
fromEdge := from.Corners() & edgeMask
toEdge := toCorners & edgeMask

The client runs the same code, translated to GDScript.

The examples above keep both tiles on the same layer. Stepping up or down a layer uses the same shift and mask, but the comparison changes to account for the one-layer difference between the tiles.

A raised corner sits at its tile's own layer, and a dropped corner sits one layer below. Once the tiles are on different layers, two corners at the same height no longer have the same bit, so equal edges stop meaning the corners meet.

Two tiles more than one layer apart can never meet, since no corner sits more than one layer below its own tile. An earlier check rejects those steps before the edges are compared, so elevationChange here is always -1, 0, or 1:

switch elevationChange {
case 0:
	return fromEdge == toEdge
case 1:
	return fromEdge&^toEdge == edgeMask
case -1:
	return toEdge&^fromEdge == edgeMask
default:
	return false
}

Going up, the from edge has to be all 1s and the to edge all 0s. That's because the to tile is a layer higher, so its edge has to dip all the way down to meet the from edge, which stays all the way up. For example, stepping east from a flat tile onto a west slope one layer up:

To check this with bitwise math, AND NOT handles both edges in one operation. It keeps a bit only where the first value has a 1 and the second has a 0. Go writes AND NOT as &^; most other languages write a & ~b.

A truth table (opens in new tab) for AND NOT: each row is one pair of input bits and the bit that comes out.

So fromEdge &^ toEdge keeps each corner that's raised on from and dropped on to. If every corner on the edge survives, the result is the whole mask: fromEdge&^toEdge == edgeMask.

Going down is the mirror: the from edge has to be all 0s and the to edge all 1s. That's because the to tile is a layer lower, so the from edge has to dip all the way down to meet the to edge, which stays all the way up. For example, stepping east off an east slope onto a flat tile one layer down:

Swapping the two sides of the AND NOT checks this. toEdge &^ fromEdge keeps each corner that's raised on to and dropped on from. If every corner on the edge survives, the result is the whole mask: toEdge&^fromEdge == edgeMask.

The server and the client both store those nine numbers. Four bits describe a tile; each step is a shift, a mask, and a compare.

The numbers earlier in this post add up quickly: a few hundred checks for a long walk, thousands when A* exhausts a map. The check has to stay cheap.

On my MacBook Pro (Apple M5), the server's full geography check (the same shift, mask, and compare, plus direction and layer guards) sustains about 50 million checks per second against a random grass map: one million adjacent tile pairs on a 36×36 map with two layers and random slopes.