Rocket sound

I've put together a very basic sound engine for my Lunar-lander-on-a-disc game, although it isn't in a released version of the game yet.

It's my first time using XAudio2; it went fairly painlessly. The only trouble I had was with my synchronization between the playback thread and the sound generation thread. Originally I was using an event but it was possible for the consumer to occasionally generate two events (meaning it had consumed two buffers) while the producer was busy. After this happened a couple of times (I am currently triple-buffering) the producer and consumer would wind up writing to and reading from the same buffer, with nasty-sounding results. I switched to a semaphore which keeps a count of how many unqueued buffers there are and it works fine now.

At the moment my sound engine is very, very low-level. I generate sound in small batches (17 ms at a time, one video frame's worth) and feed it to XAudio2 for playback. I'm not using any pre-recorded audio yet and I'm not really doing much signal processing yet either. Since I'm triple-buffering there are a couple frames of latency; I may shrink the buffer size to reduce that.

Now I'm trying to come up with a good, interesting rocket engine sound. All I have so far is some white noise that has been filtered with a 64-tap low-pass FIR filter. It's also shaped with a basic envelope for when the thruster is on or off.

I am currently generating the white noise at 44.1 KHz and filtering it down which is incredibly wasteful. I'm going to switch to synthesizing the noise at 11 KHz or lower and upsampling to the final rate since I am knocking out all the high frequencies anyway. I want to experiment with a dynamically-changing filter as well so I can get interesting transient effects at the start and finish of a rocket firing. I'd like to give the noise more of a 1/f or 1/f-squared shape as well since I think it might sound better (louder bass, softer treble). It's just kind of a generic hiss right now.

I've experimented in Audacity with phasing and it produces some really nice whooshy effects so I may try to come up with a way of relating phasing to what is going on; maybe do phasing based on the nozzle angle or something, so that as the nozzle sweeps back and forth you get some stereo effects.

The steering jets will get their own sound generators as well, and then it's on to impacts, weapons, and whatever else is needed.

Reviews: Sherman Alexie and Marjane Satrapi

Here in the Pacific Northwest it hasn't been long since the land changed hands. A lot of sad things happened and are still happening. I used to walk over to the site of the Whitman Mission on Saturday afternoons. Some people brought religion and farming and smallpox there and got killed in 1847 and it started a series of wars. I haven't ventured into any of the area's many reservations other than passing through on the highways, but when I fly over the Yakama reservation and see the trailer homes on the barren hills surrounded by their trash collections I imagine the sadness radiating upward. (Maybe my imagination's way off, though!)

The Absolutely True Diary of a Part-Time Indian is Sherman Alexie's semi-autobiographical novel about leaving the Spokane Indian Reservation, with illustrations by Ellen Forney. Arnold Spirit (“Junior”) is fourteen when he discovers his mother's name in his geometry textbook; the school hasn't acquired new books in the last 30 years. His teacher convinces him he has to leave the reservation to fulfill his potential. Junior transfers to Reardan High in a nearby white farm town, where he and the school's mascot are the only Indians. His tribe (apart from his family) take it as betrayal. When he makes the Reardan basketball team he finds himself up against his former best friend.

“Diary” is poetic, funny, sad, and raunchy. It ought to ring true with anyone who has had to leave home and family to get where they are.

Speaking of cultural displacement, the Pacific Northwest area now has a large Iranian immigrant population, including a bunch of Baha'i.

Persepolis: The Story of a Childhood



Marjane Satrapi was in grade school in Tehran when the Islamic revolution happened. Suddenly she was forced to wear a veil and attend segregated school. Then things got worse. Her parents eventually shipped her off to France when they realized that she wouldn't be able to have the life they wanted for her.

Once she found her feet in France, Satrapi produced this beautiful black-and-white graphic novel autobiography. She's done several more volumes and an animated film. It's been a while since I read this but I recommend it highly as well if you want to know more about what's happened in Iran.

Turrets Debut

Turrets make their first playable appearance in today's update to my lunar-lander-on-a-disc game, available on its website.

In addition the rocket has now been outfitted with machineries of aggression: Press right mouse button to fire projectiles out of the rocket's nose, and B to drop a bomb. Bombs start out with the same velocity as the rocket so you can use your ballistic trajectory plot to see where they will go. The nose gun has its own new trajectory plot.

Various other things have been tweaked. The landing gear now uses Chipmunk's damped-spring constraints instead of doing the spring and damping in the step itself. The damping is significantly different between the two approaches; I've tried to tune it back to be similar to before, but with less bounciness. I've also made some semi-successful attempts to tune the landing gear shock movement range to prevent inversion when you hit it sideways, but it's still doable.

The rocket doesn't activate its orientation thrusters when either of its feet are touching the ground unless the main thruster is firing. This makes landings a bit more difficult since you cannot cancel unwanted rotation quite as easily. I might try having the orientation thrusters automatically switch to rotation cancellation once you touch ground if this feels too hard.

I tried and removed missiles that accelerate continuously. They look cool but they make the game really easy, so I'm still thinking about them.

Another change is that there is now a two-planet progression. The first planet has fewer caves and fewer astronauts. The second planet is the classic one.

Work heats up

Work's getting more hectic. I am plodding forward on the lunar lander game nonetheless. I've spent a little bit of time working on coming up with distinct styles of randomly-generated planets in preparation for having a series of them in the game. The big failure there was an attempt to make a loose archipelago of small asteroids. I will need to attack it in a completely different way from how I was doing it. Planet generation needs to be spun off into its own thread so the game is always responsive.

Turrets are getting tuned up now too; hopefully they will make their debut soon. Making the game more challenging is a top priority. Last night I tried making turrets wait to shoot until they can hit the rocket at its closest point; it didn't feel very good. Not enough shooting. I could make them take that point in time and space out shots before and after it but I don't think it's worth the trouble. Next I tried taking the turrets off a synchronized shooting schedule. I'd had them synchronized because I thought it would provide a good rhythm to the game but due to the varying flight times of the shots it didn't, really. Now each turret shoots as soon as it has a shot and then runs its own recharge timer. This feels pretty good. I need to work on having the turrets turn to line up their shots, which will give them an initial reaction time. That may affect how their schedule operates.

The turrets' bullets now hit the rocket. They impart a fixed impulse and a fixed amount of damage. I may fudge the impulse so it applies less torque than is physically accurate. It's cool seeing the rocket get knocked about but if it tumbles too much it just gets annoying. The bullets make use of Chipmunk's sensor shapes; they don't participate in actual collision response, just report contacts. I handle the rest. (I'm thinking of the bullets as an energy ball right now.)

Next is to give the rocket a means of fighting back and disabling the turrets. I am unsure whether I will do a bomb-dropping weapon or a shooty weapon first. Bombs are interesting from a trajectory point of view (this game is all about trajectories) but if they allow you to take out turrets from outside their range it might not be very fun. Limited inventory is the typical way to solve this. Shooting will involve aiming distinct from the aiming used to fly so it'll be an interface problem. I will probably use the same aim and have different buttons for thrust vs. shoot, but the question is what to do with the rocket's auto-rotation. You don't necessarily want the rocket spinning around while you squeeze off a few shots during an approach. I could drop auto-rotation except while thrusting; may try that. Pedro found the auto-rotation confusing. On the other hand, that's giving up some control of the rocket.

Some other similar games like Gravitron 2 (available now on Steam and XBox Live; go get it) have direct rotation control which solves the aiming problem, but it creates problems when interacting with the landscape. Gravitron's landings and impacts feel very unsatisfying to me.

Lander Game WIP

Just posted a new version of my Lunar Lander game on its site.

There are only minor changes from the previous version. The braking line more accurately matches up to the powered trajectory plot, and there are indicator circles around the landing targets when they are very small.

There are some additional undocumented keys that will go away in the future, for things I am working on or experimenting with:

F1-F3 set the camera to one of three different modes (Auto, Manual, and Experimental).
F toggles a debug display of what the camera is trying to frame.
G toggles the ramp motors (ramps are not finished).
Home rescues the nearest guy instantly; useful for testing the camera framing and the end game.

Conversation starter #3

Sure-fire topics for easily striking up conversations with strangers:

With guys: Shaving
With new parents: Poop
With Pacific Northwesterners: Dietary restrictions

Approximately two-thirds of Seattle-area residents (a number I just made up) have some sort of dietary restriction, whether due to ideology, allergy, or both. If you're at a party just say "No thanks, I'm gluten-free right now" and you'll be off and talking with a bunch of the attendees. "Oh yeah, I have a gluten allergy too. These cookies are too good to pass up, though."

You can cross this with the new-parent poop topic: "Yeah, we're trying cutting lecithin and nuts from her diet; her poop was looking sort of greenish and she was howling at all hours of the night."

Thanks to preschool I now know that peanut allergies can be classified into airborne and contact variants. Parents take turns bringing snacks for the class and holy cow does that afford opportunities for dietary-restriction talk.

I have uncharitable theories about why this is. The Northwest is full of tech types who believe that religion is superstitious nonsense that is beneath them. Unfortunately for all of us, the universe is capricious and hard to understand, much less control. The urge to do both is within us all, though, and it finds its way out one way or another.

My related theory is that food allergies is a religion that does not set off the "no other gods before me" alarm in Judaism/Christianity/Islam. Thus it is a good mix-in religion. The Northwest is full of people who have been transplanted from all over the world. A mix-in religion is a great way to bond people of different faiths together.

Minecraft, Layton Reviews

Took a week of vacation at home; sigh, yes, a “staycation.” Amongst other things I managed to play a few computer games:

Minecraft

I've spent a ton of time playing this game. Rock, Paper, Shotgun ran a play diary which convinced me it was worth shelling out for in its alpha state. I have not been disappointed.

Here's a fan-made trailer for the game:



Minecraft (in survival mode) drops you into an infinite, randomly-generated world. Your immediate goal is to survive the nights, when various monsters come out. Once you have your basic safety assured, though, you are free to explore, dig mines for rare materials, and construct grandiose architecture. The game's in alpha and has been built by one man so far. Due to its increasing popularity he is hiring help though.

Professor Layton and the Unwound Future

Just finished this third game in the Layton series of puzzle games. It's as charming as ever; the production levels are steadily rising as the series progresses, with more voice acting and more beautiful animated movies than I remember in the previous installments.

A Layton game strings together a big collection of brain teasers with a barely-related story in which Professor Layton and his boy sidekick Luke solve mysteries. In this case they have received a message from someone claiming to be Luke from ten years in the future, requesting aid. Layton's lost love also comes into the tale; she was a scientist who died in a mysterious laboratory explosion ten years prior.

If you get stuck you can spend hint coins for increasingly specific tips. If you've played the previous Laytons, I think they've dialed back the puzzle difficulty quite a bit here. I don't mind too much; I was fairly frustrated in a few places in the first game.

A couple other games I've been playing but haven't finished:

Zak and Wiki: Quest for Barbaro's Treasure

A point-and-click adventure game for the Wii platform. Kind of fun. I'm playing through it a little bit at a time with my four-year-old.

Dragon Quest IX: Sentinels of the Starry Skies

I am generally pretty burnt out on Japanese role-playing games. This one seems like it's quite charming, despite having a very, very traditional battle system. I'm trying to save my JRPG stamina for the Ghibli-co-produced ones coming out next year so I don't know if I will finish this one.

Brake Line

This weekend was busy with hiking on Cougar Mountain, attending the Puyallup State Fair (quite an Internet-savvy fair; see the URL), and having company over. My friend Pedro tried out the lunar-lander-on-a-disc game I've been gradually making. He figured out the trajectory plots quickly, but found the rocket's auto-rotation confusing. I need to get more data points on that. The rest of his complaints were things I know about and plan to fix: landings need to be more emphatic, with less bouncing and floating around. Landing targets need better visibility from orbit.

Up until now I've had three trajectory plots: the ballistic trajectory, which is where you go under gravity's influence alone; the powered trajectory, which shows where you go if you thrust continuously in your current aim direction; and a braking trajectory which shows the quickest way to reach zero velocity. This last one I have been unsatisfied with. It gives a rough idea of the turnaround point for deceleration, but I want something that gives more information. Here's what I've got so far:



The red line is the brake line. It's a closed curve made out of the points of minimum velocity for all thrust directions. In other words, if you thrust continuously in a particular direction, when your velocity reaches a minimum it will be somewhere on that curve. The powered trajectory plot's inflection point sweeps around the curve as you change its heading. (It doesn't quite touch in the picture above; this is because for my initial prototype I'm assuming a constant gravity vector for the brake line plot.) The intensity scales with the difference between the rocket's current velocity and the velocity at each point on the curve.

The goal is to kind of show you what the powered trajectory will do as you sweep it around in a full circle, without you having to do that. It is pretty much as I'd envisioned it, but I'm still learning to fly with it so I'm not sure yet about whether I like it or not. I've posted a version to the game's site if you want to try it out and weigh in with an opinion. Remember that the gravity part doesn't match up, though, so it is not yet good enough for precise maneuvering. (There's also the issue that this represents the rocket's center of mass; the actual rocket occupies space around that so you have to take that into account. I might eventually try a Minkowski sum of the rocket's bounding circle with the curve if I'm feeling ambitious.)

Ramps and Rescuee Running

Work on my lunar-lander-on-a-disc game has been slow but steady. None of the pieces I've been working on are anywhere close to done. Here's a clip demonstrating where things are at:



The rocket has a couple of gangplank ramps that can be folded down. I'm still working on the physics of them. The ramps have a combination of several different constraints in the Chipmunk physics engine: They have a pin joint and a rotational limiter for the hinge, and then some sort of motor for opening and closing. I experimented with a rotational motor and a winch type of thing attached to the tip of the ramp. Ultimately the ramp hinge and motor need to be able to fail, too, if they're pushed too hard.

The little people on the surface now move toward the rocket when it's on the ground. “Toward” is a tricky concept. I thought I might be able to get away with local optimization (head in the direction on the ground that moves you toward the rocket) but quickly discovered places where they get stuck: mostly on slopes with a bit of concavity pointing toward the rocket.

I think what I will end up doing is identifying some “closest” point on the terrain and then determine the short way around the planet to reach it for each rescuee. I still need to limit their movement so they can't go around underhangs. Eventually I want them to run to avoid being directly under the rocket, and to approach the expected landing site even before the rocket has landed. Lots and lots of little details like moving more slowly on slopes, and waving only when they see you but think you might not see them, or something like that.

The main worry I have at the moment is that sitting around waiting for guys to board the rocket will be boring. Rescuing ten people before this change took me about five minutes, so about 30 seconds apiece. It looks like that time could easily double. That's not a problem so long as the player feels engaged. With the flight portion I didn't feel engaged until I decoupled the attitude control from the thrust direction so it was easier for the player to keep the rocket under thrust the whole flight.

I'm thinking about having some Starship Troopers-style spider enemies that pursue the guys on the ground. If you had to supply suppressing fire while they ran to the ship it might keep things interesting.

I also envision (although I don't know when I would implement it) having little scenarios associated with each rescue. Like you might have already-rescued guys come down the gangplank and wave people in, or maybe there'd be someone who needs carrying so they would have to go out and help with that. Little bits of pantomimed story that would spark the imagination.

The current version of the game is available on its website. The ramps go up and down with the G key (I guess I was thinking of landing gear).

A blast from the past

A friend and I made a CGI script ages ago (1996, probably) to generate random names for fantasy role-playing games. We used the basic templates (e.g. Blank of Blank) but the word lists eventually got a bit silly. Have a chuckle:

RPG Game Name Generator

Bathroom Guy

My quest to avoid making an art pipeline continues. I couldn't sleep last night so I replaced the landing targets with little guys that wave their arms.



These are made out of five capsules (which can have different radii at the two endpoints) and one circle (for the head). I'm still working out the relative scale of the guys to the rocket.

Next up is to make ramps that fold down from the rocket, and have the guys move aboard. They probably won't animate much yet (if any) while they move.

A Couple of YA Novels

I like young adult novels because they tend to be short. There's been a discussion recently amongst independent game developers about how long people expect games to be relative to their price. One of the mistaken points I've seen made a few times is that it's only games consumers that judge their media by its length. I'm pretty sure there's a pressure in the adult fantasy/sci-fi genre for novels to be bloated, poorly edited messes. A book needs a map in the front, “Part One of the Demon Kingdoms Saga” on the back cover, and seven or eight hundred pages of typo-laden prose in between. Fortunately you can go to the young adult field and find tightly-plotted, well-characterized books that won't waste your time. Here are two:

Ship Breaker by Paolo Bacigalupi. An oil-less near future on the flooded Mississippi coast. Nailer, a child laborer (the eponymous ship breaker) falls in with a shipwrecked princess on the run. The characters are vividly drawn, the drama is intense, and the plot comes together well. Nailer's abusive father is a particularly strong villain. Not a cheery book but the atmosphere is thick and novel. Impossible to put down once started. Bacigalupi has also written a (much longer) adult novel in similar vein, The Windup Girl.

Leviathan by Scott Westerfeld. Westerfeld, already a prolific and accomplished YA writer, tries his hand at this newfangled steampunk thing. It works out pretty well, and has a sequel coming out in a couple of months. It's an alternate history version of World War I where the British have got genetic engineering down pat (with which they create the requisite steampunk dirigibles) and the Germans have gigantic walking fighting machines (because really, what universe should not have these?) Deryn, a young girl, hides her sex to enlist on a dirigible, shipwrecks and falls in with a prince on the run. Similarly un-put-downable.

Relative neighborhood graph

I've been trying out various things to improve camera control, but nothing good has turned up yet.



Currently the camera frames the player's rocket and the nearest objective. This can introduce a big discontinuity when a new objective becomes the nearest. The camera controller smooths its motion so it's not horrible but I think I'd like it to anticipate the transfer better. I've been trying out things in a testbed; if you'd like to try it you can get it here. It's a Windows application. Click or drag the mouse to move around; press the space bar to generate a new point set.

A screenshot appears above. The light-colored circle represents the current framing algorithm. The larger circle is an alternate method. What I really want is for it to interpolate between those two solutions so it frames things tighter when it's close to only one target, and then expand so there is a smooth transfer to the next objective.

I've also learned about some cool graphs. The application displays the relative neighborhood graph of the points. I'm not sure if it'll be useful here but I threw it in to see what it was like. It's a subset of the Delaunay triangulation that only contains an edge if there is no third point that is closer to both of that edge's endpoints.

Long, long ago I made a prototype for a game that was ultimately canceled. The idea for the game was that you'd have a map full of towns and villages and you'd help one or the other of a trio of warring factions to conquer all the territory. You'd do this in typical third-person action game format. (It was basically Dynasty Warriors Empires, but about five or six years earlier.) In my prototype I sprinkled towns randomly on the map and then made a Delaunay triangulation to determine which towns were neighbors; the mission generator would use this to generate sortie missions from one to another across the current borders. The problem with the Delaunay triangulation is that you have all these really long edges connecting vertices around the outer perimeter, which wasn't at all what I wanted. This relative neighborhood graph turns out to be exactly what I wanted back then.

Turret aiming

Progress has been slow. I've been working on making the turrets aim:



After experimenting with projectiles that are influenced by gravity I'm now experimenting with ones that aren't. The goal of the turret is to find a spot along the rocket's projected trajectory where a bullet would arrive at the same time as the rocket. The turrets in the picture are assuming that the rocket undergoes constant acceleration. They use the sum of the rocket's current thrust acceleration vector and the gravity vector at the midpoint between the rocket and the turret. This gets them pretty close in the picture shown (the endpoints of the white lines) but often it's a lot worse. There are two reasons for this: the main one is that the gravity vector's strength changes with altitude and its direction changes as you go around the planet. A second inaccuracy is that when the player is thrusting without steering, the thrust vector is automatically rotated slightly as the rocket goes around the planet. (This essentially makes the thrust direction view-relative, since the view rotates in this way.)

I'm currently replumbing things so that the turrets can examine the plotted rocket trajectory instead. It is built using forward integration (albeit with a much larger time step than the game update) so it predicts where the rocket will go almost exactly. This should allow them to aim very accurately. In the past when I've worked on aimy-shooty things I've found that it's best to make them perfectly accurate and then work from there toward something that is inaccurate in a fun way.

The exact role of the turrets is not yet clear. It's no fun when you get shot with no time to react, so they need to be ineffective at close range. Probably they will avoid shooting at all at very close range (due to fear of unwanted splash damage, let's say). Making them turn slowly, and need to sync up to tracking the rocket's trajectory before firing, should also help.

I think I will plot the intercepts of all flying projectiles with your projected trajectory, although I don't yet know exactly what that ought to look like. Ideally it would give you an idea of the best evasive directions. It's possible that having all these trajectory plots will rob the game of any required skill, but my hope is that it will instead allow players to play a much denser game. I've noticed with the trajectory plots that I fly more aggressively than I ever would without them, and I feel much more in control as a result. Without plots I fly defensively and do a lot of waiting.

Ultimately you'd be able to destroy turrets to make things easier for yourself. (There'd probably be a bombing trajectory plot as well!) I've also been thinking about having turrets drop in from space over the course of the mission; maybe key the drops to astronaut pickups so that the difficulty ratchets up as you go.

Physics library updates, continued

When I started using the Chipmunk physics simulation library I did what most programmers do when confronted with unfamiliar code: I rewrote it. It was a good way to learn the ins and outs of the code, and it did integrate better with my own code, but ultimately it meant that I wasn't benefiting from other peoples' continued work on the library. The whole point of libraries is to save work.

I've fixed up the current version of the library to work with my compiler (MS Visual C++) again. Scott Lembcke has accepted the patch into the main repository, so hopefully I can save someone else some work. I've also adapted my lunar lander program to work with the updated stock library, so now I should be able to get upgrades much more easily.

The end result, of course, is that the game looks and behaves exactly the same. I have turrets in an initial state; I will now dive in and work on getting them up to fully operational status.

Physics library updates

For my lunar-lander-on-a-disc program I need some intersection-testing functions that were added to the Chipmunk Physics library I'm roughly based on. Since I translated the library from C99 to C++, though, I would need to translate the new code as well. This is a maintenance pain, so this weekend I spent some time trying unsuccessfully to get the stock library into a state in which I could use it.

I like Chipmunk; it's very understandably written and sensibly designed. I'm sure its author Scott Lembcke is reading this. (Hi Scott!) The key problem seems to be that the library is written in C99, a newer dialect of C which is poorly supported by Microsoft's C compiler. Since C99 moves C toward C++ I can get by with relatively small modifications if I compile the C code as if it were C++. Still, since the main library development isn't using my compiler I can expect to have to do this regularly.

As a result I've been examining Box2D some more. It builds easily out of the box, and it's written in C++ so it should mesh better with my project. It has a different approach to collision shapes; I'd need to break down the rocket hull into a set of convex shapes, but that wouldn't be hard. The terrain might be a bit more work. Box2D doesn't support line segments as a collision primitive (although there is contributed code to do so), so I'd probably take the triangulation and merge triangles into polygons up to the 8-vertex limit.

I've got various directions I can go and it's hard to decide how much work I should spend on this. I could patch up my library and continue working on gameplay; that might be the most prudent. Ultimately I want to produce a Flash version of the game, and I think Box2D might give me some help there.

What I'm Reading

I went camping this weekend, so no programming, alas. When I wasn't herding children I worked on my reading research instead.

ThiefRL, when I eventually return to it, will be getting a layer of Chinoiserie. Here's what I've been reading in preparation:

• China's Old Dwellings (Ronald Knapp)
• Chinese Imperial City Planning (Nancy Shatzman Steinhardt)
• Strange Tales from a Chinese Studio (Pu Songling, translated by John Minford)

My brother also picked me up some architecture books on his last trip to Shanghai; they're entirely in Chinese though so I can't give the titles.

Fox spirits seem to be similar to the fairies you find in British Isles folklore. Ghosts, on the other hand, are odd; I haven't really gotten a good handle on how they work. I just finished reading a story where a ghost ended up marrying a guy and bearing him a son, so it's not clear exactly how being dead slowed her down. I've read two stories so far where a guy has a three-way with a fox spirit and a ghost; that strikes me as a bit unrealistic, especially if said guy is a shy student with no obvious redeeming qualities.

Apparently the Strange Tales were heavily commented on by “scholars” of the succeeding centuries. The translator has mostly omitted these, but left them in on one story to give a sense of what they're like. The depth of the commentary on that story was similar to what you'd find in the comments section on an Internet article. I kept expecting to see “Firsties!” or “This. So hard.”

Turrets: First Steps

I've started on implementing some turrets to shoot at the player's rocket.



This is a chance to use my aiming math (here's another explanation from Scott Lembcke with graphs instead of equations). So far I have the turrets aiming without regard for acceleration of any kind. I'm searching for a combination of parameters that will make the player react while still leaving them enough time to do so. I think I will want to make the turrets smart enough to take into account the rocket's acceleration; otherwise it's too easy to dodge them by just flying through with your engine blazing. Maybe there will be different kinds of turrets with different target-leading algorithms; if they're clearly visually different it could be interesting. One would aim to hit the rocket without considering velocity or acceleration; one would aim considering only velocity; and one would aim considering both velocity and acceleration.

Having some additional projectiles is making me realize that my gravity is not very strong. The bullets don't arc much. I don't remember but I think I originally sized the gravity so it would be similar to Earth gravity based on the rough size of the rocket. Just looking at how long it takes to fall its own height when starting from rest (at sea level). After I have the turrets basically working I think I'll do a round of gravity strength experiments. Of course the rocket engine will have to be scaled accordingly; it needs to be able to deliver greater acceleration than gravity at “sea level” (where the gravity is strongest). Scaling gravity up might speed up the gameplay which could be interesting. I have it in my mind to add on-foot movement (a la Star Guard) and wheeled vehicle movement, so the gravity will need to feel OK for those too.

The projectiles need a lot of extra work. They need to go away upon intersection with the rocket, and they need to deliver an impulse and some damage. At the moment they are regular colliding bodies, so they do deliver some impulse and damage but I'd like it to be arbitrarily tunable. I think I will have the bullets “fade out” over time so they deliver less damage as they age, before disappearing entirely.

The turrets need to have their range of motion clamped so they can't shoot into the ground.

I'm weighing whether it's worth it to have my own version of the physics library (I translated it from C to C++) and keep porting vendor drops from the original, or whether I should just write the necessary shims to connect up the C library to my vector class and what-not so I can use it directly. I'm sort of inclining toward the latter. I'm also looking at Box2D again, although I haven't quite figured out how I would translate my collision shapes to their model. They have a maximum of eight vertices per convex shape, I think, so I'd need to make a bunch of shapes to represent my curved surfaces (my game's all about curved surfaces).

Auto-zoom camera

I've posted a new version of my lunar-lander-on-a-disc game to its little website. The addition of an auto-zooming camera makes the game much more playable most of the time. Changes:

• Auto-zooming camera (can be toggled off with Space)
• Improved landing gear graphics
• Tuned landing gear physics
• Rocket has to be touching ground with both feet to count as landed
• Display elapsed time after completing mission

Teal-’n’-Orange!

The landing gear has been adjusted so it can't invert itself on hard impacts. I still need to transmit shock through to the hull when you reach the compression limit on the landing gear; a current “exploit” is that you can survive an impact of any magnitude so long as you can absorb it completely without letting the hull touch the ground.

Line drawing is very slow on some graphics drivers, so I'm gradually replacing my uses of that. The landing gear was one; the trajectory plots are the other.

The big change this week is the camera. Most of the time it works well enough that you can complete the game without needing to manually adjust it. The algorithm right now is very simple: it frames the rocket and the nearest objective.

The biggest place where this falls down is when you need to do some close maneuvering and the nearest objective is far away. It also doesn't work if the player has something else in mind besides going to the nearest objective. I've been trying to think of better metrics but haven't hit on anything yet. I think the camera needs may change once opposing force is added, so I will probably do that next. I'll start with some simple turrets and give the rocket the ability to shoot back.

Lunar Lander: Now with Fun

What a difference a couple of tweaks make!

In the comments to my last post I mentioned that the game just wasn't that fun because the player spent a fair amount of time waiting for the rocket to follow its ballistic trajectory to get somewhere. Even with time acceleration this lacked pizazz.

Before introducing the Chipmunk physics engine, the rocket was represented by a disc for collision purposes and its heading was controlled directly with the mouse. When I switched to a physically simulated rocket I got rid of direct heading control; instead the mouse set a target heading, which the rocket would steer toward using attitude adjustment jets. This allowed ground impacts to spin the rocket around, which looks cool. Unfortunately it also introduced a lag in changing the rocket's trajectory, which slowed gameplay down.

I am now trying a hybrid: I've decoupled heading control from the main thruster. The main thruster always invisibly thrusts directly in the target heading direction, while the rocket attempts to steer toward that target heading over time. This gives a good balance between the visual effects of the rocket steering or bumping into things and the increased control of direct thruster orientation. In my opinion it feels much better; as a player I feel like I can play right up to the edge of my reaction time instead of waiting around for the rocket. Here's a sample landing; note that I am thrusting nearly the entire time:



I have also reinstated a couple more trajectory plots from the original prototype, which together also greatly improve the fun. In the video above you can see three lines emanating from the rocket. The dim blue line (which has existed in all versions) is the ballistic trajectory. If you let the rocket coast without thrusting this is the path it will follow. The bright blue line is the powered trajectory. If you hold down the thruster button without steering the mouse, this is the path the rocket will follow. The red line is the braking trajectory: if you were to always thrust in the direction opposite your velocity this is the path the rocket would follow.

The braking and powered trajectories together allow you to fly with the thruster on at all times. You can see where you're going with the powered trajectory, and the braking trajectory lets you know when it's time to reverse direction and slow down. Flying with thrusters on all the time makes the game move more quickly but more importantly keeps the player engaged and feeling in control. If you need a breather you can always fly ballistically so it has a good skill-development path, I think.

The rocket landing gear has been improved a bit as well. It has shock absorbers on both leg struts now (the lower strut used to be a rigid swing-arm). This makes landing in a concavity much smoother, since that tends to pinch the feet together horizontally.

I've put another release out so you can try it if you'd like.

The trajectory plots are still works-in-progress. Besides drawing nice-looking ribbons, I plan to replace the braking trajectory with a simple icon at its terminus, and I want to toggle the highlight between the powered and ballistic trajectories depending on whether the rocket is thrusting or or not. I've also considered trying to fold the braking info into the other trajectory plots by using different colors for different segments of the trajectory. The things I've tried in that line so far haven't been useful, though.

As currently configured, rendezvous with the mothership is not too hard but it could probably stand to have some sort of heads-up display help. I haven't figured out what that might be yet. I'm sort of waiting until I get the docking mechanism (and position on the mothership) finalized more.

If you try out the prototype and have interface improvement ideas I'd love to hear them. Some sort of automated camera framing is top of my list: it's very hard to fly and manage the camera at the same time.

Mothership, version 1

There's now a mothership in my lunar-lander-on-a-disc game:



At the moment it just orbits around the planet. The idea is that after landing at all the ground targets the player has to rendezvous with the mothership to end the level.

The mothershp rendezvous necessitates additional camera work and probably also some work on the trajectory plots, so that is what I'll be doing next.

Games I'm Playing

The runup to E3 at work has been busy. I've been getting back to putting in an hour a night on my lunar-lander-on-a-disc, though. Not a whole lot of progress to report. There are now landing targets distributed over the planet surface which detect when the rocket lands close to them.



I recently purchased a PlayStation 3 and have been catching up with some of the games on that platform.



Uncharted 2 is very, very pretty. I find the relentless shooting a bit monotonous, but they have done an excellent job of mixing storytelling and gameplay.



I'm replaying Super Mario Galaxy with my four-year-old. It's reasonably fun.



PixelJunk Shooter is a solid little game that I'd recommend to almost anyone. Its looks belie its technical sophistication. It's one of two games I played recently to compare and contrast with my lunar lander project. Shooter sets a high bar and is making me rethink some things. For instance, they use a grappling hook to rescue astronauts, instead of landing next to them as is traditional in this type of game. The result is that the game flow moves much more quickly.



My wife's been playing Picross 3D obsessively since it came out. I finally got some time with it last night; it is really, really fun. Picross 3D uses a rather heavy-handed tutorial system to teach you the game; after playing Everett Kaser's logic games, which always stay out of your way but provide excellent hinting, it's a bit hard to take. Otherwise it's great.



Gravity Crash is the other game I played for inspiration in my lunar lander game. Unfortunately I just didn't find this one very fun at all. It feels like a total ripoff of Gravitron 2, and one of the problems they share is a tendency to add energy to the ship when colliding with the terrain. The result is that one collision can quickly spiral into being completely out of control, bouncing this way and that until the ship explodes. It suffers especially when compared directly with PixelJunk Shooter.



Flower is a nice, short little game. My four-year-old can play it fairly well. I do wish there was an option to steer with an analog stick instead of with accelerometers. About half the time you feel like the wind soaring over a field of flowers (as intended), and it is exhilarating and beautiful. The other half of the time you feel like you're trying to turn a semi truck around in an alley.

Simplified, triangulated terrain

I've continued to work on the terrain for my lunar-lander-on-a-disc game. The polygons are now simplified, which cuts out a lot of little bits that result from evaluating on a grid. It also lets me dial up the grid resolution so things are smoother where they need to be. After that I dropped in my polygon triangulation code. Right now the terrain clocks in at around 4000 triangles. This is how it looks with edges shown (click to enlarge):



Now I am working on offsetting the polygons by the radius of the rocket, in order to produce new polygons representing the accessible surface (and thus possible landing sites).



The next step is to intersect the new polygons (both with each other and with themselves), which should produce new interior polygons that can be stripped by examining their signed area.

Reading Outcast SFX files

I've been replaying Outcast for the umpteenth time, courtesy of Good Old Games' rerelease and still enjoy it tremendously. (Here are some of my notes about why Outcast is cool.)

In a previous post I outlined how to read the contents of the game's archive files. Here I'll describe how the audio files are stored.

Audio files have .sfx extensions and there are vast numbers of them. They are compressed using the GSM 06.10 cell phone audio compression standard. All the audio files have a 20-byte header followed by a sequence of 33-byte frames of GSM data. Since this is a cell-phone audio standard, each frame can be decoded independently.

All the headers start with the same 12 bytes: 32 54 76 98 01 00 00 00 00 00 80 3F. After this comes two 4-byte little-endian numbers: the number of bytes of data following the header, which should be divisible by 33; and the sample rate (22050 samples per second in the file I'm looking at).

Each 33-byte frame decodes to 160 16-bit samples, so the compressed data rate is around 4.5 KB per second. I used code by Jutta Degener and Carsten Bormann to decode the frames.

Here's a random snip of dialogue from the game (ilott_found_naarn_g_7-9). Ilott has just learned of his brother's death at the hands of Kroax:

I have not had a chance to play with it, but I suspect that they get some of their “alien voice” sound by monkeying with the parameters of the linear predictive coding used to compress the audio, since it is essentially modeling a vocal tract.

Note: Another person requested the command-line tool for converting the SFX files to WAV format. I dusted it off, updated the project files to the latest version of Visual Studio, and put it up on Github: https://github.com/mcneja/sfx2wav. It's just a thin wrapper around the library mentioned above and converts all of the files in a given directory, writing the output files to a specified output directory.

Hole extraction

I've returned to work on my lunar lander program by spending some time on the planet generation code. It now collects closed polygons and then throws out any that have negative area, so there are no longer any inaccessible interior regions:



I lost a fair amount of code in doing this. There is no longer a BSP representation; I'll need to do that in a different way if I end up needing it. There's also not a triangulation yet either, but I have code lying around that I should be able to plug in for that.

The current top priority is coming up with landing targets. I've been trying to think of a good way to identify accessible landing targets on a random terrain like this. Ideally it would be able to find "interesting" places to land.

Reading Outcast PAK files

Good Old Games just released Outcast, one of my favorite games of the late 1990s. They're selling it for $6 USD. In honor of the occasion I've dug up some of my file-format hacking notes. I'm indebted to Dmitry Andreev for much of this info.

Outcast's archive files are stored in the relatively-obscure PKWARE Data Compression Library format, a variant of Lempel-Ziv-Huffman dictionary compression with static tables for the Huffman codes. The archive file contains an uncompressed directory followed by all the files, individually compressed. Multi-byte values are stored little-endian (least significant byte first).

All Outcast files start with a 2-byte magic number: (71 6e). For .pak files this is followed by ten more magic bytes: (0 0 d3 d4 7d 9 1 0 0 0). Next is a 4-byte value indicating whether the files in the archive are compressed or not. A value of 1 means they are compressed; a value of 3 means they are not.

Next up is a 4-byte value containing the number of files in the archive. Following it comes that many variable-length directory entries. Each directory entry starts with a variable-length string (a 4-byte count followed by that many bytes; no null terminators), which is followed by the 4-byte offset from the start of the archive to the file's contents; the 4-byte compressed file size; and the 4-byte uncompressed file size.

After that is the data for the individual files. Each file is compressed separately. I used code by Mark Adler to do the decompression.

Art

We played pin-the-tail-on-the-bunny at my daughter's birthday party a few months back. I drew the playing area with Sharpie on butcher paper (letters indicate where the kids put their cotton balls):



I've had acrylic paints lying around for ages and finally tried them out today:



I really have no idea what I'm doing yet with the paints. Mysteries I need to solve:

• What's the best way to mix paint? I used my brush but it seems like there must be a better way.
• How can you get a good gradient? There's the problem of mixing a consistent set of colors and then the problem of blending on the canvas.
• How do you paint sharp edges? I originally intended for the thing that became the sun to have a sharp edge but it looked horrible so I changed tacks.

I do like that they don't stink, clean up easily, and dry quickly.

Spiral Galaxy Hack

The Pinwheel Galaxy

As a sidetrack from my sidetrack I've been reading about galaxy formation (among other things). Galaxies look like a drain swirling, but when you think about it that can't be how they move or else the arms would wind tighter and tighter until they disappeared. Likewise they can't move like a pinwheel since that would require the outer tips to move much, much faster than the inner core, in direct opposition to how gravitational orbits work.

On the Wikipedia page about density wave theory I found this diagram:



The idea is that star orbits are elliptical but they are not oriented in all directions with equal probability. Instead, the orbit's direction correlates with its size. At this point I took the ball and ran my own direction with it, so abandon all hope of physical plausibility, ye who read below.

If stars were influenced primarily by the massive black hole at the center of the galaxy, and not so much by their neighbors, then they'd follow roughly elliptical orbits. This is most likely wrong, but since I had already written a solar-system orrery program with this assumption, that's what I used.

If stars followed elliptical orbits, the ellipses would not be centered as in the diagram above; instead they'd have one focus at the center of the galaxy. The stars would spend more time at the far end of the ellipse than at the near end. If the far ends of the orbits were arranged in a spiral, you'd have a spiral region of high star density, like this:



I don't know what force would cause star orbits to align in this way. If it was a symmetric process you might end up with a separate set of stars following orbits aligned 180 degrees opposite, which would produce a two-arm galaxy:



I took my solar system orrery and replaced the planets and asteroids with random stars whose orbital parameters followed these ad hoc rules:

• Pick a random eccentricity. I'm using a Guassian-ish distribution around 0.35, plus or minus 0.1.
• Pick a random orbit size. I'm just picking a uniform number over a range of sizes, which is almost certainly unrealistic.
• Pick a random initial position in orbit as a fraction of total orbit duration. This should be uniform although you can get some cool effects when it isn't.
• Compute orbit orientation as a linear function of orbit size.
• Compute a star color as a linear function of orbit size as well.
• I'm not tilting orbits out of plane at all right now.

To plot the stars the orbital elements have to be converted to instantaneous positions, which takes a little bit of Newton-Raphson iteration. I used David Vallado's Fundamentals of Astrodynamics and Applications for the algorithm.



Here it is in motion; you can see how the stars come and go across the spiral arms but they are denser there. I don't know if real galaxies move at all like this, though:

If you'd like to scrub time back and forth and examine individual star orbits, here is the Windows program I wrote to generate the movie:

• Galaxy.zip

Use the mouse wheel to zoom and the A key to toggle animation. You can also adjust the clock by dragging individual stars around their orbits with the mouse.

Network evolution algorithms

Disparate fields that all involve growing networks:

• Generating Surface Crack Patterns
• Modeling and Visualization of Leaf Venation Patterns
• Co-evolution of density and topology in a simple model of city formation
• Rapidly Exploring Random Trees

My previous posts on randomly-exploring random trees: here and here.

How often do you see a white sports car?

And, The A to Z of Awesomeness.

Transcendence 1.0

Transcendence reached version 1.0 this past week, so I have been playing some of that. George Moromisato has been developing it in his spare time for the past fifteen years. Transcendence takes the basic flying and shooting action gameplay of the Escape Velocity series and enfolds it in a game that is otherwise heavily indebted to Nethack.

After picking a trader/fighter/balanced ship, you are off on a quest to reach the galactic core or some such. You get there by warping through a series of semi-random solar systems.

Each system has jump gates connecting it to the next and previous systems; exactly like the up/down stairs in Nethack. Instead of rooms forming a dungeon you've got planets which orbit around the central star(s). At the planets you'll find friendly bases with shops and quests, or hostile bases which will deploy a bevy of fighters against you. Looting wreckage supplies you with things to use or sell. There are space analogues for magic potions and scrolls of enchantment. You have a deity to whom you can make sacrifices and from whom you can request aid. You've got tinker bases that will transmute junk into items according to their own recipes. There is a gladiatorial arena for earning money by fighting other spaceships. You can even acquire robotic sidekick ships. And behind it all is the ticking clock of your fuel consumption: run out and it's game over.

Unlike Nethack the universe is not wholly hostile. Trading ships ply the major routes within each solar system, and the friendly bases may have fighters that will launch to defend their allies.

The game's interface has some holes that I wish would be patched up. It's cumbersome to examine your ship's current configuration for comparison while shopping, for instance. When you are submitting items to the tinkers for transmutation it would be nice if the list would only show things they accept; nicer still to see recipes for things so you know what to be on the lookout for when you're collecting loot. Quest management could be improved as well; there isn't currently any way (that I've found) to remind yourself of the details about what you're supposed to be doing.

I wish there were more ability to communicate with other ships in the area. Being able to respond to distress calls or request help would do a lot to make you feel more connected to the world. Also there seem to be quite a few space bases that don't really do anything which just makes the universe seem more boring. I haven't figured out what the pubs and nightclubs are for yet, and since I've never been able to figure it out I've stopped looking into them. If they ever do become useful I won't know, and that's just bad design.

On balance, though, the game does do a fairly good job of encouraging you to play just a little bit more to see what new things you will discover. It's free so give it a try if you are at all a fan of space games or roguelikes.

Grrrr...

Grrrr... not much to report.

I've wondered in the past if Haskell might make a good language for writing data compilers: something to take source art and turn it into something ready to be linked into the game. My thinking was that it would allow for concise construction of parsers, good error messages when input is ill-formed, and make it easy to morph the data through multiple representations in the compile process.

I needed some vector art for my lunar lander program and thought I'd just take SVG output from Inkscape and convert it to a triangle mesh for inclusion in my game. Seems simple enough. I don't know yet what the best way to represent graph structures like triangle meshes will be in Haskell, but I can probably dodge that for now.

Step 1: Install Haskell. There is an installer called the Haskell Platform which is supposed to be a one-step install for everything you need. On Windows it really hasn't been well thought out though. It installs to the Program Files (x86) directory by default, but Microsoft really wants this directory to be read-only apart from installation, which seems to break the Haskell package-manager's assumptions about what it can do. If you try to install to a different directory it doesn't respect that. Some things go to the directory you've specified but most things land back in Program Files (x86). Very unprofessional!

Step 2: Parse SVG. SVG is an XML format. There are five or six different XML parsers in Haskell with no clear indication of which one's “the one you should be using”. I have a book that uses HaXml so I look it up. It doesn't appear to be installed, even though it's part of the standard Haskell libraries. I run the cabal package manager to install it. Can't do it unless I elevate privileges to Administrator first. OK, that works. But on the web I see there's another one called the Haskell XML Toolkit; it claims to be better than HaXml. So I try installing it. It fails trying to install the curl library. After searching around on the web I find a thread from November 2008 describing what's wrong: the curl library installer depends on running a shell script of some sort, and on having the curl C library installed! So you need Cygwin installed. Once Cygwin is required you've lost me; sorry!

I'll try this out in Python next. I have a feeling it will be ridiculously easy.

GDC 2010

The Game Developer Conference came and went in a hurry. I was severely disappointed to find that Emily Short's talk was on Tuesday, before I arrived. Likewise there was a physics panel on Tuesday or Wednesday featuring folks like Erin Catto and Erwin Coumans who I would have liked to meet.

The one talk I attended that really enthused me was a half-hour introduction to R-Trees, an adaptation of B-Trees to spatial indexing. Sebastian Sylvan's main point was that our current situation, with processor speeds greatly outstripping memory access speeds (particularly random access due to cache misses) is exactly analogous to the old days of database programming where disk access was very slow. Many algorithms (like B-Trees) that were developed to mitigate disk-access problems are useful in avoiding cache misses.

There wasn't time to do much networking at the conference but I did manage to meet Andy Korth and Scott Lembcke, the duo forming Howling Moon Software and the creators of the Chipmunk 2D dynamics library that I use in my lunar-lander program. They just announced a space game under development titled “Solaro”. I'm looking forward to seeing that one.

Landing gear continued

I'll be at the Game Developers Conference this year; if anyone's interested in meeting up drop me a line: mcneja at gmail.

Is there anything so lovely or useful as a critically damped spring?

The basic differential equation:



This is saying that the acceleration (the second derivative) is a weighted sum of the velocity (first derivative) and position (x), measured relative to the desired velocity and position. The weights are expressed in terms of a constant omega which indicates the spring's response speed: higher omega means faster movement. The proportions of the weights are chosen to achieve critical damping: the spring returns to its rest position as rapidly as possible without overshooting.

To solve this differential equation we form and solve a characteristic equation:



Being critically damped makes the characteristic equation work out very simply. This then allows us to construct the general solution for position as a function of time:



The constants A and B are unknowns which we determine via supplying additional constraints on the problem, which will yield a particular solution for our problem. The first constraint I'll impose is that the spring is at rest position at time zero; the idea is that the landing gear is not stretched or compressed at the instant it touches the ground:



To solve for the constant B I'll supply a second constraint, which is that the spring is being compressed with speed v0 at time zero. This is the impact velocity. To use this we'll need to differentiate our general solution:



Plugging v0 into this yields the answer for B:



Now we have an equation for the particular solution of position as a function of time:



I have to get off to work now but suffice it to say there's a lot more tedious math where this came from. The next step is to replace omega as an input constant with something more useful: the maximum acceleration we want for the given impact velocity. To find this we have to check the extrema of the acceleration function, as well as the acceleration at time zero. Turns out time zero's acceleration is bigger than any other acceleration by a factor of about 40.

After that I've been working on adding gravity's constant acceleration into the equation which messes things up a fair amount, although the math's not hard.

Landing gear

I've been working through the math for landing leg shock absorbers. Given the worst-case situation that it must handle (initial contact velocity, maximum acceleration, and surface gravity), the program should determine the dimensions of the legs and the constants for the springs and damping. I'm midway through though so I don't have anything to show.

One thing's surprised me so far, if I've done the math right. If the shock absorber is a critically-damped spring, the deceleration is maximum at the moment of first contact and tails off rapidly thereafter. With an undamped spring the maximum deceleration occurs at the point of maximum compression; an underdamped shock absorber would presumably fall between these two extremes. It seems to me that the ideal landing gear would just decelerate at a constant rate, to maximize the amount of deceleration relative to the length of the shock absorber, but I don't know that any landing gear actually works that way.

Combating comment spam

The quantity of comment spam has been steadily increasing. I'm now disallowing anonymous comments; we'll see if that changes things appreciably.

Hull damage

Continuing to work on my lunar-lander-on-a-disc, I finally got a basic damage model implemented. After the physics system has solved for a set of impulses to satisfy contact constraints, any impulses against the hull that exceed a threshold are scaled and applied as damage. There isn't yet any visible damage; it's just hit points. But the introduction of mortality takes this a step toward being a game.

I'm still trying to come to a big-picture understanding of damage, though. It seems like, in an inelastic collision, kinetic energy is being converted to heat (or some other deformation). I think a more accurate model might decide (based on the properties of the colliders) how to divide up the energy to be absorbed by each; and that the damage would be proportional to the energy absorbed. If this is the case it seems like the damage would be proportional to the square of the relative velocity, where in my current model it's a linear relationship.

Also this week I have begun to make a parametric hull design to allow for a range of rocket shapes and sizes. Time for a product plug:



This is the Lift-Off Rocket Playset and children love it. Buy one, invite them over, and watch the fights!

A few things you can't see in the photo: The nose has a hatch that opens to reveal seats for the two astronauts. The bed is a Murphy bed; it folds up to reveal the toilet. Beside the toilet is a roll of toilet paper and some reading material. In the back is a kitchenette with microwave and coffee maker. The top and bottom doors are designed to break away under stress to avoid permanent damage. Oh, and it has a button you can press to get noise and flashing lights out of the thrusters. This toy is an almost ideal marriage of stuff boys and girls like, which means none of them will want to be left out of the struggle over it. Which is where the breakaway doors come into their own!

Here's my rough likeness:



I got myself in over my head math-wise with the parametric model and ended up backing out slightly; you don't specify the height exactly from nose to base, instead specifying it from the top to bottom of the middle section before it's beveled by the round nose and the cropped bottom.