Blobs in Games: 2015-01

From Red Blob Games's Blog

Improving pseudocode on hex grid reference #

I’ve been updating my hexagonal grid reference and noticed how bad the pseudocode is. I took a few days to clean it up.

Here’s a loop that was setting variables and also calling graphics commands.

for each 0 ≤ i < 6:
    angle = 2 * PI / 6 * i
    x[i] = center_x + size * cos(angle)
    y[i] = center_y + size * sin(angle)
    if i == 0:
        moveTo(x[i], y[i])
    else:
        lineTo(x[i], y[i])

I replaced that with a function that be used independently of the line drawing code:

function hex_corner(center, size, i):
    angle = 2 * PI / 6 * (i + 0.5)
    return Point(center.x + size * cos(angle),
                 center.y + size * sin(angle))

I’ve also switched from separately tracking x and y to using a Point class/struct/record with x and y fields. This more closely matches what most people will be doing.

Here’s another example of a code snippet without any clear indication of how to use it:

neighbors = [
    [+1, -1,  0], [+1,  0, -1], [ 0, +1, -1],
    [-1, +1,  0], [-1,  0, +1], [ 0, -1, +1]
]
d = neighbors[direction]
return Cube(x + d[0], y + d[1], z + d[2])

What’s wrong with this?

1. neighbors is a constant and doesn’t need to be initialized every time you need a neighbor.
2. The return statement makes it clear this is part of a function, but the function is nowhere to be seen.
3. The inputs to the function are apparently x, y, z, direction but it’s not stated.
4. The output is a Cube object, but the input is three separate numbers x, y, z instead of another object.
5. The elements of the neighbors array are arrays of integers, but they should also be Cube objects.

Later on the page I call a directionmethod on a Cube object, but I never define that. The direction method is related to the neighbors function.

I rewrote it like this:

directions = [
   Cube(+1, -1,  0), Cube(+1,  0, -1), Cube( 0, +1, -1),
   Cube(-1, +1,  0), Cube(-1,  0, +1), Cube( 0, -1, +1)
]

function cube_direction(direction):
    return directions[direction]

function cube_neighbor(hex, direction):
    return cube_add(hex, cube_direction(direction))

1. The array is now defined outside the function, and the elements are cube objects.
2. The logic is separated into cube_direction, cube_neighbor, and the helper function cube_add. I can now use cube_add because the array contains cube elements instead of arrays of ints.
3. The input to the function is a cube object, although I don’t list the types in the pseudocode. This is something I want to address later.

Here’s another example of potentially confusing pseudocode:

function hex_distance(Cube(x1, y1, z1), Cube(x2, y2, z2)):
    return (abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)) / 2

What’s wrong with this? It’s mostly ok, except that I use destructuring bind (pattern matching) in the function arguments. I think most readers will prefer this:

function cube_distance(a, b):
    return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2

I’m also removing some of the inlining. Here’s an example of hex-to-cube inlined:

function hex_distance(Hex(q1, r1), Hex(q2, r2)):
    var x1 = q1
    var z1 = r1
    var x2 = q2
    var z2 = r2
    var y1 = -(x1 + z1)
    var y2 = -(x2 + z2)
    return (abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)) / 2

If you’re just skimming the page, you’ll have no idea where or why all those variables are there. I hope the new version is clearer:

function hex_distance(a, b):
    var ac = hex_to_cube(a)
    var bc = hex_to_cube(b)
    return cube_distance(ac, bc)

Throughout the page I had a mix of top level code, functions, and methods, and the reader would have no idea where they came from. I’m trying to be consistent in using functions everywhere. I’m also trying to consistently name these functions hex_* and cube_* depending on whether they work on hex (axial or offset) or cube coordinates. I’ve also added implementation notes in various places where there might be something tricky. I hope these changes will make it easier for the reader to understand how to turn the pseudocode into actual code.