Wednesday, April 19, 2017

Outside of games or even product development, there's a broad problem called global optimization in which you are trying to find the maximum of a function in some space. If we think about a “space” of all possible game designs, then we're trying to find good places in that space. Hill climbing is the simplest approach to function optimization — in each iteration you make a step to improve. The problem with hill climbing is that you run into “local maxima” — you are at the top of your little hill but there's somewhere far away in game design space that's even better. You can't see that far away so you never find those other game designs. Metaheuristics are different approaches to dealing with this for function optimization; some of these ideas also seem to apply to game development:

  • Simulated annealing says: start with big steps early on, make smaller steps later on. This already happens with many games, with early development making larger changes and post-launch being smaller changes.
  • Swarm optimization says: explore multiple places at once. Early on, you can prototype many different related games, and then see what works well and what works poorly. Later in development it's impractical to build many different games but you can explore small variants with A/B tests.
  • Genetic algorithms says: explore lots of places at once, randomly mutate them, and make copies of the best solutions. This seems like what the modding community provides. Let them explore many alternative sets of game rules, and then incorporate the best features into other mods or into the base game.
  • Variable neighborhood search says: alternate between making small changes for a while and then making a few big changes every once in a while. This could mean periodic patches and also bigger changes in the form of expansion packs.
  • Graduated optimization says: first optimize a simpler problem, then use the solution to simpler problems as a starting point for exploring a more complex problem. This happens in games that start small and grow more complex over time.

Are there other techniques you use to avoid your game design getting "stuck" in a local maximum?


Saturday, December 31, 2016

"Space, the final frontier. These are the voyages of the starship Enterprise. Its five-year mission: to explore strange new worlds, to seek out new life and new civilizations, to boldly go where no man has gone before." –Star Trek

Five years ago I started Red Blob Games to help game developers with interactive tutorials and also to make my own games. I had already been interested in interactive tutorials since 2004 and likely even earlier than that, but it wasn't something I had spent much time on. In August 2011 I made a explanation of "blind spots" when driving a car and discovered that by playing with the diagram, I learned things I hadn't ever learned when I had merely read about the topic. I decided to make many more interactive explanations of math and computer science topics, especially for game development. It was something I wanted to see more of in the world.

Around the same time, I discovered the work of Bret Victor. He wasn't writing interactive tutorials for game development, but he was thinking much bigger. Much, much, much bigger. His articles on “explorable explanations” and “ladder of abstraction” made me realize that there's a lot more to this than I realized.

The first interactive tutorial I published under Red Blob Games was at the beginning of 2012, about damage roll calculations and probability. Also early in 2012 I became pessimistic about making my own games so I decided to focus on helping others with my tutorials.

With the probability page, I followed a "textbook style" of starting with the basics and working my way up. I think that style didn't work so well. The top of the page was too bland; it didn't make people want to read more. For my second interactive tutorial, 2d visibility, I decided I needed more of a "journalist style" of starting with the juiciest thing at the top of the page and then the details later. I think this worked better.

My third interactive tutorial was for curved roads and tracks. This project made me rethink my strategy. In 2012 I had been exploring "small" topics I didn't know much about while learning visualization, javascript, d3, svg, etc. This project took five months, and it was a topic not many people cared about. The combination of I'm learning something new (takes a lot of time, as I'm a slow learner) and it's not very useful stung badly and I had to do something different.

In 2013 I was more focused. I had some topics to explore, and I was better about prioritizing and "shipping". I wanted something that was both a topic I knew about and a topic that would be useful. I started with my guide to hexagonal grids. Not only did I want to have the best reference to hexagonal grid math on the web, I wanted to make better visualizations and a cleaner underlying implementation than I had for my previous articles. I'm quite happy with the way it turned out.

Also in 2013 I used Emscripten to port my old OS/2 game to run in the browser, I spent a month learning signal processing, and finished by writing a page about signal processing concepts and procedural map generation.

In 2014, I wanted to follow the success of 2013 with another topic I knew about and that people would find useful: pathfinding. I started with a tutorial for Tower Defense pathfinding (flow fields), then wrote a longer page about Breadth First Search, Dijkstra's Algorithm, and A*.

One thing that had gone wrong in earlier tutorials was that I explained the theory but not how to implement the algorithms. I had stayed away from implementations because I didn't want to pick a programming language, only to have a different langauge become popular a few years later. I want my pages to last for decades. But at the same time, it was definitely a weakness of my tutorials. I decided to write an implementation guide for the A* page, with both Python and C++ code, as well as a little bit of C#. To make sure that the code I presented on the web page actually ran correctly, I used Emacs Org Mode to write code that would get run during the html export process, and both the source code and its output would be shown on the page. This solved a problem I had with previous pages in which the code on the page would differ slightly from the code I had tested.

My style evolved from "journalist style" to "action movie style". In a James Bond movie, our hero might be falling out of an airplane, fighting the henchman for a parachute. Then the movie switches to Bond talking to his boss about the geopolitical situation in some country. The first scene is exciting but gives no explanation; the second scene is quiet and explains things. The movie alternates between visual-excitement scenes and story-informative scenes until we have a final battle in a secret volcano lair, as exciting as the opening scene, but the viewer now understands the plot and motivations. I now aim to start my tutorials with something cool looking, but without much explanation of how it works. Then I give explanations. Then I give something cool looking again. Then more explanations. Maybe something doesn't work out. Maybe we have to try something different. At the end, there's some demo that's cool, but better because the reader understands the algorithm.

Towards the end of 2014 I went to a workshop that Bret Victor organized to bring people together to talk about interactive documents. It was at this workshop we ended up with the Explorable Explanations page maintained by Nicky Case.

The workshop was absolutely amazing. It inspired me to write up notes on how I write tutorials (draggable markers, A* page). Unfortunately it also paralyzed me when I tried to write new tutorials. I started overthinking everything for a while. When I get stuck on complicated things I find it useful to go back to something simpler. I wrote a quick page about straight lines on a grid.

In 2015, I wanted to try something more ambitious, so I tried procedurally generating downloadable code libraries. I wanted my readers to pick a programming language, formatting style, and hexagonal grid characteristics (offset vs axial, y-up vs y-down, size, skew, etc.), and then my procedural generator would create a downloadable library that implements the hex grid algorithms for their needs. Neat, eh? I wrote a series of blog posts about this (1 - 2 - 3 - 4 - 5 - 6 - 7). I wrote an implementation guide and also generated code for C++, Python, Javascript, C#, Haxe, Java, Typescript, and Lua. I also procedurally generated unit tests for each of those languages and ran all of them as part of the publish process.

I also got a bit distracted working on pathfinding optimizations. I wrote a partial page about differential heuristics (which I think is a fantastic optimization with large speedups from little code) and a partial page about waypoint graphs instead of grids (which I'm less excited about now). 0fps wrote a nice optimized grid pathfinding library; I tried it and it ran A* in a mere 1-3 milliseconds on an 800x800 grid map. Pretty cool. But I didn't understand the algorithm and didn't write a tutorial about it.

I realized at some point that my most successful pages were about problems that I had in a real project, and the least successful pages were about problems that I expected to have in a future project. Curved roads and tracks weren't something I needed for a real project, as I've always used grids in building games. Regular A* was fast enough for all the projects I had worked on, so optimizing it further had never been something I needed to do for a real project. Every time I ventured into a topic where it didn't matter for my own projects, that tutorial failed.

This hit me hard. Over the past three years, half that time was wasted writing things that didn't really work out.

I decided that I needed to work on more real projects. I dug through existing projects to see if there was anything I hadn't written much about, and I found one: simple procedural map generation in 50 lines of code. The rest of 2015 I spent updating my skill set (C++, OpenGL, physics, networking, shaders, distance fields, etc.) instead of tutorials, so that I could work on real projects.

In 2016, I updated some of my existing pages (1 - 2), but lost motivation to work on new tutorials. I tried several times to work on a tutorial about coordinate systems but failed each time. I continued learning things by working on small projects (React.js, SVG, Lua, WebAudio, Pixi.js, neural networks, hexagonal tiling of spheres, stylized map rendering) but I don't have much to show for it. I've worked with game developers on small projects but don't have anything I can share yet.

So that's the past five years.

  1. The first year I worked on small tutorials and learned how to use Javascript, text, and diagrams to build the kinds of explanations I wanted to build.
  2. The second year I made the guide to hexagonal grids and a few other things.
  3. The third year I made the A* pathfinding tutorial, started adding implementation guides to my pages, and came up with a style I liked for my tutorials.
  4. The fourth year I wrote some fun projects but nothing had the impact of my earlier work, and I started to figure out why.
  5. The fifth year I learned a lot but lost motivation to write big tutorials.

I'm very happy with what I accomplished during this five year mission. The hexagonal grid guide and the pathfinding tutorial are the best things I've written. I loved exploring the capabilities of the medium. Web articles can be interactive explorations of topics and don't have to be static like magazine and newspapers articles. When I started, very few people wrote interactive essays, and now I see many people writing them. I think we'll see a lot more of them.

I love writing tutorials and I love working with game developers, but 2016 convinced me that I need to change my path. I don't know what's next for me. Will I extend my mission? Will I write my own game? Will I move on to something else? I don't have a plan for 2017.

Update: [2017 Mar] Going to the Game Developers Conference helped convince me that I should spend my time helping people make interactive tutorials. I'm working on two tutorials with other people, I've joined communities of people making interactive tutorials, and I'm also mentoring summer interns who are making interactive diagrams. Thanks for all the support!

Wednesday, November 23, 2016

Update: [28 Nov 2016] I had written this blog post quickly, without really explaining the context; see my notes for a better explanation.

People have used sequence-to-sequence recurrent neural networks to "translate" words into pronunciation for speech synthesis. I have been trying to go the other direction. I was inspired by the name "Daneel Olivaw" in Asimov's stories. It's similar to "Daniel Oliver" but it's a little different. The idea is to take English names like Susannah, Michael, etc., convert them to pronunciation phonemes, alter those phonemes in some way (such as the Great Vowel Shift of Middle English), and then convert the altered pronunciation into a new spelling. Then someone could use these new names for a story or game.

I think of it as a "Spelling Bee" neural network. It hears the name and has to come up with a spelling for it. Unlike a regular spelling bee, this is for made-up words. These are results I've gotten so far:

  • Changing the N in Jennifer → Jemifer Gengnifer Gethopher Jeffepher Jessifer Geshifer Gethopher Jeviffer Jesapher Jesifer
  • Changing the C in Christopher → Bristougher Dristofer Gristopher Prestofer Tristofer Threstougher Fristopher Srystofer Shrystofer Thristopher Vristofer Zristopher Ghrystofer
  • Changing the first E in Stephanie → Stophony Staphony Stophanie Stophony Stophony Styphony Sterfaney Staphony Stiffony Stephony Stophani Steuphony Stuphony Stuphony
  • Changing the IE in Daniel → Danall Danall Dannell Dannall Danhowl Danile Danelle Dannerl Danail Dannyll Danielle Danole Danoyle Danule Daneule

I'm also going to try prefixes and suffixes. It's been a fun mini project. I got to learn some TensorFlow and recurrent neural networks, even though for the most part I'm just patching together code I've found without really understanding it. The results so far seem like plausible spellings for words, but most of them aren't sufficiently name-like.

Something that I hadn't thought about before: there can be lots of different spellings for the same sounds in English (what a messed up language!). For example michael → M AY K AH L but the AY K AH reverse maps to ichae in michael, icu in bicuspid, ica in formica, iche in lichen, yca in lycan, yco in glycogen, yche in psychedelic, yc in recycle, so which of these "should" it be using when spelling that sound? How would the neural network be able to learn something if there isn't a good answer?

See my notes for a longer explanation of what I was trying to do.

Labels: ,