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.