Spirit Engine 2 (demo)

I have been too busy keeping the household running this week to get any programming done.



I did manage to play the demo for The Spirit Engine 2, a largely-solo development effort. Mark Pay did the coding, design, and art, with Josh Whelchel composing three hours of music for the game. The game is a side-scrolling role-playing game set in a fairly novel universe (to my eyes, anyway) reminiscent of some of Miyazaki's movies. The production values are excellent. The writing could stand tightening in places but is nonetheless quite readable. Having not played the entire game I can't judge the overarching storylines although there appears to be some fairly heavy foreshadowing. If the mysterious overlords who manage the affairs of men don't turn out to be evil I will be stupefied with astonishment.

My main gripe is that the battle system is not explained in enough detail. It involves building chains of actions for each party member (prior to battle) and then selecting chains of actions dynamically. I don't have a good handle on how to do this, though; the tutorial didn't go into it very well. The interface for building action chains could stand to be improved as well; you can't examine the details of actions while you are assembling chains.

Another problem is that the keyboard interface seems to be an afterthought. I played mostly with the keyboard and it took me a while to figure out that I could open treasure chests, for instance, since they have to be clicked with the mouse. This wasn't explained.

Basically, the game could stand to have more focus-testing on new users to ensure that the ramp-up is smooth. Otherwise, it appears that once you are familiar with the game mechanics it will be a delightful experience.

Preparing to Triangulate

When I started this blog I had a list of interesting bits of code to share. I've gotten through most of them but have held back polygon triangulation until now. It's my personal symbol of jumping the shark; once I've presented polygon triangulation I've got nothing of importance left to say. It's time to get it out of the way, though, so over the long weekend I found the code and have been dusting it off as well as rereading the sources I used when I wrote it.

The polygon triangulation problem is as follows. We have a polygon outline, which may be concave and may include holes or interior lines. It may also consist of several disjoint polygons. It does not have intersecting lines. For each edge in the outline we know whether each side is inside or outside the polygon. In addition we may have individual vertices inside the polygon which we wish to be incorporated into the triangulation.

The goal is to produce a good triangulation of the polygonal interior without introducing any new vertices. Something like this:



Polygon triangulation turns out to be useful in a lot of different situations once you've got good robust code for doing it. For instance, in last week's post on river generation I used a disc because it's easy to generate uniform random points inside the disc. It would be nice to be able to have a more interesting coastline, though. With triangulation, I can take the coast outline, turn it into a triangle mesh, and then generate a uniform random point by picking a triangle at random (weighted by area) and then a random point within that triangle.

Here are the primary sources I used in writing my triangulator:

• David Mount
• Jonathan Shewchuk

Hopefully I'll have finished the code cleanup next week and can get started on the presentation of the triangulation algorithm.

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.