Randomized floodfill

Aside from the more prosaic graph traversals (breadth first, depth first, and the all-encompassing best first), we have a class of randomized traversals that come in useful in roguelikes. The best understood of these we call randomized floodfill.

In its simplest form, imagine a breadth first traversal, your common floodfill. With each node you visit, you push all unvisited neighbors onto the frontier; to visit the next cell, you pop one off the other end of the frontier. If you pick that cell off the frontier at random, you have implemented randomized floodfill.

The simplest class of these is useful for ponds and lakes and other natural formations. Just keep a count of the number of cells you want to visit and stop adding any more to the frontier when you have visited enough (but do be sure to run through the rest of the frontier or you’ll end up with gaps.) A uniform distribution does just fine, but if you experiment with unusual distributions you can get some really exceptional shapes.

If instead of simply pushing neighbors onto the frontier you push edges, you can distinguish between the ways of reaching a cell, if two of its neighbors have already been visited; in this way you can trivially generate labyrinths, for instance.

You can maintain more state than just the number of cells visited so far. You can make some pretty good mountains (although you need to fiddle with the distribution to make great ones) by simply decrementing the height of each new cell you visit. The random order tends to make this work out as a nicely craggy but generally smooth construction.

It’s an open question at the moment whether random visitation can help us solve any of our major pathfinding questions. A best-weighted search, for instance, might fail to find the very best path at times, but it would very probably perform better than A* when the best heuristic isn’t very good. Using randomness to break ties introduces no risk of missing the best solution and might be especially useful for collaborative pathfinding; most possible sets of collaborative moves are indistinguishable each turn from one another, and expanding a node at random is a better bet than always proceeding in the same order.

Give randomized floodfill a try as part of your procedural generation — you’re likely to find that you rarely need anything better than the simplest form.


What is a tile in a roguelike, anyway? If you’ve followed the development of more than a few, you’ve seen how trivial decisions at the beginning shape the whole process. Brogue’s system of layers has stretched to everything Brian has thrown at it, but at the cost of a few weird interactions (shallow water from traps will destroy spider webs; they happen to be in the same layer) and the occasional bug (a whole class of crashing bugs pertains to trying to shove too many things into a cell). Simpler systems treat simpler games very well indeed. Cataclysm has a single terrain type per cell, but it has a few flags that govern smoke and fire, and water and blood are items.

In most roguelikes, each cell has terrain, maybe a few items, and maybe a mob (a movable object), like the player or a monster. Because the terrain is pieced together out of repetitive chunks, they’re traditionally called tiles; it’s helpful still to distinguish tiles from cells. Tiles go in cells. Cells are arranged in a grid. Mobs and items stand on tiles, in cells, on a grid. And if you’ll follow me in a strange convention, mobs and items can be tiles, too.

After all, as long as you can stack several pieces of terrain in one cell, you’ve got to handle more than one tile per cell. You’ve got to deal with rules about which terrain can stack and which keeps everything else out, which block FOV and how they transition from turn to turn. That’s most of the complexity necessary just to toss in items and mobs as tiles. Most, but not all. What’s missing is a model of independent behavior, of the agency exhibited by mobs and the potential for action implicit in items.

Let’s be puzzled, for a moment, by the fact that mobs exist in cells. It makes sense that the body of a goblin should be there, but it seems like its intelligence is something else entirely. Follow this suspicion a moment. I’ve often seen roguelikes handle this by attaching an AI object, a mind to the mob, which still exists in the cell, but this is unnecessary deference to realism. From the standpoint of code clarity, especially if coroutines are cheap, it makes much more sense for the mob’s intelligence to be the free thing that uses the body in the cell to find its way through the world. Notice the appealing symmetry with the experience of the human player, who manipulates the world by way of the @ that takes commands and tells what it can see.

In my 7DRL last year I settled on the name cog for this floating intelligence; there are more exact names, but none so short with so few implications. A cog is arbitrary code, free (up to a practical limit) to use any language faculty it needs, to make decisions and interact with the world — but the world it interacts with is governed exclusively by the tiles it injected into it when it was spawned. And those tiles exist in cells, and the cells exist in spaces (of which a grid is the most sensible example) and those spaces are responsible for telling the cog, through its tiles when it asks, what it can see, where it can move, whether it can attack, and so forth.

This is the upshot of the breadboard metaphor, and these spaces happen to be supersets of the topologies from PDS.

The lovely thing is that the cog can store references to its tiles; it can move its tiles around each turn; it can send messages through its tiles to neighboring tiles, which then dispatch those messages to the cogs they’re in, which can either handle them or else leave them to a default. Incredibly complicated spatial interactions can be handled like this, and the architecture underlying it really isn’t terribly difficult. Multitile enemies, lever and door puzzles, moving platforms, and more — all quite easy.

Spaces organize cells. Cells contain tiles. Cogs inject tiles into cells and then use those tiles to send messages to other cogs. The design of the message system can be complicated but it doesn’t need to be; more on that soon.

The Breadboard Metaphor

The dungeon is a breadboard all wired up. Plug a monster in here and a player in there, and see what signals they can send each other: if they’re adjacent, they can talk about melee; if they’re in bowshot they can talk about arrows; if they’re in disjoint rooms they can, at best, talk about telepathy. (This can be taken as another way of looking at whitespace reasoning.)

Two kinds of problems succumb to this view. It’s a really practical way to understand how players will experience a new game component, since you can run down a mental list of relevant arrangements and work out which ones are covered; you can also identify arrangements that nothing really interacts with in an interesting way. But it can also help you settle on an architecture that’s appropriate for your game design, and since it does that in a way that lines up with your game design, it’s really good news.

The breadboard clearly doesn’t contribute anything (formally) that thinking about graphs won’t. But it can help limit some of the flexibility of nodes and edges and make it a little more obvious what kinds of additions you can make to your game. You can either add new things that communicate or new edges for them to communicate over. Most of your edges are spatial, but you’ll find it really useful to think of stats and resources as channels of communication, too; which components in your game communicate via hp? Which communicate via the burning status? These aren’t dependent on the shape of the dungeon for their wiring, although the ability to reach into them clearly depends on it (losing hp through melee communicated over adjacency, or being set on fire by standing in a burning cell.)

One failure of the metaphor is that we can simultaneously think of our mobs as the things doing the communication and as messages in their own right, an absurdity in the physical world. No matter. Where practice diverges from the image of a breadboard we can calmly point it out and get on with thinking about our designs.

Resources (channels without location)

If you have lots of special purpose channels, it gets to be pretty easy for players to figure out what’s going to happen in the long term. You won’t see them making lots of interesting tradeoffs. A general purpose channel, like the money in your wallet or hp you can spend in battle, is subject to a kind of interference: once used for one exchange it’s unavailable for another. Instead of thinking about resources concretely and spread across time, then, you can think of them statically in terms of what they’re wired up to; what feeds into the resource, what draws from it, what’s limited by it? Most important, why is the player going to have fun managing it?

It’s often useful to look at one resource as a buffer against overruns in another. I’m particularly fond of treating hp this way; instead of seeing resources as a way of saving health, health is a way of saving resources for later. The player’s job is to cut corners as tight as possible, but no tighter, by engaging in melee whenever health can be spared. The core game, though, consists in tactical positioning and the expenditure of more specific resources.

(Channels meant as buffers fail when the player can successfully fill them forever. An absolute cap, like 100% health, a full stomach, or a packed bag, is the simplest fix. A soft cap, like decay, is a little more complicated for design and play alike. Balancing it only against the availability of a resource in the world is, in all cases, the most difficult and the most elegant protection. Games with money traditionally have too much of it, inviting this mode of failure.)

Brogue’s food clock converts food into health (through regeneration), uses health as a buffer against resource use, and puts food in the inventory along side other resources to protect against a kind of hoarding and misinterpretation of the game’s intent. These channels of communication then interact with spatial nodes by, for instance, the positioning of food in the dungeon (which can be seen through fov, detected indirectly by monster movement with telepathy, and so forth.)

A dataflow implementation

The other lovely application of the breadboard metaphor (as limited as it is) is in the way we structure our code. The general notion is that our game components (player, monsters, dungeon features, and items) merely ‘register’ themselves in the locations that interest them, and are otherwise positionless entities. A more thorough treatment will have to wait for a dedicated technical post.

Engineering PDS

With Dijkstra we have a tried and proven technique for writing powerful AI easily. It does basically everything we need. It’s easy to understand and it’s easy to modify. The result (assuming we don’t provide goals for early termination) can be processed in many interesting ways. This reprocessing leads to chances to recompute with new edge weights, new edge connections, or new starting points; because we don’t just find our path costs and call it quits, this is the Progressive Dijkstra Scan, and in order to make it work, we need the right data structures.


Some terminology: a cell is the space in which a monster can stand; a cell contains at least one tile; it exists at a location; in a grid-based game, it is embedded in a grid; it is, in an abstract sense, equivalent to a node or vertex in the graph of the dungeon, and its connections to its neighbors are edges (which is kind of counterintuitive, because you’d think edges would be boundaries if you didn’t know the language of graph theory.)

We’ll start with a graph that represents all the positions in the dungeon, and we won’t worry about the edges yet. We’ll number all the nodes, giving each one its own index. It’s ok if we waste an index on a cell like a wall where nothing can stand and where, for some purposes, we wouldn’t want to have a node; for the use we’ll make of it it’s really quite good to have one node for every cell. One cell corresponds to one easily computed index corresponds to one node. This doesn’t change from turn to turn or monster to monster.

It doesn’t get simpler than that.

To actually allocate one number for every node, we just make an array of length width * height. We’ll be doing that a lot, so our implementation will treat these as a primitive type, called an overlay. I imagine it as a transparent sheet of plastic I lay over the dungeon. It has exactly the same structure as the map, but it’s not stored in the map. We’ll have lots of convenient methods defined for them, and we’ll use them for all kinds of things: distance/cost/Dijkstra maps; scent maps; edge weight modifiers; gas and fluid maps; masks; field of view scans; map memory; the dungeon map itself; an inverse lookup from node numbers to coordinates; representing derived topologies.

If your language has templates, you’ll be using them for this; you’ll have something like class Overlay<TTopology, TType>. In a language like LuaJIT, with its powerful ffi, you’ll write something like overlay.new(topology, ctype), and internally you’ll allocate cells = ffi.new(ctype .. "[?]", 1 + topology.length). (The topology is the shape of your dungeon; more on that in a moment.)

With the right set of operations on overlays, you can trivially make any of these things interact with each other. That’s powerful.

Graph Topology

An overlay is made to fit a topology, the shape of the dungeon. So far we’ve only really looked at the fundamental topology, which describes the shape of the dungeon. Think of it as a conversion between the abstract world of nodes-and-edges and the more concrete world of coordinates and rooms. We’d like the same techniques to work on square maps, hex maps, Penrose tilings, arbitrary non-geometric maps. The fundamental topology is all about extracting the simple, predictable part of the geometry, without worrying about details pertinent to the current dungeon. It needs to know (1) what a coordinate looks like, (2) how to convert a coordinate to an index, (3) how many nodes it has, and (4) how to convert an index back to a coordinate. But since we can just create an overlay of coordinates, (4) is trivial and doesn’t depend on topology at all.

If we have more complicated rules to deal with, they’ll be introduced as derived topologies. Derived topologies exist in a hierarchy like an inheritance hierarchy; if two overlays share the same ancestor, it’s easy to intermingle them. That’s one reason we want the fundamental topology at hand; without it, we wouldn’t be able to use interesting results together.

We have different edges depending on what’s moving around the map. An eel can’t move where a gorilla can. So even without worrying about complications like time and slippery ice, there’s no single answer. That fact ends up being fantastically important, because edges only matter when we actually path through the map. We can apply Dijkstra scans repeatedly to the same set of nodes, but respecting different edges, and get interesting compound results.

We’ll represent edges by code, not data; they’ll list out the index and cost of each reachable neighbor of a given node (at a given time). Most of the time we’ll use one specialized to a particular type of monster, that knows where a waterbound monster or a flying monster can go, and bases its decisions on the map data we already have sitting around for the dungeon. With a good trace compiler like LuaJIT, these functions won’t even cost you anything, because they’ll just get inlined. Consider ways you can compose several functions to represent edges, such as starting with a really basic one that returns all neighbors and a filter that makes sure a particular creature can actually move over the edges it returns.

Deriving Topologies

Now when we want to find paths in the presence of more complicated features, like ice, we need to build on top of the foundation we just laid. The rule concerning ice in Cogs of Cronus, to recap, is that you can move in the direction you just moved, or 45-degrees off of it, but you can’t double back without first skating in a circle. That means there are nine different states you can be in while standing on the same tile of ice: you just moved left, you just moved up-left, you just moved up, you just moved up-right, you just moved right, you just moved down-right, you just moved down, you just moved down-left, or you weren’t moving at all. We need one node for each of those states. We could just make nine nodes for every cell on the map, but that’s bloated and inflexible.

You can look at a cell and tell immediately how many different states you need to distinguish; if it’s ice you need nine; if it’s a bridge you can stand on or go under you need two; for most cells you only need one, and for walls you don’t really need any. This is a one-to-many relationship, where each cell corresponds to zero or more nodes. The simple trick to represent it is to count the total number of states you need and allocate a derived topology with that many nodes. Then you create an overlay on the fundamental topology, and in every cell you store the index into the derived topology of the first node in it.

To recap: Create a numerical overlay of the fundamental topology. Keep a counter and loop over all of the cells in order. For each cell, store the current value of the counter in the overlay, then increase the counter by the number of states you need for the cell. When you’re done, the counter will be the size of a brand new derived topology, and the overlay will tell you how to index it. Given the coordinate (x, y, s), you’ll pass x and y through to the fundamental topology, ending up with something not unlike derived_index = one_to_many_overlay:get(x, y) + s. (The one_to_many_overlay has a reference to the fundamental topology, so it already knows how to calculate the index from x and y.)

In addition to handling cases like ice, derived topologies offer a kind of compression when the dungeon is full of walls, or when you’re looking at a creature that can only move in a rare kind of cell. You derive the topology once and it’s good until the terrain changes. Since that’s a cheap operation, you can do it every turn if your terrain changes that often. And since all overlays of the derived topology make use of the same one-to-many map, it’s not costly in terms of memory.

If you have an overlay on a derived topology, you can convert it to an overlay of the fundamental topology by reducing the various states into one. You can take the lowest value in any of them, or you can take the value in one particular one, or whatever makes sense; the translation should accept a function that controls how it happens.

You also need to write new edge functions for the derived topology, although you can certainly start from existing ones. For ice, the edge function will need to pick one of the nine target cells based on which direction it’s moving to get there, and it’ll have to consider backwards motion as being blocked entirely. You can start with a function that enumerates the fundamental topology and then filter it further and decide which substate of the target cell you’re actually moving to.


These can handle one simple class of timing problems easily as long as the measure of cost you’re using is a time cost. Imagine a door that will open on turn 10. From a neighboring cell that’s reachable on turn 1, it will take until turn 11 to move into it, for a cost of 10; from a neighboring cell that’s reachable on turn 9, it’ll take two turns to move into it, for a cost of 2. As long as you’re not dealing with spaces becoming dangerous (crushers and the like), this simple scheme will always work: When you pop a node N off the frontier and try to visit a neighbor D that has a timed door, fetch the cost c of reaching N, and calculate the next moment after c at which the door will be open; use that instead of c as you continue with the scan. Instead of leaving the node the very moment we reach it, we account for having to wait until the neighbor we’re going to becomes available.

The more general intuition is that we don’t really care how long it takes to cross an edge; we really care when we’ll get to the other side. It’s actually really helpful to return the end time instead of the delta from the edge function. The edge function can handle everything for you, and your implementation of Dijkstra doesn’t need to understand doors at all.

What if you have two adjacent cells in a corridor, slightly out of sync, and instead of blocking you they would kill you? This is really pushing the bounds of best first search: The soonest you get to the first cell might, in fact, be too soon, and we can’t allow that. So you do a bit of fudging and you pretend that the first cell can’t be entered until it will actually line up with the second one; it’s a dirty hack, but it’s the only way to do it without giving up on best first search. The problem, of course, is that with nowhere to wait you can’t assume it’s always best to reach the first one as soon as possible.

Algorithms on Overlays

How about a simple operation like taking the sum or product of two overlays? You don’t even need an edge function for that! You just make sure they both use the same topology and loop over the array. This is exactly what overlays are for: The great majority of operations are just as simple as this. Finding minima and maxima, totals, sums and products, clipping one overlay against another, using a condition on one overlay to pick a value from two other overlays — they’re all trivial.

Given an overlay (which has a reference to its topology) and an edge function, we can write even more interesting algorithms. Often we’ll want another overlay or two for a workspace — we can mark nodes as visited, for instance, or keep a doubly linked list of them (Brogue’s pathfinding actually works this way.) With that trick in hand, it’s trivial to write floodfill; add the first cell to a frontier list, and then repeatedly remove one cell from the frontier, mark it as visited in the workspace, use the neighbor function to visit all the neighbors, and add all the ones that aren’t actually visited onto the frontier. Repeat until the frontier is empty.

You can even do fluid simulation this way, but you’ll want your edge function to indicate how wide each edge is, too. (In a later article on fluid simulation, I’ll lay out the details.)

To implement Dijsktra, start with the same strategy as floodfill, but instead of visiting the frontier in arbitrary order, keep the frontier sorted. That’s all it takes. And if you are treating your costs as time, you can pass the time associated with the node you’re processing through into your edge function, so it can use it for dynamic dungeon features like timed doors. The costmap, which is your output, can also double as the ‘visited’ map, so you don’t even need an extra workspace for that.

Make sure that workspaces are cheap; it’s a good idea to have a caching or pooling strategy instead of relying on your language’s built-in allocator. You’ll be making and destroying a whole lot of them otherwise.

A Pathfinding Primer

There’s a thick mist to cut through on the way to good game AI. A data structure, after all, means nothing without a host of algorithms, and the algorithms can’t be described without their data. Everything depends on knowing everything else.

A graph consists of nodes and edges; an edge takes you from one node to another. Usually by a node we really mean a state that our system can enter; maybe it’s a position a monster can be in (quite concrete) or maybe it’s the position of everything in the game (a little more abstract). The edges just describe the way we can move from one state to another; they’re decisions we can make. That’s why graphs matter so much in game AI. They’re important everywhere, but in games we want to make decisions, and graphs make that easy to talk about.

Much of the cleverness comes in in deciding what counts as a node and what counts as an edge. That’s up to you. Sometimes you want edges to go both ways and sometimes you don’t; maybe you can only jump down a cliff, or maybe you don’t allow backwards motion because time only runs one direction. Often it doesn’t even matter (for reasons we’ll see) since the question you’re asking carries with it a sense of direction. There are lots of transformations you can make without changing what your graph means. There are bipartite graphs, for instance, where there are two disjoint sets of nodes, and every edge takes you from one set to the other; for example, you might have a node for a person and a node for a club, and edges tell you who’s in which clubs. If it’s easier you can turn the edges in any graph into nodes and end up with a bipartite graph, or turn one set of nodes in a bipartite graph back into edges, and you can even swap edges and nodes. Or sometimes you want to take a big complicated graph and simplify it by merging lots of nodes into one, losing some detail. The point is that if you ask how it has to be, you’re going to get a lot of waffling. You can do whatever you want with graphs, but that doesn’t help until you know what you can do.

Your graph might not even exist. Oh, sure, in the mathematician’s sense it exists, but it might not exist anywhere in computer memory. It might not even be possible to compute the whole thing before the universe dies. Sometimes the nodes actually exist, but you’ll just work out the edges in code; on a grid based map, there’s really no reason to construct data representing the step from one cell to another. (If it helps, remember that data doesn’t mean anything without code to read it; so pretending that an edge has to be stored as a pointer or an instance of a class, is pretending that it somehow doesn’t take code to follow that edge. In fact, you should always start with the assumption that edges are code, and only do something special if that’s clearly not true. This turns out to be especially convenient if you can easily undo an edge, since certain really thorny problems will then succumb to brute force.) It’s ok for it to be infinite if you don’t need to look at the whole thing to answer your question, but I’ll leave that for the section on Dijkstra.

What You’re Searching For

You’re looking for a path. A path is a sequence of edges. Each edge leads away from the node where the last one left you, and the first edge sets out from the source and the last one leads into the destination, if there is one. The informal language lines up with the formal language here.

When you want to find a path, you’re not just looking for the destination. If you were, you wouldn’t need a pathfinder at all; the path has to tell you how to get there, but the destination is just a location, and usually you’re starting with a destination in mind. (But not always! You can pick a path even when you have no destination in mind, so you should be able to search for a path in that case, too.) A path is a sequence of steps you plan to take, which means it’s a sequence of edges. It will never intersect itself, so it’s actually just a set of edges; but though a set is simpler in math, sequences are usually easier in computing. But sometimes the intuition that it doesn’t have to be a sequence will come in useful.

How you represent the path in memory as you build it is up to you, too. You might keep a sequence of steps to take (that is, a literal sequence of edges), or you might mark cells on the map to indicate which step you’re supposed to take out of them, or maybe you’ll keep the sequence of cells the path visits and figure out which direction to go based on that. If you use Dijkstra maps, you might not even have that: instead, you just have a score on each cell, and you construct a path as you go by moving to the best neighboring score. You can think of random walks and Brownian motion as being sequences of edges represented by the random seed!

(This isn’t any different from other data structures. Practice on a few. If you read that a list is “a first element and the rest of the list,” it means that there’s a chunk of code you can run to get the first element, and a chunk of code to get the rest of the list, and maybe all that code does is look something up in memory but that’s an implementation detail. If the rest of the list is represented by code and some state, you get a lazy list instead. Try it with the definition of any data structure you’re familiar with.)

Your search space is the set of all reasonable possibilities — so in the case of paths, you’re not searching “on a map” or “in a dungeon.” You’re searching through the set of all connected sequences of edges. But the practical sense of searching for a path through the map is identical, so you don’t usually need to think about it until you set about hybridizing multiple algorithms.

The Edges of a Dungeon

What do the edges actually look like? Everything depends on game rules. There are no edges leading from a floor into a wall cell, for instance, or through a corner that’s too “narrow” for the player to pass through. But there might be edges leading across teleports, and there can even be edges that depend on the time component of the node (remember that there will be many nodes for each cell if you need to track more state, and that that state might include time).

In Cogs of Cronus, I’ve got ice, which is slippery. That means that in addition to location you have momentum, and momentum affects where you can move next and is determined by where you moved from. So, for ice cells at least, there are actually nine different nodes: one for each direction of motion. From any of the eight neighboring cells, stepping onto the ice will lead you (for pathfinding purposes, at least) onto the node that represents that direction of motion; if you are able to stop and you wait then you move to the ninth node, which represents stillness. A little bit of thought will tell you a lot about how your monsters can think about the dungeon.

Try thinking about how you would label each node if you had to drop them all in a bag and then tell them apart later. You might name it by an <x, y> pair, or you might want to have a time component too, <x, y, t>, or you might have something like <x, y, t, <potion a, potion b, potion c>>. Even if some possible labels would never get used, this can give you some hints to help you figure out what you need for your particular problem. You always want to put as little into the label as you can. If you don’t need to know how much time has passed, don’t label the nodes that way. If you find yourself staring at graph paper, confused, you might ask yourself what you’d have to do to keep a path from intersecting itself. Sometimes there’s a bit of state you forgot.

Suppose you’re doing some cooperative pathfinding. A few different graphs make sense, and you’ll use more than one. There’s the graph (call it D) that represents the position of a single entity in the dungeon; the edges are the ways it can move from cell to cell, or wait, or teleport, or whatever. But then you can think of another graph where (let’s take the two monster case for a moment) the label of each node is <monster A is at position a and monster B is at position b>, where positions a and b are actually nodes in the simpler graph. The edges of this cooperative graph, if you imagine the monsters as moving simultaneously, will correspond to all possible pairs of edges of D (one move for each monster). If you imagine that one moves and then the other moves, then you get twice as many nodes (“A is here, B is there, and it’s A’s turn,” “A is here, B is there, and it’s B’s turn.”) but you have far fewer edges. Either way this is a huge search space and it takes some good tricks to do it well.

Search Strategies

A breadth-first search proceeds outward in shells, like an onion, visiting the source first, then all the nodes one edge away, then all the nodes two edges away, and so on out. When roguelike devs talk about floodfill, this is what they mean. To perform a breadth-first search you have to keep track of all of the “open” nodes, which are the ones in the current shell, so you can come back to them and visit their children. It’s a good approach when (as in the floodfill case) you actually want to visit every node in the graph.

A depth-first search just sets out on a path and keeps going until it hits a dead-end; then it backs up one step and tries something else. Backtracking algorithms (like Knuth’s Dancing Links) perform depth-first searches of combinations of constraints. Depth-first needs to remember its path back, which means you either need a stack or you need to mark nodes with the direction to their parent. It’s still up to you what order you pick the children of any node in; making a good guess can save a lot of time.

A best-first search also, like a breadth-first search, keeps track of open nodes; instead of running through all the nodes in one “shell,” though, it repeatedly picks the “best,” or most promising, open node. What the best open node is depends entirely on the problem you’re solving, so best-first search is a huge category. The other strategies can both be treated as forms of best-first, since in the case of breadth-first you can say the best node is the one the fewest steps from the start, and in the case of depth-first you can say the best node is the one that’s the most steps away. But best-first searches really shine when you have a different measure, such as distance, hazard, or time cost. It’s not just that you find your destination faster with a best-first search. This really useful property emerges: The sequence of steps from the source to the destination, when you find it, will also be the best path (or one of several ties for best), because if there had been a better path you would have expanded it first! (You try the best first, so of course the first is the best.)

Practical pathfinding algorithms expand the best nodes first. It is faster, easier to prove that the result is optimal, and more versatile. But it is useful to see the varieties as being more akin to breadth-first or to depth-first.

Dijkstra is more like breadth-first; it checks all of the options closer to the source before proceeding further. A* is more like depth-first; it sends runners out towards the destination, and only defaults to a Dijkstra-like strategy when they crash into obstacles. A* requires more information about global geometry than Dijkstra, since it has to know which edges are closer to the destination in order to send runners out towards it (this knowledge is called the “heuristic,” since it’s a rule of thumb for judging how far is left to go). We also normally let Dijkstra keep going after finding the destination, or we don’t even have a destination in mind, in order to get costs to every cell on the map; A* we normally terminate as soon as it finds the destination, and treat the result as the best path.

But you can terminate Dijkstra after finding a destination, or (if there is more than one), after finding a certain number of them, and you can also use a heuristic in order to find that destination faster. Make both of those simple changes and you’ve turned Dijkstra into A*.

In any search you can terminate after visiting a certain number of nodes, or after going a certain maximum distance, although then you can’t gurantee that you will find a result even if one exists; it might happen to be further away than you’re willing to look. For an AI this is generally quite ok. You can get passable results by running shorter searches most of the time, and proceeding to longer searches only if you have to, creating the appearance of indecision.

With Dijkstra we often want to visit every node, so we have to simplify our graph as far as possible. We usually want one node per cell of the dungeon, and we want edges to correspond to steps we take, and we don’t want to worry about things like backtracking. With A*, because we zero in on a path that looks quite likely, we can travel a more elaborate graph, or at least keep more information about each node. The rule of thumb is that with Dijkstra, we get exactly one number per node to treat as state, and that’s the score that we were already using to direct the best-first search.

The score, which is the cost of the best path so far, is the one extra piece of state you can track in Dijkstra without allocating additional space. (Really, though, it’s just that you’ve already allocated extra space for it.) If the number is time, then you can use that very carefully to let edge costs change with time. Monsters can wait for doors to open, or even wait for a floating platform to arrive. If that number represents an accumulated “hazard,” the chance of taking enough damage to be killed, then perhaps we believe that a certain kind of risk no longer matters after a certain threshold is passed (imagine separate shields and health, where some damage only affects shields.)

Neither A* nor Dijkstra allows us to speak of any property of the path as a whole. They cannot, for instance, prefer paths that look the most like straight lines when they move through open rooms; that must be achieved by post-processing. But if you are willing to track some extra state you can certainly minimize twistiness, defined by the number of times you have to change direction, by the same trick I use for ice in Cronus: give yourself eight nodes per dungeon cell and charge extra whenever the next step is in a different direction than the last. You can track the properties of the path, such as whether it crosses a certain kind of cell, and even to take that into account in choosing the best step to take next — but only as a tiebreaker, as with lexicographic ordering.


It is possible, in some simple cases, to find paths without doing any pathfinding at all, as such. When you have a gradient map of any kind, representing (perhaps) the distance from valuable items, or the most recent time that a cell was visible to the player, or when cells were last traversed by fleeing monsters, it is possible to find a local optimum by simply rolling down (or up, if that’s how you roll,) the map. Find the neighbor with the best score and move there by whatever edge connects you.

If this gradient has been generated by a Dijkstra search, then the result will in fact be an optimal path to the destination. Influence maps and scent maps also produce gradients. It is possible to perform arithmetic on them, cell by cell, adding or multiplying them together; consider that our computers are more than a thousand times faster than they were thirty years ago, when arithmetic on single numbers was cheap enough not to worry about, and conclude that arithmetic on thousands of cells must now be cheap, too.

You can pick a random cell in a gradient map, if you treat each cell as a score, by picking a random number between one and the sum of all cells, then looping over them and subtracting them from that number until it falls below zero.

You can treat any gradient map as a cost map for each step in another pathfinding scan. You can also treat one as the initial state when pathfinding; the number in each cell tells you how much it costs to start there. (Brogue makes extensive use of this.) Making a Dijkstra scan, manipulating the resulting gradient, and then running another scan on the result, is a potent technique.

Whitespace Reasoning

Our agents need to make sense of a complicated world. They need to outwit the player every so often and they need to make convincingly organic mistakes, not systematic outcomes on obvious clockwork. There are simpler problems to deal with; they need to maneuver and plan in a world that changes, not only with time within a playthrough, but over the scale of development. You can’t afford to hold the hand of every monster you’ve ever added, every time you add another.

(A word about the brain, by way of metaphor. We think the purpose of the brain is to deal with the world, but its first purpose is to deal with the body. It doesn’t know, until it learns, how tall you are, how many colors you can distinguish, or even how many limbs you actually grew. Its job is to cope with whatever the body throws at it. If the brain had to change every time the body changed, every mutation would be abortive and every amputation, mortal. Equate the body with the game world, not with the monster’s body; good AI lets you change the game world without worrying about breaking carefully crafted monster behaviors. It’s about looser coupling.)

I’ll start by discussing the general principle of objectification (how you pretend that your beliefs about the world are actually out in the world, and how that idea can simplify monster AI), the more specific principle of whitespace reasoning (which is the point of bringing up objectification at all), and then start to discuss Dijkstra scans from the very particular perspective of the roguelike developer. In later posts, I’ll develop these themes more completely; this is something of a cross-section.


It is profitable for an actor not to think about what it can do. It should project its capacities onto the world around it, asking what the world can do for it. This is a very practical view, but it seems strange because we use it automatically, without understanding it. An everyday object like a hammer seems to be for driving nails and, if it has a claw, for pulling them; this is the only property of a hammer that sets it apart from other objects of similar heft. But this isn’t an ability of the hammer at all — you’re projecting your own ability (that is, to swing) onto it. Your actors need to objectify the world, and each other, and themselves.

Because video game actors spend most of their time moving around, it makes sense for them to objectify the space around them. You can see this as offloading thought from the actor onto the space around the actor — whitespace reasoning. Instead of imagining that your actors think for themselves, pretend that the space they’re standing in does the thinking for them. The floor knows there’s food in the fridge; the road knows there’s work at the factory; the grass knows there’s a wolf nearby. You can think in terms of ants and their pheromones if it helps you, but I suggest that you not think about it in those terms too long. Instead, think of places that feel strange even when they’re not serving their usual function. Consider how you feel standing in the middle of an empty street, or when you’ve wandered into the wrong neighborhood, or when you’re stuck in the woods. I feel queasy cutting across a queue, during the moment I intersect it geometrically.

You want to imagine that your actors feel this way.

You’ll most often see this done by analogy with ants or hounds, though. In a scent map everything interesting leaves a smell, and smells diffuse and fade with time. Most models you’ll see go in for a very literal interpretation based on physical diffusion, which is curious, and an example of taking the analogy too far. They also tend to stop right here, because the analogy doesn’t get you any further. Influence maps are scent maps by a different name, and I haven’t seen them used in any more sophisticated way. They’re often worse, using an exponential falloff function for which there is simply no justification, but which makes reasoning about the map much more difficult.

Neither of these, of course, does more than compute distance, with a few wrinkles that are hard to formalize. Both, for instance, propagate signals slowly — a more distant change takes long to affect local values. (The reduction of jittering caused by slower propagation can justly be adduced in its favor, but jitter is likely to reemerge in unusual situations; it is better dealt with directly.) Both perform poorly, but as they are generally used sparingly, this is no great loss. We’ll be using a more general formulation that is faster, easier to integrate with other techniques, and much easier to reason about formally.

Enter Dijkstra

If you haven’t read it, read Brian Walker’s The Incredible Power of Dijkstra Maps. Brogue shows just how exciting a sprinkling of pathfinding techniques can be. The algorithm given in the article performs suboptimally, but it hardly even matters. It’s amazing what you can get away with, and it’s worth it even if you can’t put together the most efficient scan. You can do more with distance maps than immediately presents itself.

Brogue’s safety maps, which are used when monkeys run away from the player, are calculated by scanning the distance from the player, multiplying by a constant smaller than -1, and scanning again. This is a totally different world than anything done with influence maps or scent maps. The first scan detects cells that are most distant from the player; the negation turns those cells into goals, and the constant causes the monster to be willing to dash by the player to get further away. Several nonlocal effects get rolled into one map, and the monsters exhibit global thinking — all without looking further than neighboring cells. Space itself has done the thinking for them.

In Brian’s fourth case (“Desire Driven AI”), you’ll want to make sure to run another scan after adding the desire maps together, and then add some multiple of the original sum back in. Why? You don’t want to get stuck in a local rut, but you really would like to stop by water on your way to a more important goal. These Dijkstra maps treat every cell as a potential source; the scan doesn’t take a single source and minimize its cost, nor even a list of sources. Instead it lets you give every cell an effective cap. If you can’t get there cheaper from somewhere else, then its own influence kicks in. This is absolutely invaluable for safety maps and similar global reasoning.

What’s in a node?

We needn’t assume, even in a grid-based game, that one grid cell is one node. It’s certainly possible to reduce the number of nodes we need to look at; you can set one node at every doorway, for instance, and assume it’s easy to path across rooms. Each node, in that case, would represent more than one grid cell, speeding up pathfinding considerably. But that kind of optimization works against us, here; we’re looking for new interpretations of space, and that that trimming would lock us into one model.

More than one node can belong to a single grid cell. This is much more useful: It lets us track state other than position. We don’t want to track any kind of global state this way because it results in an exponential explosion of nodes, but we can track local state very easily. So keeping track of which doors have been opened is probably a bad idea, but if doors close automatically after two turns it’s fine (because we don’t need separate nodes for that state when we’re further than two steps from the door.) If there’s slippery ground, we can have nine nodes for one cell, one node for each direction of motion; stepping from a neighbor onto such a cell, actually brings us to the node that includes the proper direction.

For every two sets of state we want to track, we need to track their direct product. If we need to track whether a door is open and which way we’re sliding on ice, we need 2*9=18 nodes. If we need to track eight doors and sliding, we need 256*9=2304 nodes, all for one cell. We obviously need to control this carefully, but the general technique is too powerful to give up entirely; it’s also quite inexpensive, used carefully.

Dijkstra and A*

The explosion of nodes representing various states is the major reason Dijkstra ends up falling flat for us: Every node has to actually exist, and we expect to visit all of them. When that’s just one node per cell on an 80×25 map, that’s 2000 nodes; smaller than a couple lines of a high-resolution bitmap. When it’s sixteen nodes per cell on a 400×300 map, we hit 1.83 million nodes, about a thousand times bigger and a thousand times slower. Or keep the map small, still just 80×25, but give the player 26 potions to drink: each turn, the player can either move or drink one potion. We end up needing at least 226 * 2000 nodes, because at any given time each potion will have been used or not; in practice we need even more, so we can track the state of the effects caused by drinking potions. If each cell takes one byte (which is unreasonably compact), that’s 125 gigabytes. Good luck.

Now, one way to simplify things is to construct nodes only when we need them; until your search algorithm tries drinking the Potion of Levitation, don’t actually allocate cells for that case, and then only allocate them on the nodes you visit. But we have to add a cutoff — either limit the number of nodes we expand, or limit the maximum distance we’ll search. Neither is entirely desirable, particularly since we’ll still only explore the immediate neighborhood. If the puzzle is remotely difficult, and the potion-drinking searcher needs to make it across the map, we’re pretty much certain not to find an answer.

A* and Dijkstra solve the same basic problem, but A* relies on a few extra hints in order to avoid visiting every cell. (This isn’t a huge gain for us in the 80×25 case; whitespace reasoning is all about visiting every cell, and it’s really quite cheap to do so, as long as we avoid an explosion of states. We do need A* for some very unusual problems, and we’ll come to those in a moment.) The first hint is a destination; we have a particular node (or set of nodes) that will short-circuit our search, if we happen to bump into them. (We can add a destination to Dijkstra, too; the result is half way to A*). The second hint has to do with the order in which we search. Instead of looking all around our starting point, we take advantage of geometry to start out walking blindly towards the destination, based on an admissible heuristic, which is a guess as to how much further we need to go before we get to the destination. It’s not actually a guess: It’s got to be the absolute best case. On a simple grid based map, it’s the number of steps we’d have to take if there were no walls anywhere.

If the heuristic is always exactly right, then the search will always go straight to the destination, giving the best possible path as fast as possible. The worse the heuristic underestimates the real cost, the longer it will take us to find the optimal path, but we will eventually find it. If the heuristic ever, even once, overestimates the real cost, it becomes possible that we will never find an optimal path. A heuristic that can produce an overestimate is inadmissible.

On a map with teleports we cannot, in general, use any better heuristic than the distance to the nearest teleport (plus the distance from the destination to the nearest teleport to it). If the map is totally non-euclidean and nodes are connected arbitrarily, as they might be in interactive fiction or on a MUD, then all bets are off. We simply cannot generate a valid heuristic; there’s no grid to overlay on the nodes, anymore.

On the other hand, we’re allowed to track extra state with our A* nodes. We actually can attempt to solve a puzzle that involves drinking potions in a certain order. (Risto Saarelma wrote an AI for Vector Racer, in which players manually adjust the x and y components of a car’s velocity to navigate a track drawn on graph paper; it involved an A* search over the quartet <x, y, xv, yv>. This kind of thing is valid and really quite practical.) The only problem is that our heuristic is going to be terrible.

Dijkstra to the rescue. We can actually perform a Dijkstra scan under better-than-possible conditions and use the result as our heuristic — it’s an absolutely glorious possibility. It means that while our A* search is making the hard decisions, it doesn’t have to deal with things it’s bad at, like navigating a maze. Dijkstra, which is great at navigating mazes, has already handled that part. If the A* just follows the result of Dijkstra, whenever it’s possible, it’ll get to its destination. All that A* needs to handle, in this case, is the extra state that Dijkstra couldn’t handle. It’s a perfect pairing; the weakness of one plays off the other.

Take group coordination. It’s easy to do approximate group coordination with Dijkstra alone; monsters can path towards their target, try to stay a certain distance from each other, or follow a leader just fine. But they’ll bump into each other and you need to add game rules, like displacement, to resolve it. To do a Dijkstra scan for two monsters, over a map with N nodes, you now need N*(N-1) nodes — each monster can be anywhere. Even if you force them to stay within five steps of each other (the implementation of which is an interesting challenge), it doesn’t help matters considerably, and you risk missing an otherwise valid solution. But A* can handle the two monster case just fine, and for many more monsters, too, as long as it has useful Dijkstra scans to help it find its way.

(Other refinements to A*, like Jump Point Search, amount to a simplification of the graph the search is being performed on; they’re really only useful when certain assumptions about symmetry hold, and we’re not willing to make those assumptions. Instead, we’ll go on designing around the more general cases.)

Future Topics

In a later post, I’ll be discussing the design and implementation of the PDS (Progressive Dijkstra Scan) suite and the novel possibilities that these techniques open up. Maps no longer have to be static; monsters can understand levers, wait for each other to finish walking through narrow tunnels, and make sensible decisions about their inventories. More important than anything, though, the bad decisions they still inevitably make will make sense to players — and the bugs (for there will be bugs), will be hilarious.

Design is Constraint

This is an essay for the indecisive. This is for the writer with the blank page, the game designer with the eternal tech demo, the perfectionist who might finish something one day.


Creative output tracks with the technical proficiency of a student, initially. (Many great games were made by budding programmers, for instance.) When the overwhelming potential of the medium becomes clear, however, a student with a wide purview and high standards suddenly becomes unable to complete anything substantial. Only when the student masters the paralyzing illusion of infinite choice does output grow again, and ascend gloriously, but specifically, through the boundless chaos of possible designs.  The master puts boundlessness aside and learns to choose.

And choice is clearly the imposition of constraint. But not all constraint is choice, and that’s the first wrinkle; we’re finite, and our mental, moral, physical, and technical capacities are finite, too. There’s no kind of guarantee that we’ll find the optimal design or anything close to it. We find our ways into media, schools, and genres, mastering techniques and tools; they open us to worlds even as they constrain us. It’s entirely possible to develop a new medium, forge a new school, or spin off a new genre (entirely possible and entirely reasonable) but it’s quite probably impossible to do without entirely. These are the constraints of the designer, though, not of the design; new techniques open new spaces while they close off others, but progress in one particular work always reduces the space open to potential designs. No matter how brilliant a decision is, it is only ever one of uncountable decisions that could have been made. When you’ve struggled to wider your options, narrowing them again runs contrary to emotional sense.

The point of recognizing all this is not to uncover the ontological underpinnings of human creativity or some balderdash like that. No, it’s closer to home: Creativity, when it gets out of the expansive phase and sets into the hard work of choice, hurts. Every possible outcome you reject was one you’d have been happy to come out with. The fear of shutting out those possibilities is worse than the feeling of erasing work already done. Work already done was one possible outcome, after all, but the vaguely perceived future is of inestimable value. Before you achieve anything, anything will do: Once you start getting results, you want the perfect realization of your artistic hopes and, if you don’t know a way to avoid the feeling, nothing less. The work of art, unbegun, is infinite.

It’s a dreary fallacy to fall for.

In Writing

No one with plenty to say will find the feeling unfamiliar, when looking at a blank piece of paper, that it’s all downhill from there.  On any theme that comes to mind, you could rhapsodize for hours over tea to an eager friend on a rainy day.  And the sum of it would come out beautifully, if a stenographer were listening in, and with a bit of cutting you’d have yourself the essay you wanted — but somehow the paper’s blank face doesn’t draw the words from you the way your friend does. Anyone who really writes must have a way around it.

The prolific writer simply avoids getting stuck. Bland, profound, insightful, insipid; whatever the product, the process looks about the same. Just keep writing, no matter whether it’s the right next thing to write. Accept that whatever you write isn’t something else you could have written, and move on.

The alternative is terrible. The longer writer’s block goes on, the more valuable the finished project must be, or the whole effort feels vain. Rapid fire writing feels inexpensive, disposable, expendable to the writer; it doesn’t lend itself to writer’s block. And volumes get written, and cruft gets cut, and the result might not be great, but it’s very probably good. Writer’s block trains the writer’s eye on the infinite, on the scenes that might be written but never will, and sets the expectation up that those scenes had better get written, or what’s all this waiting for?

Make a choice and get it written. What’s this next sentence going to be? Anything is better than the blankness there now.

In Games

The writer with no specific vision never gets anything written of any length. The game designer with no specific vision can write systems just about forever. What’s worse, it can (and inevitably does) feel like having a vision. I know; I’ve been there.

The joke goes that they made this great game that you can mod with absolute freedom, and it’s called gcc. “This is going to be the best game ever,” thinks everyone who ever dared to dream big, “because you’ll be able to do whatever you can think of.” And they never actually design anything in particular, and nothing ever shapes up.

The people who are out there, getting things done, making great games, are simply making them. They’ll write posts where they tell you to do the same. But knowing what needs to be done doesn’t help. You already wanted to make a game and just get it done, so why could they and why couldn’t you? And you know you could make an even better game than theirs, with more options. And yours would let the player map the controls however the player wants. And yours would have more variety in the level design and the puzzles. Enough. It’s all about constraints, and it’s about accepting that you need to apply them to your design, and that you have to turn it into something that can one day be complete. You need to deal with the pain of limiting your options, of accepting that most things you can do, you never will: So you’ve got to choose.

Do not design for every possible option. Do not make it so that everything can be put in a backpack, and a room is just a special kind of container, and items take damage the same way monsters do, and the player can control more than one character at once, and every fluid can be put in any bottle, and bottles are just containers, so rooms can fill with fluids and items can rust in rooms full of Potion of Peroxide and — Enough. Pick solid abstractions so you can change your mind later, but make it all as simple as you can, for your particular design. Make a choice and get on with it. (Now, maybe you want to make the simulationist’s dream. That’s ok. That topic comes later.)

You want freedom, yes, so you can do whatever you want — but you’ve actually got to do it, and once you do, you’ve given up some freedom. That’s the bargain. That’s the point. Get better at what you do so you have more freedom; then hurry up and give it up, so you have a game.

Possible Futures

There’s a marriage waiting between the sense of meaning that applies to video games and the trees of future states you’ll find in game theory.  Meaning takes outcomes into account even if they never actually happen; these trees, likewise, branch out into every conceivable outcome.  Modification of future possibilities, even possibilities that will never be realized, will change the interpretation of the immediate situation.  Players sense this and experience it as meaning.

Decision trees

Let’s start by admitting that, for the present at least, we only need an informal sort of decision tree.  This is the kind of structure the player will actually work through mentally; a really complete enumeration of all possible futures is a useful construct for working out proofs, but it’s utterly intractable in games as they are actually played.  The number of possible moves each turn, and the number of turns, is simply monumental: Take Brogue.  With a full inventory and in a wide open space, you can wait, search, apply or equip or remove any one of your items, throw any of your items at any of the 400 or so dungeon cells around you.  Many of those applications, such as of a scroll of enchantment, will prompt for another item or for a direction to zap in.  In such a situation, the player has at least ten thousand possible moves.  Over the typical course of a twenty thousand turn ascension, that’s an astronomical profusion of futures to account for.

Thankfully, however, most of that variety is degenerate.  Many of those moves will actually be impossible (not least because they get you killed), and many others will be functionally indistinguishable.  There’s an incredible degree of self-similarity in the futures of these trees; sitting around waiting, in the absence of any enemies, takes the game to a new state that is exactly the same except that all child trees are one turn shorter — the rogue is one turn closer to starving.  The same is true, for instance, of the various ways of pathing across a room.  The exact sequence of steps really won’t matter much, and you’ll find yourself facing the same future as before.

This self-similarity turns out to be the key to making headway, which is rather unusual: In most situations, introducing the fractal nature of a problem serves as a distraction.  Look, look, it’s so complicated, but isn’t it pretty?  Here, instead, what we want to notice is that what had seemed dreadfully complicated (ten-thousand to the twenty-thousandth power) really mostly comprises the same simple patterns over and over again.  The differences between futures can largely be broken down into situation and resources, and this, again, is exactly what players do.  These are the tactical and the strategic subgames.

Situation and resources

My situation might be bad, but it’s just one path between my earlier state and a target state, and once I get there it doesn’t matter how I got there.  It doesn’t matter whether my health dropped to 50% or 10%, so long as I didn’t die.  It doesn’t matter whether I triggered a fire trap, so long as I didn’t burn a scroll.  It doesn’t matter whether I went north and then east or east and then north, so long as I end up where I’m going.  Situation is the part that gets scrubbed away by the passage of turns.  I might only have two possible moves this turn, because I’m in a corridor, but I’ll have more as soon as I step into a room.  My situation changes quickly.

Resources, on the other hand, describe the differences between sub-trees that propagate uniformly from parent to child.  Any turn on which I have a Potion of Healing is a turn on which I can use a Potion of Healing, but after that turn I have no more Potions of Healing to use: The shape of my options each turn changes the moment I actually use it.  Likewise, an item on the floor that I haven’t picked up is an item I can walk over to and grab whenever I please, until I’ve actually done it.  Once I’ve picked it up I can’t pick it up again.  Anything that functions in this way, from finite monster spawns to inflammable terrain to walls that can only be tunneled through once (and are forever open after), functions as a resource.

The two, it should be obvious, commute.  On a long enough timescale most resources look a lot like situations; on a short enough timescale, most situations look like resources.  How far ahead you’re willing to look determines which is which, and so, again, the nature of the heuristic becomes clear: we’ve constructed one tree of futures at a fine scale and called it our tactical situation (even though we’re not likely to distinguish every one of our ten-thousand possible moves each turn, and we’re really only considering a few dozen of them), and we’ve constructed another one by recognizing self-similarity and labeling each distinct feature of each potential future with a named resource.  A tree that looks like this is one that has a healing potion; a tree that looks like this is one where the rogue is starving; a tree that looks like this is one where the player has a powerful suit of armor.  We take each of these, treat them as a single state, and get (what else?) another tree out of it.  This is the tree we actually think about for the strategic subgame; do I pursue this resource or that one, expend this one or that?  The ugly turn-by-turn of it is abstracted away.

And the ugly turn-by-turn of it goes about attaching a sense of meaning to resources.  The general sense we get of when a particular item is useful and which items we’d like to put in our kit together, itself yields a deeply rewarding sense of drive and of mastery.  Just watch the lengths that actual players of roguelikes will go to to ascend with a more peculiar build than ever before.

Randomness and uncertainty can be incorporated just as they are in game theory: Any time the dice will be thrown, you construct a turn that will be taken not by a player but by the dice, and you annotate the edges with their probabilities.  Curiously, the optimal strategy in the face of probability tends towards two extremes, depending on whether the player can mitigate the risk of absolute failure: in the one state, expected value dominates, and rolls are treated in terms of their averages; in the other, the player considers only the worst case.  At full health, for instance, a player will treat a 20% chance of hitting as doing a fixed 20% of the damage.  When that 20% chance might kill, however, a good player will treat that as inevitable.  (A bad player, on the other hand, will systematically succumb to wishful thinking, and bet on the 80%.  This is one of several hard skills that roguelike players must acquire — but that’s for another post.)

Smoothness of time and space

The heuristic we use to counter the combinatoric explosion of a roguelike’s future can be adapted with no real trouble to games with smooth time and movement.  Indeed, smoothness is no obstacle at all: Even without relying on discrete frames of motion, we can identify arbitrary key frames between which no decisions take place.  The length of time between them does not have to be uniform, and we don’t (for reasons to be developed) need to consider reaction times.  This is entirely reasonable, in practice.  No, the true obstacle is the matter of skill.

A player is certain to decide which of two platforms to attempt a jump from, for instance, on the basis of which is more amenable to success.  The player has firsthand knowledge of skill, and can treat performance as a random roll.  A thoroughly unskilled player, aware of these shortcomings, is likely to harvest resources — to grind — in order to overcome a situational weakness by resource sufficiency.  As a child playing Mario World, I would get two feathers and a blue yoshi before entering any difficult level.  Most people do the same.

Players actually do experience these exercises of skill as gambles, and I would suggest that it is because of this equation of skill with gambling that gambling tickles our reward anticipation as strongly as it does.  Before people came along, nothing could exploit this property of our learning mechanism, just as nothing could add refined sugar to a 32-oz drink.

Bringing it back around

The interesting thing is that the process by which a player identifies possible futures is itself subject to failure, and can itself be assigned a probability.  The application of our situation/resource heuristic is difficult.  Remembering present possibilities is hard enough (and it’s one of the cornerstones of roguelike difficulty).  Anticipating future consequences is another beast altogether. The savvy player, rather than fret over this, assigns a probability to the failure to consider all outcomes, just like the platformer player did when considering a jump.

A naïve player will also internalize actual randomness as an expression of skill, and experience a psychological reward accordingly.  Designers find it easy to exploit this failure.  Traditional power curves stand on several psychological legs, one of which is this inability to distinguish skill from external conditioning, in a peculiar misreading of cause and effect.  (The same effect is also, quite probably, responsible for our trancelike enjoyment of television and film, but that’s for later.)

Players plan for their own fallibility.  This can also help us understand the psychology of hoarders; cognizant of their total inability to plan for a game with unknown rules, they preserve every possible resource for later use in repairing the damage their ignorance will probably inflict.  Good players plan for fallibility, too, and attempt to distinguish between what they could have anticipated and what they never could have.  Good designers respect that.

Games and Meaning

Games hang human-crafted assets on abstract structures to give meaning to both.


There’s a sense of meaning, rather inflexible and prescriptive, that ascribes it only to the formal relationship of signifier to signified — the word to the denotation, the clothing to the fashion statement, the blush to the thrill.  There’s a contrary sense that voids meaning of meaning, makes it an ineffable, impenetrable core of subjectivity that can’t very well be conveyed or reasoned about.  We know we want meaningful experiences.  Let’s start there. Look around you.  With a little evidence from your eyes, you’re constructing a rich model of your surroundings.  You know at a glance how the floor feels to the touch.  You know what happens if you throw the screen you’re reading from against it; you won’t be doing that.  The model is the meaning of the stimulus.  Meaning is the entire body of implicit and unperformed associations: the things you feel, know, expect, or intend, yes, but especially the things that you would feel, know, expect, or intend, if some potential interaction came to pass.

Meaning is the part of the model that isn’t inherent in what you’re taking in. To draw a definitive line between sensation and meaning is pointless.  You’re not a clean processor of raw data; your eyes aren’t cameras plugged into a soul.  Because we’re composite and convoluted beings, meanings have meanings have meanings.  The sense that something has a meaning, but that you don’t know it yet?  That’s curiosity, ambition, exploration, playfulness.  And the sense that something has no meaning, even if you try to find it? That’s ennui, boredom, depression, despair.

And when you are actuated by meaning, you’re filled with purpose.  You’re driven not only by what’s out there and not only by what’s inside you, but by an elaborate, vibrant, and fractured blending of the two.  Purpose is the sense that action has meaning, and this kind of meaning expresses itself through the will.

… and Games

When players are having fun playing our games, and not just pulling the lever for another irregularly scheduled epic drop, we hope that they’re exhibiting curiosity, ambition, exploration, and playfulness.  We hope that they’re exhibiting a sense of purpose.  They also tell us explicitly that they want games to have meaning.  Every aspect of the high-level appreciation of games (games as art, if you’ll forgive the phrase) comes back to one facet or another of meaning.  It seems we’re back where we started — we want games to mean something, but we don’t know what and we don’t know how.  But there’s an in.

When I wrote that “meanings have meanings have meanings,” I might as well have said that meaning is recursive and transitive.  If two meanings both pertain to the same object, then they end up meaning each other; they also take meaning from each other.  Fabric that is rough to the touch, looks rough; a printed pattern that once looked rough no longer looks rough once touched.  A favorite song sets the mood for a time of life, and retains meaning from the memory of that time. Feeling like a spaceman in a game doesn’t come from a grand title or a big ship.  It comes from zipping around going pew pew pew and landing on alien planets.  Once that feeling is established, then the grand title or the big ship might further it, but only then.

Every video game experience starts with components the player understands already and assembles it into a more meaningful whole.  This is where most of the recent work has been done: Juiciness, polish, gamefeel, reward cycles, and the like, are ways of exploiting the most fundamental generators of meaning.  Anything that produces a response in us, however slight, by dint of our biology or acculturation, can be amplified by a process of the accretion of meaning.  The glint of a gem, like the glint of clean water, first caught your eye; now you’re a diamond miner.

It’s a curious fact, otherwise, that players don’t just extract the victory fanfare and the crawl and sit around like sots in an opium den, feeling victorious.  It’s a good feeling, but you can’t get it without doing the work.  The assets are like puppets; the game is a puppet show.  Without the meaning that the rest of the game experience gave to them, the assets elicit only a very slight response.  But that response that they do elicit is enough to start building upon.  A springy sound for a jump, a sad theme for failure, a mean looking mushroom: taken separately they’ll fall flat, but taken together they sparkle.

When a neophyte looks at an old game, or a tty roguelike, and calls the graphics ‘bad,’ old hands will sigh with exasperation.  The graphics look fine, they’ll explain.  They do their job.  It’s the game mechanics that matter.  This is to miss the point; the graphics (or the colorful letters) do their job not because the mechanics matter instead, but because mechanics are so powerful they can ascribe meaning even to a capital letter D.  And sometimes, of course, these more abstract forms let the mechanics do that job even better than more verisimilitudinous assets might do.

Where from here?

This is the intersection point that interests me most and that I will discuss most often here: How exactly do game mechanics cause assets to interact in ways that produce a sense of meaning, and how can that sense of meaning be exploited to produce known effects in the player?  The good news is that it is possible to answer, if haltingly, on the basis of established work.

There will be the question of how art assets evoke responses.  There will be the question of how game physics does its job (infinitely more interesting than it first seems!) and what makes it possible for players to project themselves into the game world.  There will be the question of how game mechanics interact in a purely abstract space, what game theory can tell us about the decisions players make, and how to design systems that let players extract.  And there will be the question of narrative, both within the context of written assets and scripted plots, and without them.

Game mechanics are a dancing skeleton, and game assets are a pile of flesh.  Stitch them together and your game will live.