Last year while working on my new introduction to A*, I decided to try something different for me. Usually I focus on the math, algorithms, and techniques, and let the reader figure out the code. However, for the A* page, I wrote a companion guide that shows how to implement A*. It's simple and unoptimized but I hope it's easy to understand, and shows all the tricky bits that I sometimes gloss over on the main page. While going back through my guide to hexagonal grids, I was improving the pseudocode examples on the page and realized I should probably help people who want to write code.

What usually happens is I have an explosion of questions and possibilities. What languages should I use? What grid variants should I support? What display styles should I implement? Dan Cook writes about alternating brainstorming and culling. I was deep in the brainstorming phase, and came up a crazy idea, that I should procedurally generate code, so that I could generate sample code on the page that matched your choice of grid and programming language, and then I decided I'd learn Haxe macros to do this, and run the code generator both on the server and in the browser, and then also procedurally generate unit tests, and …

… a few months later, I realized I had gone down an unnecessarily long route.

What happened?

Implementing the code generator made me realize I could simplify the variants. That part was actually great. I learned a lot by thinking through all the different ways to structure the code, and found simpler ways of thinking about hex grids. As I simplified more and found a better class design, I realized I didn't need most of the code generator after all.

Once I realized this, it killed my motivation. I felt bad that I had spent so much time on something that didn't work out.

I had jumped right into the procedural code generator, because that part sounded like fun. And it was!! One mistake I often make with procedural generators is that I start with a cool process instead of starting with the end goal. I did that here. I should've started with the output I wanted to make, and then figured out how to get there.

The code generator project didn't really work out the way I wanted. I wasn't sure where to go from there. Should I add more languages? Should I add more grid variants? Should I add comments to the output? I realized that I was spiraling back into the brainstorming phase instead of culling. I switched to culling. No, I won't add Rust and Scheme and Haskell output. No, I won't add more grid variants. No, I won't add comments and modules and docstrings and instance methods. Instead, I'll write up what I have and share it.

Telling myself no to all the possible ways this project could go is what helped me get un-stuck. Based on what I learned from this project, I wrote up a guide to implementing hex grids and also made some improvements to the hex grid guide. I also linked to the output of the code generator, so that you can get started with some working, tested code in C++, Python, C#, Java, Haxe, or JavaScript. Time to move on to another project!

Update: [2015-05-14] I added a bit about why I wanted to generate code (to show sample code on the hex grid guide)

Labels: , , ,

Two years ago when I wrote my hex grid guide, I had to come up with some names of grid types and coordinates. There were several to choose from, and I ended up picking Cube, Axial, Offset for the grid types, and x/y/z, q/r for the coordinates. For the last few months I've been working on a procedural generator that creates various types of hex grid libraries. The guide is focused on theory, but actually making hex grid libraries made me think about implementation. This project made me realize the naming conventions I've used are a bit confusing.

Here's what I had done for the theory post: I picked names based on whether it's a 3d cartesian coordinate system or a 2d hex coordinate system. The world space 3d cartesian coordinates are a rotation of the 3d cube-hex coordinates, so they're related geometrically.

name-by-structure.png

However, in practice, I don't think about them that way. I think about the world and screen coordinates as being different from Cube. World and screen coordinates are "pixel" and Cube is "grid". Axial and Offset coordinates are also different, as they use different axes, and the kinds of operations you can do on the two are different. Cube and Axial are essentially the same though. In some of my projects using Axial coordinates, I calculate a third "s" coordinate, which is "y" from Cube coordinates. I think of the systems like this:

name-by-axes.png

My choice of names seems to be the worst combination:

  1. I use the same names for world/screen cartesian coordinates and Cube, even though they're different.
  2. I use the same names for Axial and Offset, even though they're different.
  3. I use different names for Cube and Axial, even though they're the same.

Of these, #1 bothers me the most. In past projects I've found it best to name the grid coordinates and the world/screen coordinates differently. I end up with more bugs when I use the same names for two different systems. Problem #2 is minor, because most people aren't using both Axial and Offset in the same project. Problem #3 complicates things. If they had the same name, then you'd no longer have to treat them separately. You can compute the third coordinate when you need to, or store it all the time if you prefer. Axial vs. Cube becomes "no big deal" instead of being a separate system you have to think about.

Of course, if I had known all of this when I started, I would've done things differently. The question is, what do I want to do now? Do I keep the current system because it's the same as what the last 2 years of readers have seen, or do I switch to a less error-prone naming scheme, because it helps the next 20 years of readers? If I switch, how do I support the last 2 years of readers? Do I point to archive.org, which has an older version of the page, or do I host my own second version? If I host my own, do I backport future bug fixes, improvements, and new diagrams to that version?

Trying to decide what to do about this change reminds me that I've made lots of other changes. How should I handle all the other changes I've made over the years?

  • I've switched treating pointy vs flat as a 30° rotation to a 90° rotation and then to an x/y axis flip. The x/y axis flip is more consistent with the pseudocode I give, but the 30° rotation is more consistent with the diagrams. I'm still unsure of what to do with this.
  • I've switched the inconsistent naming of "3-axis" + Cube, "2-axis" + Axial to only use Cube and Axial.
  • I've switched pixel-to-hex from showing lots of different ways to one recommendation and then listing the others on a separate page. I want to avoid a "paradox of choice" problem. This change also made me start thinking of the page as recommendations instead of a catalog of every approach I've seen.
  • I've switched field of view from one suboptimal algorithm to another suboptimal algorithm. The newer one is simpler and slower but works on all maps instead of only specific shaped maps.
  • I've switched the Axial coordinate axes to be consistent with Cube axes. I had previously claimed that the axes were different from Cube, but I was wrong about that, and didn't realize it for months.
  • I've added an explanation of how hex-to-pixel and pixel-to-hex are related. They're both matrix multiplies, and the matrices are inverses of each other.
  • I've switched the line drawing algorithm to one that mostly worked to one that always works, and is simpler. I later switched the pseudocode from something long and custom to something short and simple.
  • I've switched the pathfinding explanation from "go look at this other page and figure it out" to "here's a diagram, but then go look at this other page".
  • I've made the pathfinding, field of view, and movement range diagrams consistent in their interaction and appearance.
  • I've made many of the maps editable, including on touch devices.
  • I've added a visual explanation of the six constraints needed to make a hexagonal region.
  • I've switched the code for coordinate conversions from pure pseudocode to code that might actually have a chance of working in a real programming language, given precedence rules and integer arithmetic rules. For example, "1/2" evaluates to 0 in many languages, so I instead write "1.0/2".
  • I've fixed lots of bugs in diagrams and pseudocode.

I also have to balance this with what it will do to the likelihood of me updating the page. If it's a lot of work to update the page, I'm less likely to do it.

My plan right now is to rename offset coordinate fields q,r to col,row, but to leave alone the names of the offset coordinate systems (even-q, odd-q, even-r, odd-r). Those field names aren't used in many places on the page. I don't yet know what to do about Cube coordinates x,y,z. They show up in far more places on the page. Merging Cube and Axial would simplify things, and be even more a step towards this page becoming a recommendation page instead of a catalog of techniques. I have mixed feelings about that.

Labels: , ,

In the last post I described how I had expected to generate lots of algorithm variants, but ended up discovering a better approach. The new system is different from the system I used when I wrote the hex grid guide. It's simpler and more modular, and I have ideas for making it even simpler. If I am able to simplify enough, I may not need to generate algorithms dynamically. In any case, the final step is to convert the algorithms in abstract format into a specific programming language.

Transforming the algorithms into code was easier than figuring out how to structure the algorithms, but it was also more tedious. For expressions, it's pretty straightforward. A syntax tree like Add(Name("x"), Int(3)) turns into x+3 in Python/C/Java/JS or (+ x 3) in Racket/Scheme/Lisp/Clojure. For statements, it's pretty straightforward too, but there are a few more differences between languages, including indentation and placement of braces. For declarations, languages start differing more, with functions, structs, classes, methods, modules, namespaces, etc. I wanted to generate code that uses each language's canonical style, including naming conventions and comments. I'll show some examples, using the distance function:

Function("cube_distance", Int, [Param("a", Cube), Param("b", Cube)],
 Return(
   Int(
     Divide(
       Add(
         Add(Call("abs", 
                Subtract(Field("a", "x"), Field("b", "x"))),
             Call("abs", 
                Subtract(Field("a", "y"), Field("b", "y")))),
         Call("abs", 
            Subtract(Field("a", "z"), Field("b", "z")))
       ),
       Int(2)
     )
   )
 )
)
Python
Python uses / for float division and // for integer division. My syntax tree does not. Instead, when I see a pattern Call(Int, Divide(a, b)) I want to output a//b instead of int(a/b). This shows up in the distance function:
def cube_distance(a, b):
    return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) // 2

Python doesn't need a separate class to hold int and float coordinates, so FractionalCube should be merged into Cube.

C++
C++ uses / for float division and / for integer division, but it depends on the types of the operands. My syntax tree doesn't track the types of the subexpressions, so I don't know which I'll get. As a result, I end up with an unneccessary int() in the distance function:
int cube_distance(Cube a, Cube b)
{
    return int((abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2);
}
Racket
Division is tricky here too. Racket uses quotient instead of / when the result is going to be an integer. Like Python's output, I can look for Call(Int, Divide(a, b)) and output (quotient a b) instead of (truncate (/ a b)). Racket also supports multi-argument addition, so I could convert (+ (+ a b) c) into (+ a b c). Here's the distance function in Racket:
(define (cube-distance a b)
  (quotient
   (+ (abs (- (cube-x a) (cube-x b)))
      (abs (- (cube-y a) (cube-y b)))
      (abs (- (cube-z a) (cube-z b))))
   2))

The naming convention is cube-distance instead of cube_distance.

C#, Java
Declarations are different here. Instead of top-level functions, I need to make everything into a method. For now, I'm using static methods, but it might make sense to use instance methods for some of the algorithms. Here's what distance looks like in C#:
public class Cube
{
    ...
    static public int Distance(Cube a, Cube b)
    {
        return (int)((Math.Abs(a.x - b.x) + Math.Abs(a.y - b.y) + Math.Abs(a.z - b.z)) / 2);
    }
}

Instead of cube_distance, I should use Cube.Distance in C# and Cube.distance in Java.

The differences between languages got larger as I moved to bigger functions. The sequence and record data types translate easily: C++ arrays/structs, Python lists/records, C# arrays/classes, Racket vectors/structs. But some algorithms use sets and maps, and it's less clear what types to use there. For Racket and Haskell, I want to use a more functional style, but for C++ and Python, I use an imperative style. In the end:

  • I didn't implement the more complex algorithms. They're harder, and I decided I should prioritize getting the simple ones working across many languages and many grid types. If I had known this from the beginning, I would've used a simpler proto-algorithm approach.
  • I didn't implement the more complex approach of adapting code for each grid type. Instead, I used the simpler approach of having each grid type convert to Cube coordinates, and then use the cube algorithms. If I had known this from the beginning, I would've written the algorithms by hand instead of writing a proto-algorithm to algorithm conversion step.
  • I didn't implement all the grid types. Instead of all the variants of Cube, Axial, and Offset, I only implemented one Cube variant, one Axial variant, and two Offset variants. If I had known this from the beginning, I would've written a simpler system.
  • The code for Axial coordinates is mostly different from the code for Offset coordinates. I was expecting more code to be shared. This made think that I probably shouldn't treat these two the same.
  • I now realize that my choice of Cube/Axial isn't great. Instead of q=x, r=z I should have picked q=x, r=y! I could have switched the y and z axes on the cube diagram. If I merge Cube and Axial I'll make this change then.
  • I wrote the proto-algorithms expecting that I'd output functional style (Racket, Haskell), object-oriented style (C#, Java, Haxe), and module style (C++, Python, Javascript). Looking back, I probably should have used object-oriented style everywhere. The style differences somewhat complicated things.
  • I also wrote the proto-algorithms expecting that I'd use them on the page itself, and also convert them to code for a downloadable library. That complicated things. I should have focused on downloadable libraries.
  • The code generator for Racket mostly works but it wasn't a purely functional style (because my "proto-algorithms" are imperative). I had planned to make the standard algorithms work in a purely functional style but some of the more complex algorithms will probably be too much work to justify a separate version. Looking back, I shouldn't have spent time trying to figure out a functional style for Racket; it wasn't worth spending time on a different style for just one language.
  • I didn't implement variants in code style, such as indentation and brace placement. When I started the project it seemed like it would be cool, but it just doesn't seem important anymore.
  • I didn't implement a "pro" version of the code that would use small arrays with 2 or 3 elements instead of named fields. Thinking of them as arrays or matrices would also potentially allow SIMD or GPU instructions. Pointy vs flat variants become an index swizzle. Converting hex to pixel and pixel to hex become matrix multiplies.

It's been a fun project, and as usual there are so many more things I want to do with this, but there are so many other things I want to do too, so I want to wrap this up.

  • Should I switch to the simpler system that merges Axial and Cube together? This will require a major update to the hex grid guide. It would make my advice much simpler. Instead of "use Cube for calculations and Axial for storage" I could say "use Axial everywhere". However, I'm worried that it will annoy anyone who's using the current hex grid page, because the new system will be incompatible.
  • Should I treat pointy vs flat as an x/y switch or as a 90° rotation? I am leaning towards x/y switch. I will also have to switch q/r to keep q being "columns" and r being "rows".

What's my next step? Testing. I have unit tests for the generated code, and they all pass, but I want to test the code in a real project. What real project do I have? The hex grid page itself. I'm going to replace the hand-written hex grid code for the page with the generated code. This will give me confidence that I have the right design and set of algorithms.

What are other things I need to do before I publish? Add comments to the generated code, implement more outputs (Javascript, Typescript, Java, Objective C, Racket), add an option for overloaded operators (+ and ==) in languages where that's standard style, and figure out instance vs class methods.

That's it for now. My blog posts aren't polished but I hope they give you a "behind the scenes" view of the stuff that goes through my head and the things I try while working on these projects. I also find that trying to write down what I'm doing helps me work out the design and details, and this series of posts was no exception. By "thinking out loud" I've been able to resolve some of the issues I had been trying to figure out. I hope to have the rest of the code generator finished in a few weeks.

Labels: , , ,

Popular Posts