Blobs in Games

From Red Blob Games's Blog

Procedural name generation using pronunciation changes #

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

Hexagon tiling of a sphere #

Image from Wikipedia

Recently two people asked me about making a tile-based game that uses a sphere topology. Some games have tile maps that wrap around. Civilization for example lets you go off the left side of the map and you warp to the right side. You can’t go off the top or bottom of the map. In 3D space, this would be a cylinder. Some games also let you go off the top side and warp to the bottom, and vice versa. In 3D space, this would be a torus. But most tile map games don’t use a sphere. Why? The sphere doesn't tile. I thought … can we almost tile it? The answer is yes!

I wrote up my notes here including a small interactive demo. This is a quick & dirty investigation and not one of my longer polished articles; see this post about my wanting to write pages more quickly.

Labels: hexagons , maps , triangles

Outside the box #

Labels: design , making-of

3 Whys - what problem am I addressing? #

I've wanted to write a page about coordinate transforms, but I've started it and abandoned it several times.

The first version was about matrices. I had seen Nicky Case's interactive explanation and Max Goldstein's animated explanation but I wanted to write something more basic. I wrote out an outline showing how matrices could be used for translate, scale, rotate, and shear transformations, and how those could be combined or inverted to generate all the effects we want.

After struggling with this for a few weeks, I put the page on hold.

I returned to it after a friend of mine suggested that I take matrices out completely. I had to ponder that for a while. Surely, the whole point of the page was to show how matrices worked. How could I do that if I took out matrices?

I came up with a new outline that pushed matrices to the very end. I covered all the transforms first, with simple code to implement each. If you have a series of transforms A, B, C, and you want to transform point p, you can call C(B(A(p))). At the end I introduced matrices as a uniform representation of all the different types of transforms. They also offer a way to combine transforms together, so that you can call (C ∘ B ∘ A)(p).

I had implemented lots of interactive diagrams for this page (see the draft version), but in the end I was unhappy with that version too.

There's a technique called 5 Whys (or 3 Whys) that I should've tried.

Why do I want to explain matrices? Because they are a nice way of implementing transformations.

Why do I want to explain transformations? Because they are a uniform way of thinking about operations we need in games: translate, scale, rotate.

Why do I want to explain translate, scale, rotate? Because they are a clean way to solve problems with game cameras: scrolling, zooming, rotating, and isometric views.

Aha! Maybe that's the real problem: game cameras. Instead of starting with matrices and then explaining how they represent transformations and then explaining how transformations can be combined, I could start with game cameras and then work my way up to transformations and then matrices.

I'm going to make another attempt at an outline for this page starting with game cameras.

Update: [2016 Aug] Well, I failed. I lost motivation to work on this so I've put it on hold … again. I think I may take a long break from tutorials.

Labels: making-of

Minor A* page improvements #

Labels: making-of , pathfinding

Updating my Introduction to A* #

One of the things that's bothered me about my Introduction to A* page and also my older A* pages is that I use grids everywhere. I fear that some of my readers will think that A* is only for grids or that it's best with grids. In my opinion it's worst when it is given grids, especially grids where every step has the same movement cost.

I decided the simplest thing I could do would be to change the grid map at the top of the page. That's the first impression a reader gets. Instead of showing non-grid maps halfway down the page, I should show a map that's not a grid. That way the reader immediately sees that we're not solving a grid problem. This was the first map on the page:

I took some graph paper and came up with a polygon version of this map. I hand-coded it and got the A* page to show it:

Although making the initial version of this map with pen and graph paper wasn't too bad, iterating was quite a pain. I decided to make a quick & dirty tool to edit the shapes. I wanted to edit the graph connectivity too but didn't want to spend more than an hour writing the tool, so I didn't implement that. I put the connectivity in manually.

The tool helped a lot! I made it output JSON, and then I copied-and-pasted that JSON into my A* page, where I wrote some code to turn that into the diagram. I spent a few hours on that map and also several others. The tool made it so much easier to edit maps that I ended up making more maps for the page.

After I had this new map up, the next step was to add a section to the page that described graphs. Although I have a link to another page that describes graphs, I think the input and output to an algorithm are too important to not explain on the main page.

I had implemented the A* diagrams with layers (see this); I was able to easily add new layers to show graph nodes and graph edges. With this I made a new diagram:

I wanted to demonstrate two things with pathfinding graphs:

Completely different game maps might have similar pathfinding graphs. I drew a game map based on StarRaven's cartography brushes that shared the same pathfinding map as the main example.

The same game map can be represented by different pathfinding graphs. I added two more pathfinding graphs for the same game map:

Comparing these, you can see how A* has to do a lot more work when the pathfinding graph is a grid than when the pathfinding graph is a navmesh or waypoint graph. If you're looking to optimize pathfinding on a grid, the first thing to try is to construct a non-grid pathfinding map.

With all of the new content on the page, I also wanted to simplify some of the other parts of the page. I decided that the contour maps were the least valuable concept, and removed most of the contour map diagrams. I think it's an interesting way of looking at things, but I was never quite happy with them, and they probably belong on an advanced level page, not on this introductory page.

While testing on iPhone and Android, I realized that I had never finished a touch version of the drag-and-drop maps. Until now, it didn't matter, because the diagrams were grid-based, and I had a touch version of the grid code. I had to fill in the non-grid touch event handlers. It doesn't work that well but it's good enough for now.

I'm much happier with the page now, although I still have some work to do on the wording. Take a look! There's still more I want to improve on this page.

Labels: making-of , pathfinding

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.

Labels: annual-review

Updating Probability of Damage Rolls #

Probability of damage rolls was the first interactive tutorial I wrote on redblobgames.com. 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.

Labels: making-of

Hex grids: finishing up the code generator project #

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: grids , hexagons , making-of , project

Hex grids: more on coordinate names #

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.

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:

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: grids , hexagons , making-of