Monthly Archives: August 2013

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.

Overlays

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.

Timing

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.