Thursday, January 21, 2016

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.

3 comments:

thijsmie wrote at January 26, 2016 4:45 AM

Your tutorials helped me out in a major way! I used the hex tutorial to write a game engine and I am currently inspired by your map generation to generate D&D worlds from the ground up. Thank you for taking the time to write them and I hope to see some more this year!

Bright Eyes wrote at January 27, 2016 6:19 PM

I was just going to write an email asking what you are doing now. Having delved into your pages and feeling like I barely skimmed the surface, it was nice to look at your photography for a change of pace. I just picked up a mirrorless Sony A6000, but I only bought the body and a 55mm lens. No zoom, no kit. I love it! Plus it's small and light. Your photos are gorgeous. Thanks for sharing!

I also took a train trip through Canada, but only made it as far as Vancouver ==>> Montreal, before entering the states again. I much prefer VIA over Amtrak. ;)

Shana

rob wrote at February 03, 2016 8:50 AM

Thanks for the summary, Amit. I'll have to browse back through your blog to find some good ideas to steal.