What I did in 2015

It’s been a while since I wrote a blog post. What did I do in 2015? The first part of the year started out good. I worked on hexes:

• I updated my Hexagonal Grid Reference with better explanations, better diagrams, and better sample code.


• I worked on a procedural code generator (1, 2, 3) that generates hexagonal grid libraries in C++, Python, Javascript, C#, Haxe, Java, Typescript, and Lua.


• I also procedurally generated the unit tests for those libraries, and ran the generated unit tests on the generated code.


• I also used the generated Javascript code for a new page, a guide to implementing hex grids. My tutorials are typically about the algorithms and not the code, but for this topic I made an exception.

After that, I lost my way. I became interested in pathfinding optimizations, and wrote some things that I didn’t finish:

• L1-Clarkson based A*, with a super fast implementation from 0fps. People often want to optimize the algorithm but a lot of the time, it’s better to focus on the data. Unweighted grids are a waste of A*’s capabilities; you can greatly speed up A* by not feeding it such inefficiently structured data. The algorithm demoed on this page implements one such possible transformation. Try the demo — it takes only milliseconds, in javascript, to find paths on a large grid map. For references and code, see this page.


• Differential heuristics demo and article. This is something 0fps recommended I explore. It turns out to be pretty awesome, with huge speed improvements with only a few lines of code. Unfortunately I lost interest partway through.


• Visibility graph construction to turn unweighted grids (tons of nodes for A*) into lightweight graphs. This can both speed up A* and make the paths on a grid look “straighter”. Unfortunately with this topic too I lost interest partway through.

The problem, I think, is that in my own games I’ve not needed these optimizations. So I was exploring a set of potential optimizations that I haven’t actually needed. In practice, a lot of optimizations are specific to a project, and without having worked on a real project that needed these, I didn’t have the confidence that they were good recommendations. Also, knowing that I haven’t actually needed these reduced my motivation to explore them.

The pathfinding optimization part of the year mostly fizzled, so I stepped away from that topic and worked on other topics:

• I improved one of my older tutorials, on Probability / damage rolls. I wrote a blog post about why I was unhappy with the original version and what I did to improve the tutorial.


• Some people see my tutorial on polygonal map generation and walk away saying it’s too complicated. Well, it is. That’s not where I started. I started with something much simpler and worked my way up to the complicated one. I wrote a tutorial on the simple map generator I often start with. It’s limited, but it’s simple.

Realizing that my tutorials are better when they come from experience with real projects, I decided to take a break from tutorials and instead try some small game projects. In the last few months of the year I worked with Jetbolt Games learning about browser-based MMOs. We used Emscripten so that we could write both the server and client in C++. I played with SDL and OpenGL shaders, as well as network synchronization. This was a fun few months. It was nice to do something different. I didn’t write any of this up.

I also worked on a bunch of small projects throughout the year:

• Beta distribution from statistics — I’ve been pondering applying the interactive essay techniques I use to non-game topics. I got positive feedback from testers but haven’t worked on more math topics yet. Did you try to fill in the square? Hmm.


• Influence maps — just for the pretty pic (I think I wrote this between GDC sessions)


• Max of noise functions — I thought it might be useful for maps but I wasn’t that happy with it


• Procedural face generator — incomplete but fun to play with


• A simple shape editor that I used when making shapes for an articulated movement test using box2d. I decided that physics engines are cool but not for me. I’d rather work with grid games.


• Distance field sprites — for possible future use in a game project


• Dividers between hex regions — sometimes I write an interactive demo as a reply to a reddit question


• Chained movement — like the Snake game, but the chain can be slack

The next step for me is to get back into writing. I’ll start with some small projects and then I’d like to explore some algorithms that are useful in simulation games like SimCity, Dwarf Fortress, Rimworld, Prison Architect, Cities Skylines. For example, I learned about Munkres-Kuhn from Goblin Camp, an open source game inspired by Dwarf Fortress, but haven’t yet explored this algorithm.

Oh, and I’ve also been spending time in nature.