RRT With Obstacles

Last week I tried making a rapidly-exploring random tree, or RRT. Instead of starting from a single point as is typical in motion planning, I started from an entire coastline. This produced something vaguely resembling a drainage network of streams and rivers.

Because the tree grows toward each random point from the closest river or shore, it's extremely unlikely that you'd ever replicate South America, with most of the water draining to one side. This can be remedied by adding obstacles (click to enlarge):



Obstacles are defined as line segments which block line of sight between each randomly generated point and the tree. They manually specify some of the ridges on the terrain. Note that rivers will tend to cut quite close to the ends of the obstacles, so the obstacles don't represent just the highest parts of the ridges.

With my brute-force algorithm (coded in a couple of hours) the addition of obstacles slowed it down by a large amount that scales directly with the number of obstacle line segments. As the shape of the obstacles gets more mazelike, the algorithm will require drastically more iterations to fill in the tree, too, since it won't get line of sight to the inner portions for quite some time.

I also did some experiments with RRTs on a grid, where tree edges are all oriented horizontally or vertically. It turns out to bear a strong resemblance to maze-generation algorithms in that context.

Rapidly-Exploring Random Trees

Time to play a bit. I just learned about rapidly-exploring random trees while reading about motion planning. They look kind of like drainage networks so I had to try them out. I created a disc (a perfectly round island, if you will) and then generated a tree in the interior. Here are a couple of example results (click to enlarge):





The gist of the algorithm is that you generate a sequence of random points distributed uniformly over the interior. For each point, find the closest point on the tree and create a new branch from there, headed toward the random query point. You don't go all the way to the query point, though; just a small step. The net result of this is that the tree tends to head toward open areas.

I've shaded the tree edges as a function of how many other edges empty into them, so you can see the big rivers are darker than their tributaries.

Eye Contact

The November 10 issue of the New Yorker has an article about Kent Kiehl, a scientist who uses functional MRI to study the brains of psychopaths. He's got a trailer MRI machine set up at a New Mexico prison and has scanned the brains of most of its inmates. There are debates about the fruitfulness of this approach, but I am glad the problem is being studied by actually looking at real psychopaths. Dr. Kiehl says that whenever he goes to conferences the first thing his colleagues ask is “What are they like?” which seems a shame.

The assumption underlying this research is that there are physical brain differences in psychopaths, a tangible perversity. I was struck by a comment from Robert Hare, Dr. Kiehl's thesis professor, regarding psychopaths he's interviewed:

“It's their eyes that are the most remarkable feature,” he said. “How they drill into you.”

I wonder if the intense eye contact is an emotional version of lip-reading? Lacking emotional empathy or something like that, the psychopath must closely examine his conversation partner's face for clues as to what they are feeling, much like a poker player searching for tells. Perhaps the superficial charm that many psychopaths exhibit is a result of the heightened attention they are forced to devote to interpersonal interaction.

---

On a completely unrelated note, my latest bad movie premise: an Indian casino has been inadvertently constructed on the site of an ancient Indian burial ground.

---

Seen on the marquee of an indoor shooting range in Kent: “Come on in. You know you want to!”

Multiple predefined levels

I'm averaging about one hour a week of work on my little game project. This week, I added support for multiple predefined maps. I'm thinking it is time to create a new test map that can help me answer questions about size: whether the game will primarily center around guarded compounds or if there are interesting things that would include surrounding city as well.

The prospect of creating a larger map using a text editor is daunting so I'm considering whether it might make sense to have a simple in-game editor. That is a pretty big change to how things work, though.

Other things I've done this week:

I bought Gothic from Good Old Games and have played it a little bit. I had played its sequel Gothic 2 several times, including with its Night of the Raven expansion and I have always wanted to try the first game in the series. It's been an interesting experience because Gothic 2 included Gothic's map as a subset of its world (albeit with some major changes due to war) so I am finding that I already roughly know my way around.

The Good Old Games folks are doing a great thing by fixing up old games so they'll run on modern computers and selling them without DRM. I had a terrible time trying to get my original Gothic 2 discs to run on my recent computer due to the execrable (StarForce or SecuROM, I forget which) DRM they employed. After getting the runaround from Gothic's publisher and some ineffectual assistance from the DRM company I ended up just buying the rerelease of the game, which (as is common) omitted the DRM. I suppose I'm sending the wrong message to the publisher by re-buying the game. (I tried looking for no-CD cracks first, believe me.) If I could personally deliver a good stiff whack with a stick I would.

I picked up John Christopher's Tripod series of young-adult sci-fi books at the library and have started reading those. They got made into a BBC show which I haven't seen. The setting is Europe a few hundred years after Earth has been enslaved by alien overlords, who use mild neurological pacification to maintain the remaining humans in a feudal state. Humans are fitted with “caps” at puberty; most become contributing members of society. In a small percentage of people the procedure fails, producing mentally ill vagrants. It sounds darker in my telling than it seems to me as I read it.

I played a bit more World of Goo but am stuck on a level in the Fall world now. This game is charming but it's not really my type, I think. Each level seems to consist mainly of finding the one trick that is necessary to complete the level, so it is more of a “get into the designer's head” than an avenue for creativity. My two-year-old likes watching me play, which makes my wife uneasy (there is a macabre undercurrent in the game which mostly goes over toddlers' heads).

Finally, I have been reading up on motion planning. I found a good survey paper here and an excellent textbook here.

Guard Turfs

I've hacked together the beginnings of guard turf. The idea of turf is to have some areas of the map in which the player can move unmolested so long as he doesn't do anything suspicious. Here's a quick visualization of the turfs (click to enlarge):



Different guards have different turfs: the bank guards care about the cyan building in the upper right, for instance. This is likely overkill; I will probably be able to cut it down to a guarded/unguarded designation, or break it down by a handful of factions.

As an initial test I just made it so that guards can't see you if they are patrolling and you're not in their turf. This is not a terribly satisfactory solution, though.

I also did a quick experiment in loiter detection. I thought it might be interesting if the street guards would harass you if they thought you were hanging around somewhere you ought to be moving along. When I mentioned this to my wife she laughed and said that the Supreme Court has had its hands full slapping down anti-loitering legislation. Loiter detection in real life is tricky at best, often amounting to an excuse for police to arrest black men driving with white women and that sort of thing. Apparently Mayor Daley of Chicago has tried several times to pass laws prohibiting gang members from loitering on the streets.

Fortunately I don't care if my guards are just or not, so long as they act believably. I have tried summing the player's movements over a window of a few turns and if the resulting vector falls below a threshold he's considered to be loitering. I think this might work out OK.

I'm still pondering whether the addition of turfs is a good design decision. One goal is to add relatively safe areas from which to reconnoiter the guarded areas, looking for good ways in. Another goal is to have accessible public areas. I plan to do some experiments with overheard speech soon, and would like to have safe areas in which to listen. Also I'd like to have non-guard people walking the streets. These goals could also be met to some extent by providing appropriate cover or darkness within guarded territory, but I think the turfs will provide an additional layer of control and believability.

Bump To Use

Continuing last week's thought, I tried out bump-to-use and really like it.

Formerly when you would attempt to move into a usable object (a door, lamp, or switch, say), you'd get a message saying something like “Press Ctrl-left to open the door.” Thus, you'd learn what something was by bumping it, then use a Ctrl-dir key chord to actually use it.

Following a tester suggestion, I tried switching it so that you don't have to press Ctrl-dir to use most things. Instead you just bump them directly and they get used.

This makes the game feel a lot more fluid, which is good. Most usable objects are fairly self-explanatory, and the ones that aren't were not getting well explained under the old system, anyway. The big puzzle for me is how to allow players to shut doors. At the moment this is accomplished by aiming a Ctrl-dir combo at an open door while standing next to it.

At the moment I have status-bar messages that indicate what happened when you use something. This is all right but I think I can pare it down to be even less obtrusive. I'm going to try allocating a field on the status bar for indicating the “current thing.” Normally this will be the terrain underneath the player, but when you use something or bump something it will describe that thing instead, so after opening a door it would say door on the status bar.

I also spent several hours writing some dialog for the captain of the protagonist's ship, which in the test level serves as home base. The ship captain is my first attempt at a friendly character. By having him guard his ship I hoped to introduce the player to the mechanics of guards in a safe environment. He says most of the same things as regular guards, until he recognizes his passenger. “Using” him triggers a series of lines. (Our hero is currently the classic silent player-character whose reticence provokes monologues from everyone he meets.)

I've been mulling over whether the game design has room for sidekicks; the ship captain is kind of a prototype. They have the potential to add a lot more interest to the story since they'd each have their own agendas. However, it's important that they not take away any of the fun of the game. None of them should steal any loot that you can, for instance.

Miscellaneous interface tests

Another update for my turn-based, ASCII rendition of Thief.

I've decided to shelve random level construction for a bit and return to AI and gameplay development, where things were going well. To warm up I tried a couple of things I've been intending to for a long time. Neither worked out, but I'm glad to have seen them on-screen.

Status bar terrain description

At the moment the game requires a Ctrl-plus-direction key chord to use objects in the environment. If the player bumps into one of these objects using normal movement, the game gives them a prompt along the lines of “Press Ctrl-Up to open the door.”

This works pretty well for unobtrusively teaching the player what all the usable things are. Unfortunately it doesn't provide any way to teach the player about the terrain types under their feet.

As an experiment I added a phrase to the status bar that described the currently-occupied square. Something like “On a creaky floorboard&rdquo or “Under a table.” It feels a bit too overbearing to me, though, so I'm trying to think of alternatives.

Prohibit movement while speech is on-screen

The other problem I tried to solve is that the player can be holding down a movement key and miss the speech balloons flashing by when other characters talk. I did a quick experiment to require the player to press Space to clear the speech balloons before moving. That turns out to be incredibly onerous. If you aren't interested in what people are saying you should be able to just go about your business.

I think the correct solution for missed messages will be undo/redo. This will allow players to back up time a few moves to see dialog they missed. I've started looking at applications' undo/redo interfaces.

The Microsoft apps all seem to use Ctrl-Z and Ctrl-Y for undo and redo. I'm not sure how Ctrl-Y got chosen; it is not reachable with the same hand that's doing the undo operations. Perhaps undo predated redo by a few years and all the nearby keys were already taken by that time.

Maya (a 3D modeling package I use at work) uses Ctrl-Z and Shift-Z for undo/redo. This allow for easy motion in both directions. I think I have also used an application that paired Ctrl-Z with Ctrl-Shift-Z.

In addition to undo/redo I think I'm going to want a hotkey for jumping straight to the end of the timeline. I could envision Ctrl-Shift-Y under the Microsoft scheme, or perhaps Ctrl-Shift-Z under the Maya scheme.

Another key pair might be Space/Backspace, since they are natural antitheses. Space already does duty for clearing status-bar messages and speech balloons, though (as in most other Roguelikes), so that might not work. Backspace/Enter could work, too, but both of these ideas are pretty nonstandard.

Other Ideas

One of my testing complaints was that it was a bit cumbersome to have to use Ctrl-dir to open doors. I've been thinking about ways I could turn using into normal movement. For the most part it would just work. The interface would be slightly more risky for a couple of reasons: the player has to try an unfamiliar object to see what it does, rather than getting a bump message; and cruising along by holding down a key could result in using something when the player collided with it.

I'm not too worried about the learning aspect; I can put up a message on the status bar following the use saying what the player just did. A certain amount of experimentation is fun.

The accidental uses due to holding down keys could be reduced by not allowing a held key to use; you'd have to let up on the key and press it again.

The other thing I haven't figured out with a non-Ctrl-based use is how to close open doors. Open doors currently have no physical presence so they can't be bumped. In that way they are unique so they have always troubled me.

Open doors could be made into a physical presence. They would sit off to one side of the open doorway; stepping on one would close it. I think I'll try this out to see how it feels.