Hex grids: procedurally generating code

From Red Blob Games's Blog

I've been questioning some of my approach to writing tutorials. Most of the time I provide algorithms, math, and pseudocode but not runnable code. Part of the reason is that I've been on so many platforms and languages in the past, and I don't want to spend time on things that are useful today but not five years from now. Part of the reason is that I learn better by studying pseudocode and producing runnable code. And part of the reason is that many of the topics I cover (pathfinding, simulation, AI) aren't really about code, but about techniques that are useful when writing code. Most of it has to be adapted for each game.

Hex grids are different though. There's not as much to be learned by studying the code; I think most of it is learned through the diagrams and explanations. Adaptation is sometimes tricky, and I don't want you spending your time on trivial bugs like missing a negative sign. So I decided to try, for this one page, providing some useful code.

Which language? Which platform? Which of the 70+ grid types? How many combinations of these can I practically provide code for?

Well, of course, the solution is procedural generation, right? Right??

I attempted to procedurally generate downloadable libraries to handle hex grids.

The plan was:

1. Write some "proto-algorithms" that could work with any geometry.
2. Ask the reader about the geometry of hex grids being used.
3. Mix the "proto-algorithm" with a description of the geometry, generating algorithms in some abstract format.
4. Ask the reader about the programming language and style.
5. Turn the generated algorithms into downloadable code.

For example, I would write a "proto-algorithm" by hand for hex distances:

/* Distance between two hexes */
function hex_distance(a, b) {
    var ac = cube(a);
    var bc = cube(b);
    var dx = ac.x - bc.x;
    var dy = ac.y - bc.y;
    var dz = ac.z - bc.z;
    return abs(dx) + abs(dy) + abs(dz);
}

Let's say that the reader uses an axial coordinate system where x=q, y=-r, z=r-q. This is different from the one I use in my hex grid guide. So if you wanted to take the hex distance algorithm from my page and adapt it for this coordinate system, it'd be a little tricky, with some renaming and sign flipping. I should be able to generate it instead, by inlining the cube conversion:

function hex_distance(a, b) {
    var ax = a.q;
    var ay = -a.r;
    var az = a.r - a.q;
    var bx = b.q;
    var by = -b.r;
    var bz = b.r - b.q;
    var dx = ax - bx;
    var dy = ay - by;
    var dz = az - bz;
    return abs(dx) + abs(dy) + abs(dz);
}

and then simplifying that code:

function hex_distance(a, b) {
    var dx = a.q - b.q;
    var dy = -a.r + b.r;
    var dz = a.r - a.q - b.r + b.q;
    return abs(dx) + abs(dy) + abs(dz);
}

and simplifying more:

function hex_distance(a, b) {
    return abs(a.q - b.q) + abs(b.r - a.r) + abs(a.r - a.q - b.r + b.q);
}

Then if the reader says, I want Java code for this, with three space indentation, I could convert this abstract format into Java code:

public abstract class AbstractSpringBeanFactoryProxy { ... }

No, no, not like that! Sorry. ;-) How about this:

public class Hex {
   public int q, r;
   ...
   /**                           
    * Distance between two hexes 
    */                           
   public static distance(Hex a, Hex b) {
      return Math.abs(a.q - b.q) + Math.abs(b.r - a.r) + Math.abs(a.r - a.q - b.r + b.q);
   }
   ...
}

Wouldn't that be cool? Custom-built algorithms for your choice of hex grid, in your choice of language, in your preferred programming style? With comments? And if I'm generating code that could be error-prone, I should have unit tests too, right? And of course I should procedurally generate the unit tests. And if I'm generating unit tests, I should generate all possible grid variants and all possible languages on the server, and compile and run the unit tests, so that I make sure that whichever choices the reader makes, the code will be correct.

I knew it was a little ambitious, and probably way overkill, but I decided to try anyway.

Well, as expected, I didn't succeed. In the next blog post, I'll describe what happened.

Labels: grids , haxe , hexagons , project