Weaver Modulation

...about sins of omission there is one particularly painful lack of beauty,
Namely, it isn't as though it had been a riotous red letter day or night every time you neglected to do your duty;
You didn't get a wicked forbidden thrill
Every time you let a policy lapse or forgot to pay a bill;
You didn't slap the lads in the tavern on the back and loudly cry Whee,
Let's all fail to write just one more letter before we go home, and this round of unwritten letters is on me.

(From Portrait of the Artist as a Prematurely Old Man by Ogden Nash)

The frenzied finish to inFamous has subsided and I've just finished up a week of vacation. A large part of the week was spent atoning for sins of omission: visiting the dentist, renewing my driver's license, returning clothes to stores, mopping floors, and so forth. I have been reading and thinking, too, though, and finally put fingers to keyboard in the last couple of days.

The earpiece is one of videogames' hoariest clichés. Generally there's a sexy-voiced female operative on the other end dispensing instruction, exposition, and exhortation. Infamous has it; Sly Cooper has it in nerdy-turtle form. In Psi Ops we mixed things up by using telepathy (can't tell you how many times I had to listen to what's-her-name say “I'm speaking to you in your mind, via telepathy”), but generally it's assumed to be some sort of magic radio that never fails unless the story requires it. Anyone who has used a cell phone knows this is a major simplification.

One of my childhood memories is of listening to amateur radio in the HF band. Radios in this band use single-sideband amplitude modulation because of its efficient use of both power and bandwidth. As you tune across a signal with an SSB radio you get some really interesting effects on the voice. Here's an example of a sexy-voiced female spy transmitting her report as a series of spoken numbers:

(Borrowed from this site. You may need to use Firefox or Chrome to see the embedded players; I had a lot of trouble even getting them to appear in Firefox. If they don't, you can always click on the links to the MP3 files and play them yourself.)

A lot of what you hear in this recording is noise, but the reason for the odd effects on the voices is that AM radio consists fundamentally of frequency shifting. A signal in the audible range of frequencies (20-2000 Hz, say) is shifted up by a whole lot (e.g. to 2 MHz) and then broadcast using radio waves. After receiving the signal, it is shifted back down to audible range to drive a speaker. If it isn't upshifted and downshifted by the same amount all the harmonics in the signal become misaligned with respect to each other. Human voices and our understanding of them are all about harmonics (which is why linear predictive coding works so well) so they sound pretty strange when they are out of alignment.

I'm interested in simulating what this round-trip transmission/reception does to an audio signal in the presence of noise and/or mistuning. The core part is the frequency shifting. I found an article that describes beautifully how to do digital frequency shifting using Weaver modulation. Since it is nicely illustrated and I'm still learning this stuff I refer you to it.

My three-year-old daughter supplies the audio clip for today's demonstration. (I've awakened a monster; ever since, it's been a never-ending litany of “Can we sit in front of Mommy's computer and say ‘Weaver modulation’ again?” Stage Dad, here I come!) First the original, and then a series of shifts upward and downward from there.

Original:

Here are the results of shifting this audio by a variety of frequency offsets:

Shifted down 10000 Hz:
Shifted down 5000 Hz:
Shifted down 1000 Hz:
Shifted down 500 Hz:
Shifted down 100 Hz:
Shifted down 50 Hz:
Unshifted:
Shifted up 50 Hz:
Shifted up 100 Hz:
Shifted up 500 Hz:
Shifted up 1000 Hz:
Shifted up 5000 Hz:
Shifted up 10000 Hz:
Shifted up 22050 Hz:

The recording was made using the Zoom H2 Handy Recorder, which lives up the “handy recorder” part of its name. It was a birthday gift from my wife, who researched the various options and found the one that delivers the best bang for the buck. It is also popular with music teachers in eastern Washington (my mother tells me) and my brother said he wished he'd bought one instead of whatever he did buy for field-recording classroom instruction. Highly recommended!

SpaceRL released

I knew ahead of time that it would be next to impossible for me to enter this year's Seven-Day Roguelike Challenge due to my work schedule. When the call for dates went out at the beginning of the year I decided to start immediately on something small in the hopes of having it ready to release to coincide with the Challenge deadline, since deadlines are good to have. The core idea was to try and approximate zero-gravity movement in a turn-based, square-based game, as I outlined in my previous post.

Starting with the engine for ThiefRL, my unreleased stealth-based Roguelike (eh; might as well release it now), I stripped out the sound propagation, guard speech, and various other things. I kept the line-of-sight code, the pathfinding, the map structure, and the basics of the monster type. I added in a random map generator from another experiment I'd done in villa creation, and I created the basic inertia-based movement scheme.

And that is pretty much where it is now.

I spent a huge amount of time thinking about how to do predictable rigid-body dynamics so that you could push collections of objects around (or be pushed by them). In the end I had to abandon all of that in order to get something done. Currently, only you and the monsters move, and the monsters don't obey the zero-gravity movement rules.

I also spent a huge amount of time on the dungeon (a.k.a. starship wreck) generator. I'm happy with the overall shape of the spaceships. Here are some examples (click to enlarge):



The generator starts with a target number of rooms and a horizontal or vertical symmetry axis. It accretes rooms next to existing rooms. Each placed room adds its four neighbor positions (if they're not already in use) to a set of candidate positions. The next position to use is drawn randomly from that set. Thus empty positions become more likely to be used as they acquire more used neighbor positions.



Once the core room layout is created, the walls are randomly offset by up to half a room in either direction. A fixup process ensures that rooms don't overlap by picking horizontal or vertical at each intersection and forcing the walls to align in that dimension at that intersection.



Next is the crazy part. Originally I allowed doors only between rooms that were adjacent in the original grid. However, the wall-shifting can create new adjacencies. At considerable pain I created a system to identify all adjacencies and form a graph of possible room connections (doors). Then I create a simply-connected graph by randomly adding edges between unconnected components until the entire spacecraft is connected. This ensures that you can always get everywhere. After that I add a random fraction of the remaining unused edges, as well as some doors to the outside.



I got partway through cleaning up the door placement. You may notice in the maps above that some doors are placed symmetrically and others aren't. I'd like to have the underlying door structure be symmetric, and then block or destroy doors to satisfy the level connectivity requirements, which would be determined by a system that would take into account locked doors and key placement; that sort of thing. You want to make the player work a bit to get through the level.

I also got partway into implementing air ducts: an alternate movement layer which only the monsters can use. The idea is that they can't open or close the doors, so if you close the doors they will backtrack to the nearest duct and get through to you that way. I think it shows promise but I just didn't get it done in time.

I've got loads of additional feature ideas which I'd like to put in when I get more time.

---

The ThiefRL game I linked to above is an entirely different experience. It features a single hand-authored map at the moment, which I have been using to test out gameplay features. You can't kill anything in that game, although you do play a threat to society. I'd estimate that it's got 30 minutes to a couple of hours of gameplay in it right now, and is quite a bit more fun (I think) than SpaceRL.

Square-based, turn-based rigid-body dynamics

The day job's been very busy lately. I'm finishing up a game (Infamous) which I've been working on for something like three and a half years. I've always wanted to be on a game project from start to finish, and I'm almost there. It's sobering to think of my life in chunks of this length, though. I have two daughters I didn't at the start. How many more of these do I have left in my career? etc. It's night and I'm maudlin.

At home I've been thinking, fairly fruitlessly, about how to put simple rigid-body dynamics into a Roguelike framework. This was the inspiration:



In this scene from Tobias Buckell's Caribbean-flavored space opera, the heroes propel themselves across the zero-gravity core of a space colony by pumping lead into their pursuers with a giant Gatling gun.



The other inspiration would be Space Hulk, I suppose, although I've never played it.

First, I repurposed an earlier attempt to randomly generate villas to create derelict starcraft:



I did some work on opening and closing doors using bumping alone and finally came up with something I like. Bumping a door head-on opens it; the problem was always to come up with a reasonable interface for closing the door again. What I have now is that if the door is open and you stand in front of it and diagonally bump the door frame on either side it will close again.

My other current Roguelike-in-progress uses a Ctrl-dir key chord to close doors. In this game I'm devoting the Ctrl-dir key chords to shooting; the idea is that when you're shooting you keep moving in whatever direction you were moving the turn before (floating in zero gravity). Also, you cannot change your movement direction unless you're adjacent to a wall or other mass.

I mocked up movement for the player character and it went pretty well. I threw in some really basic monsters, and as soon as I gave them enough hit points that they took several turns to kill it got interesting. You'd want to lead them to a straight corridor, kick off, and glide backward while shooting.

The “physics” seems like it has potential for some interesting gameplay. For instance there might be a monster that can't be killed, only stunned. Permanently neutralizing it would involve pushing it to the nearest hatch and committing it to the void. Or you could have crate-stacking, but IN SPACE...

I thought it ought not to be too hard to adapt a rigid-body physics system to a turn-based, square-based regime but so far it has stymied me.

The important thing, I think, is for it to be predictable to the player. Positions are constrained to squares, obviously, and I want to prohibit multiple objects in the same square. I've decided to constrain velocities to be integral in each component as well. Furthermore I'm trying to constrain velocities to be -1, 0, or 1 in each dimension. Velocities of 2 or more might be okay for some things, but experimentation is necessary.

I've tried out solving collisions and contacts using a fairly standard impulse-based solver, in floating-point, and then rounding velocities back to integers. It doesn't yield good predictability though and falls down on some fairly simple cases, like a line of crates hitting another line of crates. With the right numbers of crates you can get it so that the momentum hasn't been totally propagated throughout the stack and some crates round to zero velocity and others not, which means they move on top of each other.

Contact is a tricky concept in the grid-based environment too. Objects that are diagonally adjacent are contacting if they're moving toward each other, but not if they are moving past each other. A conventional “relative velocity dotted with contact normal” approach can't distinguish these.

You can also have objects that will move into the same square on the next turn if left alone but which aren't actually adjacent at the start of the time interval. What ought to happen in these situations?





I'm now working out some problems on paper in terms of generating sets of contact constraints and solving them as a system of linear equations. I think it might be possible to do that with rational arithmetic so that everything comes out perfectly. There are some cases I'm not sure about though.

If you have any good ideas about doing “physics” in a turn-based, square-based game, I'd love to hear them. I feel like I'm spinning my wheels on this right now.

(An academic paper on this might be titled Rigid-body dynamics with large-scale time and space discretization.)

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.