Tuesday, March 24, 2015

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.

design of my hex grid code generator

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.

combinations of code to generate on the server and client

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: , , ,


Christophe wrote at March 25, 2015 6:13 AM

The multi langage feature is indeed may be a little overkill :)
A library to handle the most common game algorithms (path finding, grid, field of view ...) would be great. In JavaScript, because the world need another JS game library :)

Amit wrote at March 25, 2015 9:29 AM

Christophe, check out rot.js — it has pathfinding, field of view, and several other useful algorithms in Javascript :)

Christophe wrote at March 25, 2015 9:58 AM

Oh nice !

Herman Tulleken wrote at March 25, 2015 8:49 PM

An interesting project! I look forward to read the followup post.

For our Grids library we had a similar problem to solve, not for versions of hex grids, but for a wide variety of grids (triangular, rectangular, Cairo-pentagon, etc.). We only need one language (C#) and fixed the coordinate system for each grid type. And although many algorithms can be abstracted to work on general grids, it cannot be done completely if you take other factors in mind (performance / memory allocation, and limitations in C#). In the end, a large amount of our code is actually generated using text templates.

And this works OK, but things we didn't think about started popping up their heads. One is the definition of distance, which may be different even for a single grid type and coordinate system. And the idea of non-symmetric distance (where going up is more expensive than going down). And neighbors (different definitions are possible for rect grids, for example).

The generation also makes the library surprisingly brittle in it's darker corners. It also makes it very expensive to add a new grid (a lot of machinery is necessary under the hood that seems silly), and it deals poorly with 1D and 3D grids...

Grids and grid code is a fascinating subject!

Amit wrote at March 26, 2015 10:53 AM

Herman: interesting! I had wondered how that grids library was implemented because it goes so far beyond any other grid library I had seen. It's really amazing.

I agree, grids and grid code are fascinating :)

Craig wrote at March 27, 2015 6:26 AM

It sounds like your great idea had a little slippery slope, that slid you right into a black hole of never ending turmoil ;)

Amit wrote at March 28, 2015 9:23 AM

Craig: yes, very slippery … I'm still on it, trying to figure out what to do :)