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:

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.

Probability of damage rolls was the first interactive tutorial I wrote on I was just starting to learn how to make diagrams with d3.js and SVG. On that page I also used Bret Victor's Tangle library.

I structured the page in "textbook style", because that's what I was used to. I started with the simplest thing (rolling one die) and worked progressively towards more complicated things (multiple dice, min/max of rolls, discarding rolls, and critical hits). For each scenario, I presented the idea, the code, and then a histogram of the values you'd get from that code.

One of my goals was to structure all of my pages so that I'd first give you the solution you were looking for, and then give you an idea that would change the way you thought about the problem. For the damage rolls page, the problem you're trying to solve is how to set up the rules for the dice so that you get a distribution of values that you like. You fiddle with the rules, look at the distribution, fiddle with the rules again, look at the distribution, and keep fiddling until you get the distribution you want. The big idea was that you should start with a distribution, and then work backwards towards the code. That way you don't have to keep fiddling with parameters.

When I wrote the page, I was just learning how to make diagrams. The level of diagrams on that page took plenty of effort, and I decided not to implement the "work backwards" diagram: letting someone draw a distribution, and then generating corresponding code. It was more complicated than the others and I thought it'd take too much time.

Since then I've gotten better at making diagrams. I decided to attempt the two interactive diagrams I had wanted for that page but hadn't implemented. The first is making the existing non-interactive diagram in section 3 interactive. It shows an arbitrary distribution:

I wanted to make the distribution editable. You should be able to drag the bars up and down to change their size. To do that, I added a mouse drag handler to the bars. Using the x position of the drag, I calculated which column you are over, and set the bar height to the y position of the drag. However, that wasn't enough, because if you made the bar very short, you can no longer get the mouse over it to drag it back up. I added a white <rect> underneath the bars and put the same drag handler on there. That way all the mouse events would be captured. There are probably some things I could do with SVG's pointer-events CSS property without making the rectangle white, but making it white was the easiest thing to do.

Looking back on it, this diagram was fairly easy to implement. It only took an hour. However I think it would've taken far longer back when I originally wrote the page. I barely understood D3, I didn't understand d3 mouse drag, I didn't understand SVG events, and I had been thinking I needed separate drag handles on each bar instead of the much simpler drawing UI pattern. Looking back on that code, I can see how much I've learned since then.

After the first diagram, I showed the code for a four-valued distribution, and then explained how to generalize it to work for any size. That's where the page ended. I added a diagram here to show that it works for any size. I wanted to let you draw any distribution you wanted, and show the code for it:

The "code" is actually a table. It's an array of values, which you pass to a function roll() that I previously gave.

With this diagram, the narrative of the page is complete. First I take you from random number code to random number distributions, for lots of different variants of code. Then I say that you should be choosing distributions first instead of choosing code first. Then I let you draw the distribution you want and show the corresponding code. I'm pretty happy with the way section 3 looks now.


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

Popular Posts