Shipped!

Yesterday we finally delivered a product that's been in the works for nine months. I did conceptual work and production assistance; my wife did the rest. We named her Esther.

Boobs, Booty, and Booze: Adventures In Edit Distance

This week I got to thinking about word puzzles like this:

MOAT
____
____
____
____
SPRY

Fill in the four intermediate words. Each word is four letters long and differs by exactly one letter from the word above it and the word below it.

This is an example of a type of minimum edit distance. “Spry” is five steps away from “moat” when each step consists of changing a single letter.

How can puzzles like this be created? How can a puzzle's difficulty be evaluated? What does the space of possible puzzles look like?

To answer these questions, I went to wordlist.sourceforge.net and picked up the 12dicts package. This is a collection of word lists which have been compiled from twelve dictionaries. I chose the 2of12inf list, which contains any word listed in at least two of the twelve dictionaries, plus all of that word's inflections.

After filtering the list to words of a specific length the next step is to build an adjacency graph. I tried brute force first: a doubly-nested loop over all the words, testing each pair to see if they were adjacent. This takes a very long time. As an example, with the 2,546 four-letter words there are 3,242,331 pairs of words to consider.

Because the graph is pretty sparse there are much faster ways to build it. One way is to consider each letter position in turn, sorting the words into groups in which all the other letters are the same. All the words in a given group are neighbors of each other. Here's an implementation in Python:

adjacent_words = {}

for i in range(word_len):
    grouped_words = {}
    for word in words:
        group = word[:i] + word[i+1:]
        grouped_words.setdefault(group, []).append(word)

    for group_words in grouped_words.itervalues():
        for word1 in group_words:
            for word2 in group_words:
                if word1 != word2:
                    adjacent_words.setdefault(word1, set()).add(word2)

Once we have the graph structure in hand we can begin analyzing it in various ways. The simplest is to identify words that have no adjacencies. For instance, “sexy” and “odor” stand alone. These words can't be used in puzzles.

These “loner” words are a special case of identifying the connected components of the graph. These are the groups of words that are interconnected. A puzzle needs to have both of its endpoints in the same connected component or it won't be solvable. The basic algorithm for identifying connected components is to flood-fill from every word that hasn't already been visited, keeping track of all the words collected on each fill.

It turns out that, for lengths of three to six letters, most words belong to a single large connected component. As words get longer, they become less and less interconnected and the number of components increases rapidly.

Length	Words	Adjacencies	Loners	Groups	Biggest	Bridges
3	642	3840	11	1	631	9
4	2546	11476	79	19	2415	125
5	5122	12435	613	179	3935	547
6	8303	11218	2239	670	3943	752
7	11571	10039	4689	1173	2235	9
8	12687	5012	7052	1695	433	0
9	11768	2426	8135	1467	37	3
10	9896	1525	7388	1103	21	2
11	7362	905	5820	699	14	1
12	5067	500	4155	433	6	0

In the table above, Adjacencies are the number of edges in the graph. Loners counts connected components with only a single word. Groups counts components with two or more words. Biggest is the size of the largest group.

The final column, Bridges, counts edges which, if removed, break a component into two separate pieces. These represent the word transformations which you might expect to use frequently, since they are the only way to get from words on one side to words on the other side.

As it happens, though, words tend to be very well connected, and so there are never more than 20 or so words on one side of a bridge. Most of the time there is only one word on the other side of the bridge, i.e. the word is a dead-end with only one neighbor. An example of a dead-end is the word SPRY in the puzzle above. There is only one possible word to go above it in the puzzle (at least in my dictionary).

The diagram below shows several bridges in the five-letter word graph.



The edge between boozy and booze represents the most common sort of bridge, dividing one word from the rest. In comparison, cutting the edge between booby and bobby isolates nine words. Other bridges are the edge from hobby to hubby, and from tubby to tabby.

The algorithm for finding bridges took a while for me to understand. It's hinted at in the exercises of Introduction to Algorithms (Corman, Leiserson, Rivest) and is built on a depth-first traversal of the graph. I found pseudocode for it but it happens to be incorrect.

The gist of it is that, if you do a depth-first traversal, any edges you find that point at already-visited nodes are back edges: they close a loop, meaning that none of the edges on that loop can be bridges. Related to this, all bridge edges must be edges of the tree produced by the depth-first traversal. During the recursive descent of the depth-first traversal you can compute the highest (closest to root) position that each subtree points to. If a subtree does not point to a node outside of itself, then the edge to that subtree is a bridge.

Another metric for good words to know is the words with the most connections. For example, here are the top few words of length four, along with how many neighboring words each has:

ware: 25
pats: 24
wine: 24
bale: 23
bare: 23
care: 23
core: 23
mare: 23
mate: 23
paps: 23
tars: 23
bars: 22
caps: 22
cars: 22
done: 22
line: 22
lore: 22
male: 22
mats: 22
mine: 22
pale: 22
pare: 22
pits: 22
tons: 22
tots: 22

I'm out of time now, and haven't gotten to the questions of generating puzzles or evaluating their difficulty. Difficulty might be a function of how many choices you have at each step of the puzzle, combined with the relative frequency of each of the words in the English language (and hence, how likely you are to know them). Nevertheless, I feel I understand the word space a lot better, and have managed to generate some interesting puzzles along the way. I find that five steps is about the maximum that I can reasonably do. There are minimum paths that get up to 17 and higher steps, though.

Powered trajectory plot

Soonest-descent trajectory

I've spent a bit of time attempting to simplify the math for the soonest-descent trajectory angle. The basic equation relates the rocket angle (which is presumed to be held constant during the horizontal braking phase) to the difference between the height when horizontal braking finishes and the height at which vertical braking must start.

The equation ends up having the sine of the rocket angle in its denominators, which means it gets squirrelly near zero. However, as you can see in the last plot from two weeks ago, the curve does not look complicated at all, and it looks well-behaved at zero.

It turns out that the equation can be simplified down to this form:



If that was all we knew about the equation, we'd be stuck. However, it turns out that the constants b and c will always have opposite signs. Likewise d and e will have opposite signs. This means that their respective terms cancel each other out as the angle approaches zero. I figured this out by writing out the series expansions for the sines and cosines.

On a separate note, I put a very simple solver for the equation into my lander game and draw an arrow indicating the direction to fire the rocket for soonest descent. It turns out that, if horizontal braking finishes at the same instant that vertical braking starts (which is what the equation is aiming for), there's often quite a large instantaneous turn necessary. This is hard to fly. If I was intending to produce a flyable trajectory I'd need to add in sufficient time for the rocket to turn upright before commencing vertical braking.

Powered trajectory plot

The ballistic trajectory plot has turned out to be very useful. It shows you where the rocket will go if you don't do anything. I got to thinking that perhaps a similar plot for powered flight might be useful. The idea is to show where the rocket will go if you keep the rocket firing continuously but don't do any additional steering. (My rocket attitude is defined in screen space, which rotates to keep the rocket at the top of the screen, so technically the rocket does rotate when you don't do anything. This turned out to be the most useful frame of reference for controlling rocket direction.)

The powered trajectory plot allows you to swivel the rocket and experimentally find the horizontal braking trajectory that I was aiming for in the section above. Here's a sample:







I may cut off the trajectory plot when (local) horizontal velocity reaches zero. It would also be good to mark that point with a circle or something so it's clear. Next, I plan to compute the height at which vertical braking must start at the point where horizontal velocity reaches zero. This could be color-coded based on whether it's above or below the height where the rocket stop moving horizontally. Using this you can visually solve the equation to figure out how to fly an approach trajectory.

Super Mario Galaxy and Camera Control

Thanksgiving was a busy weekend, with lots of friends and family at our house. I played a bunch of Super Mario Galaxy, too. I like the bite-size gameplay pieces, and the live orchestral soundtrack.

On the downside, the camera is even crazier than in other third-person action games, which reduces the game's appeal for non-hardcore gamers. There are a couple of reasons for this. One is that there is almost no manual control over the camera. Sometimes you can press the D-pad to reorient the camera, but due to the controller geometry this is not something you can do easily. The other reason the camera is squirrelly is because the worlds have unusual geometries. As a result there is a lot of camera hinting (at my day job we call them camera volumes). This is where designers mark a region of space and give a preferred direction for the camera for that region. Due to the crazy gravity it's necessary to swing the camera direction wildly from region to region.

As anyone who's worked on 3D action games knows, there is a fundamental conflict between character control and camera control. You've got two basic choices for character control: character-relative and screen-relative. Character-relative is characterized by the Tomb Raider series (at least the early games; I'm not familiar with the more recent efforts). I call this “radio-control car” control because it has the familiar problem that if the character is moving toward the camera, you have to push right on the stick to get them to go left on-screen, and vice versa. As a result of this, virtually all third-person games (including Super Mario) use screen-relative control. The joystick deflection is projected to the screen and the character moves directly in that direction. Right is always right and left is always left.

Screen-relative control is great, until you need to rotate the camera. Suddenly the frame of reference that the player is using to control their character has shifted. If they're trying to run along a narrow beam, say, and you rotate the camera, suddenly their character will veer off and plunge to her death. If the player manually rotated the camera then they're expecting it and can adjust their movement to compensate, but if the game is controlling the camera the problem is much worse.

There are various tricks that we've tried to get around this. For instance, if the movement joystick is deflected and then the camera rotates, you can continue the character on their previous course until the player lets up on the joystick, after which any subsequent deflection will be projected to the current camera frame. This has mixed results, and probably works best when you're outright cutting the camera from one view to another.

Super Mario Galaxy has an additional problem with screen-relative control that most other games don't. I mentioned above that you project the joystick deflection onto the screen. There are various ways to do this, but usually they involve projecting the controller deflection onto a ground plane, so that pushing up on the stick moves the character further away on the ground (upstage), and pushing down moves the character nearer (downstage). In Mario, the player is sometimes running around on the ceiling, which introduces a new problem: should pushing up on the stick move Mario further away, or toward the top of the screen (which means running closer to the camera)?

In order to make screen-relative character movement work as well as possible, you basically want to make smooth, slow adjustments to the camera so the player has ample time to correct for the change in their character movement. On top of that you can add a manual control to snap the camera quickly to a better direction. That way, the player can stand still when they adjust the camera.

Unfortunately Super Mario Galaxy's environments don't lend themselves well to smooth camera adjustments. Gravity changes directions suddenly, or worlds will be tight and twisty, necessitating rapid camera movements to keep Mario in view. I'm having fun with the game, but it makes my wife really dizzy just to watch it.

Soonest-landing trajectory

In my rocket game, it is difficult to know when to begin a braking burn in order to land at a given target. I've been working on the math for a trajectory that lands at the nearest possible point. (To clarify: I want the nearest point that doesn't involve backtracking or waiting for the next orbit. Given unlimited fuel and time you can land anywhere.)

To start with I'm making some simplifying assumptions. These boil down to assuming you're close to the ground. Gravity is constant; it doesn't vary with position. The ground is a flat plane at y=0, and the gravity vector is pointed in the -y direction. With the constant-gravity assumption, the rocket's trajectory becomes a parabola and can be solved easily.

If the rocket starts out high enough, the trajectory is simple. The rocket is pointed completely sideways and fired until the horizontal velocity is zero. After that it is turned upright, falls a bit if necessary, and then fires vertically to brake to a soft landing.

A sample rocket trajectory of this type is plotted below. For this graph, the rocket's acceleration is 2 and its initial velocity is (4, 0). Gravity acceleration is -1. The graphs end when horizontal velocity reaches zero; they do not show the vertical braking component (if any).



Sometimes, though, canceling all horizontal velocity before addressing vertical velocity doesn't work because the rocket falls too far and hits the ground before it's done, or else there isn't enough altitude, given its vertical velocity, to complete the vertical braking. In these cases the rocket has to be tilted upward somewhat, diverting some acceleration toward staying above ground. We want to divert the minimum necessary, so as to extend the braking distance as little as possible.

In the example below, the rocket acceleration is still 2, but the initial velocity is increased to (6, 0). As a result, the rocket has to be tilted at an angle of 76.86 degrees from vertical in order to have space for the vertical descent:



Finally, sometimes the initial velocity is such that the rocket has to actually gain altitude in order to make a soft landing. Here, I've reduced the rocket's acceleration to 1.25, set the initial velocity to (6, -0.5), and put the initial rocket altitude at 1. The rocket angle is 25.84 degrees from vertical:



I've let the rocket graze the ground in the trajectory above. In reality you'd pick a safe minimum altitude and adjust the angle to keep it above that.

Thus, the rocket's trajectory consists of one or two pieces. If the horizontal velocity is nonzero, the rocket will execute a burn while tilted to the side by some amount. Once the horizontal velocity is zero, if there is remaining elevation, there will be a vertical burn to cancel that. (There may be a coasting period in between the two burns.) For simplicity I'm assuming that the rocket can change heading instantly. Time for turning could be added to the problem without too much trouble.

I've covered the coast-and-vertical-braking phase in a previous entry. The remaining problem is to find the angle for the first burn. The general approach is as follows:

For a given angle of the rocket, we can compute when it will cancel its horizontal velocity (divide horizontal velocity by horizontal acceleration). We plug this time into the equations for vertical motion to find out the rocket's elevation and vertical velocity at that time. This elevation and velocity can then be plugged into the equation for the altitude at which to begin vertical braking, developed in the above-mentioned blog entry. If the braking altitude is at or below us, we're good. If it's above us, we can't do it, and this angle is not usable.

Since we're comparing two altitudes, the natural thing to do is to make an equation which says that their difference equals zero. By solving this we get the minimum angle which will result in a successful landing. The minimum angle equals minimum distance traveled since we put as much thrust as possible toward horizontal braking.

Unfortunately since the variable we're solving for is encased in sines and cosines I don't know if there's an analytical way to solve for it. However, it should be easy to search for the value. Here's a sample plot illustrating the type of curve it is:



The curve above corresponds to the second case given earlier. It crosses the x axis at around 76.86 degrees.

The only remaining wrinkle (that I know of) is presented in the third case above. We can't ever let the rocket's elevation dip below zero. We need to determine when its vertical velocity reaches zero (this is a possible point of minimum altitude). If this time is earlier than the time for zero horizontal velocity (and greater than zero), then we need to check the rocket's elevation at that time. If it's less than zero (or whatever safe altitude we choose), then we need to search for a rocket angle closer to vertical that keeps the rocket above-ground.

I've been working this out in Excel; the next thing to do is to implement it in-game. There are a variety of ways it could be used: I could plot the earliest-landing point on the ground, or plot the trajectory to it, or have an attitude indicator showing which direction to burn. Once it's in I'll see how valid the flat-earth assumptions are. They do become more correct as the rocket approaches the ground so they may not be a problem.

Another thing this could be useful for is the beginning of a rocket AI. Computer-controlled rockets will probably have slightly different trajectory needs. They'll be wanting to land at a specific spot, rather than at the earliest possible spot. It shouldn't be too different, though.

Flying over eastern Washington

This weekend we visited my parents. My father took me up for a couple of hours in his little yellow Super Cub, which is always fun. We toured the Hanford site, the Coyote Ridge Corrections Center in Connell, Palouse Falls, Lower Monumental Dam, the Kahlotus Cemetery, and we did touch and gos at a couple of farm landing strips. There are always a lot of deer on the wheat fields, and we scared up a coyote yesterday as well.

I'd never been over Hanford before. It's a very interesting place. During World War 2 the US Department of Energy took over a vast swath of land next to the Columbia River in order to produce the plutonium for the nation's nuclear weapons. The river provided cooling water, and the barren land provided isolation.

There was a town named Hanford on the site, which was dismantled. You can still see the streets and the trees; the only walls still standing are the high school building.

The “B” reactor was the “world's first industrial-scale nuclear reactor.” Here's a picture:



About a dozen more reactors were built. In the early 1990s (I believe; I'm writing from memory) the government decided to shut it all down. Most of the reactors have been encased in concrete and steel sarcophagi; the B reactor has been left standing free due to sentimental reasons, but as you can see in the picture, all the ancillary buildings have been torn down.

I don't know the details off-hand, but I think the reactors were shut down fairly suddenly, and their fuel rods were dumped into the nearby processing ponds and tanks. They were left alone for a while and made a mess, which the Hanford site is now cleaning up at great expense.

The nuclear reactors from our nation's decommissioned subs are shipped up the river and placed in neat rows in a pit on the Hanford site:



I'm convinced that nuclear energy will be needed to help solve the coming energy shortages. Nuclear physics is pretty far removed from daily experience in most people's lives, and I think this, combined with its use in weapons, has given it an almost religious aura in many minds, occupying space next to Satan. What people don't realize is that there isn't necessarily a reason why nuclear power generation has to produce lots of radioactive waste. We just haven't been trying to make nuclear reactors any better. In particular, thorium-based reactors look promising. See this blog for details.

The prison in Connell was depressing. They have a medium-security facility already, but are building a huge expansion that looks (from the air) like it will have considerably more security, with a double fence enclosing a no-man's-land.

Forcing people who have done something wrong to only associate with other people like themselves seems like just about the stupidest idea possible, if “correction” is at all a goal. It's a hard problem, I'm sure; it just seems like there must be a better way.

The Kahlotus Cemetery is a small plot in a small town. It apparently contains quite a few graves of anonymous Chinese laborers who were killed in accidents while building the railroad.

James McColl and The Hussy's

James McColl is a Glasgow-based songwriter. He was a member of The Supernaturals in the 1990s, and now has a female-fronted band called The Hussy's (their spelling, not mine). Very catchy songs. My personal favorites are “Tiger” and “We Expected”.

The band is recording an album right now. They aren't signed to a label and it looks from their blog entries like they're undergoing some internal friction as a result. Here's hoping they weather their difficulties and get the album out.