Path Symmetry

The past couple of weeks I've been wrestling with video editing in order to put together a very short video for my father's memorial service. The state of video codecs and containers (in terms of what can go in what, and which platforms support which) is truly awful. Go software patents, eh? Spurring innovation and so forth.

Windows Movie Maker also turns out to be truly awful. I wasted way too much time. You get what you pay for, I suppose. I ended up purchasing AVS Video Editor, which I'm not linking since it also seems to be only intermittently functional.

In the meantime I came across this interesting article about speeding up A* pathfinding on a grid: Jump point search.

Daniel Harabor makes an excellent point: Having lots of equally-good paths between start and destination just kills A* performance because it must examine every possibility on the chance that one of them turns out to be superior. Here's an example of a situation where there are multiple possible paths (one of which is highlighted):

The path must consist of four horizontal moves and three diagonal moves, but they can be made in any order. Imagine a deck of seven cards, four of which say go east and three of which say go northeast. There are 7! ways you can order those cards. Since there is no difference between the go east cards or between the go northeast cards you divide out by the number of ways you can order those. This is 7 choose 3 (or 7 choose 4), which is 7! / (4! * 3!). The end result is 35 distinct paths. (One of my programming interview questions is about this sort of thing, by the way.)

Daniel speeds up A* by navigating the search space in such a way that only one style of movement is ever used: diagonal moves first, followed by the horizontal or vertical moves. His article is a bit misleading because he is plotting only the nodes that go into the "open" priority queue, and this number is vastly lower with his approach than it is in the basic A* algorithm. However! His algorithm is still looking at all the same grid squares; it's just doing less work at each.

My pathfinding implementation is designed to pick from among all the available equally-good paths with equal probability (in order to make groups of moving units move a bit more chaotically), so it isn't compatible with jump point search. (You could also imagine a pathfinding algorithm that tries to interleave the moves in a way to most closely approximate straight-line movement, which would also not be compatible with jump point search.) It has got me thinking about ways to squash symmetry out of my pathfinding, though.

16x16 Tiles

New version of ThiefRL with 16x16 tiles instead of 8x16. The graphics are still fairly temporary. Sight and hearing is circular on the grid now instead of being twice as far horizontally as vertically (which was to make things come out visually circular). I split the difference so light/sound travels further vertically and less far horizontally as before. As a result the level is probably not the best balance.

Remembering my father

Yesterday my father would have turned 65. He died two weeks ago after having had a lung and its surrounding tissue removed, as an attempt to fight the spread of mesothelioma.

James Sr. (I was a Junior) was born in 1946, second of four. When he was thirteen his father died suddenly (most likely of mesothelioma), and Jim became the "man of the house." He had his impish streak but he was also very hard-working. He knew what he wanted and he got it. He worked his way through college since his mother did not have much money. He pursued my mother from high school, despite not being the favored suitor with her family, and married her following college. He bought a Piper Cub airplane in high school (under his mother's name) which he flew out of the field at the family farm. He did not want to go to Vietnam, so he went to medical school instead. He became a renowned ophthalmologist specializing in cornea transplants, and was the chair of the ophthalmology department at Loma Linda University for a decade. He founded the Inland Eye Bank for sourcing eye tissue.

My father was a meticulous (nay, obsessive) record keeper. Ophthalmologists are gadgeteers (as sure as neurosurgeons are egotists or pathologists are grim or orthopedic surgeons are fun-loving) and my father bought pretty much every generation of IBM PC as a means of keeping his own personal surgery databases. He let me play with them when he wasn't at home and as he saw my interest he kept me supplied with programming software. He gave me copies of IBM Logo, MS QuickBASIC, Borland Turbo Pascal, and eventually Borland Turbo C. I think I first encountered Rogue (the computer game) on a PC in the eye bank offices when I was hanging around there on a weekend with him. Being raised Seventh-day Adventist I had little exposure to pop culture of any kind. Rogue was riveting; I made a copy of it on a floppy disk, took it home, and played it furtively and obsessively. I wanted to make games like this!

After the university sold its ophthalmology department to a private practice, my father did some soul-searching and decided to move to the Pacific Northwest and join up with a "cataract mill," as they were derisively called by many ophthalmologists. To cut costs, these practices devolve most of the pre- and post-op care to a supporting network of optometrists, handling just the surgery bits that the optometrists cannot do. The optometrists love this because referring a patient to a traditional ophthalmologist typically means losing future business; the ophthalmologist will just absorb the patient into their own practice. With a cataract mill the optometrist stays in the game.

Focusing on just surgery meant that my father racked up incredible numbers of them: up to twenty-five surgeries a day, adding up to a lifetime total of over 55,000. (Remember the meticulous records?) He had two surgery suites. The nurses would prep a patient in one while he was operating in the other. He'd walk in, read the patient's name off a sign, and a few minutes later they'd have their cataract out and a plastic lens implanted. By then a patient would be ready in the other room and he'd swap gloves and start over again.

This is incredibly demanding performance work in the space of a square centimeter. There is no tolerance for error. Fortunately the high volume of surgery that he was doing meant he'd seen just about everything and could react appropriately. He experimented with making improvements to his instruments and ran studies on them to see whether the modifications were effective.

They say that when you have your mid-life crisis you buy the car you had when you were a teenager. Remember the plane? Yeah. My father bought a brand-new Super Cub and flew it all over eastern Washington, Oregon, and Idaho. Every time I would visit he'd get me out in his plane and we'd range all over. We dropped in on Red's Horse Ranch (now defunct) in Minam Creek; you can only get there by horse or by plane. We dropped in on a friend's wheat farm; the neighbor boy would come racing over on his quad to get a ride. We'd chase coyotes with the airplane, buzz herds of cattle, do touch-and-go landings at the Lower Monumental dam.

Surgical careers don't tend to run long. Retirement was looming. I think my father was waiting for his 65th birthday to start thinking about what came next.

What came next, last April, was mesothelioma: a cancer of lining tissue, in this case the lining around his right lung.

There isn't any particular reason that we know of why he would have gotten it: he wasn't a smoker and hadn't been exposed to asbestos (the two major causes). My father did several rounds of chemotherapy. I sat in with him on the infusion days and was reminded of how blunt our medical instruments still are in many areas. Chemotherapy is basically poison, to be absorbed by living cells. The cancer, being more vigorously alive than the rest of the body, will hopefully take the brunt of it. There is inevitably a lot of pain, which can be addressed with opiates at the cost of addiction and reduced mentual acuity. Taking the opiates results in constipation. Vitamins are getting destroyed. Sleeplessness is common. Before you know it you're taking a giant regimen of pills and patches around the clock.

The chemotherapy didn't do anything to the cancer. A surgeon at Swedish Hospital in Seattle wanted to have a go at removing the lung; my father was relatively young and in excellent health other than the cancer. After a lot of deliberation he decided to give it a shot. He made it through the surgery but could not sleep in the next few days, which made him paranoid and combative. After sedation he deteriorated steadily until his remaining lung could not supply enough oxygen even with pure oxygen being pumped in via a respirator. We took him off life support (he had not been conscious, I think, since he was sedated three days before) and he died quickly.

Given who my father was, and who I am, it was inevitable that I would disappoint him to some extent. I didn't go to medical school (despite plenty of urging). I didn't marry a nice Adventist girl (despite being sent to an Adventist college). I didn't pick a particularly respectable line of work (and started out in Las Vegas, at that). Nevertheless he was always very good to me and seemed to get on very well with the girl I did marry.

We loved him and we'll miss him.

Resizable Windows

I've just finished implementing a relatively mundane feature that's been on my to-do list for a long time: the ability to resize the game window in my Roguelike projects. I found myself always cranking up the window size during development so I could see more, and then reducing it back to 80x25 upon release. I suppose the next step would be to preserve the window layout in the registry but that comes with its own set of issues, and I want to avoid going into the registry just yet.

Here is the latest version of ThiefRL, my transplant of Thief-style stealth gameplay into a turn-based, grid-based world.

Here is the latest version of SpaceRL, my experiment in approximating zero-gravity movement through a randomly-generated, monster-infested derelict starship.

Both games are pretty simple at the moment; there's lots more that needs to be done.

Supporting resizing involved a fairly major change to the conceptual model of my roguelike framework. It used to have a virtual frame buffer of 80x25 characters. The game would write to this buffer very much like you might have written to the graphics memory in the DOS days, and the framework would display it. Now the game follows the model I more typically use in my non-roguelike games: the framework calls back to the game when it needs the screen drawn, including information about the window size. The game issues calls back to the framework to render glyphs at arbitrary positions within the window.

In ThiefRL I ended up swapping out the speech-bubble placement algorithm for something a bit simpler, in order to get it to behave well on resizing windows. The old algorithm was trying to avoid placing speech bubbles over NPCs. It used a sort of simulated annealing, but this resulted in totally different solutions every time it rendered. When resizing the window this looked pretty crazy. The new algorithm just tries to put each speech bubble on the opposite side of the player from its source, to keep a clear view of the space between the player and the speaker. If multiple NPCs say something on the same turn, though, it's possible for the bubbles to overlap.

I also took the opportunity to touch up some of the in-game note text to give it a bit more thematic flavor. There are still some notes that don't belong at all: the limerick in the heavily-guarded house, for instance. This really was just my test world for features, so it hasn't had terribly focused world-building done on it.

I received a couple of fan letters for these projects, which was very gratifying. I know I tend to lurch about from project to project as my whims dictate. ThiefRL feels like it's furthest along in terms of the quantity and quality of gameplay on offer, and in terms of it not having any particularly big technical challenges on the horizon. (Hierarchical pathfinding would be the next one I can think of.)

Next up, I think I will implement one-way windows in ThiefRL. I think I'd like to give the player more options for de-escalating a situation. One way might be to have "high windows" that you can jump out of to move from a heavily-guarded inner area to a less dangerous outer area. The guards would not be able to follow directly so you would gain some distance immediately. You would not be able to return through the high window, though, so it would preserve the difficulty of getting into the inner area.

Linear Maze

Different maze-generation algorithms can produce drastically different results. Up until now, in SpaceRL I've been using an algorithm that picks a random potential connection and adds it if it is joining two disjoint areas of the maze. Here is a version that does a depth-first traversal instead. It maintains a stack of potential connections to visit. Starting at the entrance, it pushes all potential outgoing edges onto the stack (in random order), then pops edges off until it finds one that goes to an unvisited room. After adding that edge it then pushes on all the unused exits from that room, and so forth until the stack is empty. The result is a maze with a much longer, more linear main path. I'm not sure whether this is good or not, but it's different.

Barricaded Doors Release

Uploaded a new version of SpaceRL.

Changes:

• Once player sees a location, it stays permanently visible.
• Door construction revamped to included barricaded and broken doors.
• Single outside hatch on symmetry axis.
• Player always starts out floating toward the entrance hatch.
• Limit ship's spread away from symmetry axis.

The general algorithm for connecting the rooms is as follows:

1. Come up with a set of all potential adjacencies (rooms sharing a wall)
2. Connect all of the adjacent space rooms together (you can't see them in the final product)
3. Connect the ship's rooms together with “original” doors. These may or may not be passable in the final level but represent how the ship was originally constructed. The ship's interior is minimally connected, plus about 50% of the remaining adjacencies.
4. Doors between the inside and the enclosed outside areas are added. This is the same process as the previous step, but doing it afterward ensures that the ship's original layout would not have relied on going outside to traverse it.
5. Create the door to surrounding outer space. It's on the symmetry axis at the moment.
6. Choose from the set of “original” doors to construct a simply-connected maze through the rooms. This will be the expected traversal. These become regular doors. Note that this path may require passage through enclosed exterior areas.
7. Compute each room's depth from the entrance hatch when traversing via the maze.
8. Turn the remaining original doors into broken or barricaded doors: broken, if the traversal depth is the same on either side, and barricaded (so they can only be opened from the deeper side) otherwise.

A couple other things:

• The window size is expanded from 80x25 to 120x40. It really needs to be resizable but that's been a low priority.
• The number of rooms in the ship is greater: 10-100.
• If you just want to look at ship layouts, use the undocumented Ctrl-A hotkey to toggle visibility of everything.

Barricaded Doors

Miscellany today:

In SpaceRL, I added barricaded doors that can only be opened from one side. With these, the level generator can control the order in which the player encounters rooms in the spaceship, while allowing the player to subsequently take shortcuts across the level.

I also added a slight refinement to the way the level generator places doors. It first creates the ship's original door layout, then replaces some of those doors with barricaded or broken doors to restrict the player's travel path. Previously it was only doing one pass to establish the connectivity of the ship's rooms. With this algorithm there is a slight bit of history implied in the level, as you can see the ship's original symmetric, non-maze door layout underneath the current restricted connectivity.

Separately from this I've been experimenting with learning Javascript. It's not that bad of a language, so far. I had a C program I wrote with a friend many years ago to generate random RPG names; it was designed to be run on a web server to generate a web page. Hardly anybody does things this way any more. As an exercise I rewrote it in Javascript; the server only has to serve up the page and the client's browser does the rest. It's around 10 KB, most of which goes into the word lists. Unfortunately none of the free Google things (Blogger, Sites) are good for serving up Javascript so I can't easily demonstrate. Maybe it's time to get my own domain and hosting again.

I logged into Facebook (as I do every other month or so) and discovered that Chad Jones, an artist with whom I worked on two games over the course of four years, has written an e-book about his last decade-plus of experience working in the games industry. It's a dollar and a good read, especially for anyone thinking about going into games. It's available for Kindle and Nook. The book's called “Laid Off” which in boxed games development is the usual disincentive for shipping a product.

Symmetric Starship Doors

This week I took a break from working on my lunar-lander game to go back and fix the level symmetry in a simple game I made a couple years ago.

SpaceRL (unimaginative working title) is a turn-based, grid-based, Roguelike-inspired attempt to represent zero-gravity motion; in particular, the ability to shoot a gun in one direction whilst floating in another direction. It's inspired by the cover of Tobias Buckell's book Ragamuffin:



The game is very simple at the moment: survey derelict, monster-infested starship wrecks and identify the crew remains. The basic combat maneuver is shown above: get some monsters following you, find a straight corridor, kick off, and blow them away as they pursue.

Coming up with level design that suggests a starship was an interesting challenge. I want something that appears to have been constructed along an axis of symmetry but that due to barricades and debris can no longer be navigated straightforwardly.

This week I finished making door placement be symmetric across the central axis. I also experimented with making the levels into simply-connected mazes. If there is only one way to get to each room from the entrance, the player will need to backtrack more in the process of visiting every room. Whether this is fun or not is debatable; it depends on whether revisiting rooms is interesting. I've thought about having the player eventually find the artificial gravity controls, for instance. Gravity would remove your ability to move and shoot simultaneously, which would change the experience.

The more-likely solution will be the typical thing of having shortcuts back toward the root of the tree that the player can open up. For instance, there might be a door that is barricaded from one side; once the player gets to that other side via a round-about route they can un-barricade it and take the shortcut.

Here are four versions of the same map:

Asymmetric

Symmetric

Asymmetric Maze

Symmetric Maze

The percent signs in the maps represent destroyed doors. They are there to imply that the original layout was symmetric even if the current connectivity is not. The “symmetric” level style means the generation algorithm attempts to connect matching pairs of rooms on opposite sides of the symmetry axis at the same time, rather than leaving it to chance. Without it there tend to be more destroyed doors.

Here is one more ship layout, this time with a horizontal axis of symmetry:

Caves and Orbiting Debris

This week I did a couple of small experiments with the terrain generation. One was to make the base density function (before applying noise) have a couple of concentric rings with space between. The noise function breaks through between the layers to create entrances to the caves. (Actually the base density function has a couple of built-in holes between the layers too.)

I also threw in some orbiting debris to see what it feels like to fly through it. At the moment it is just discs.

The terrain generation needs to have more smarts about area accessibility. I think I'm going to evaluate the density function onto a grid roughly the size of the rocket (maybe slightly larger). Then I can do evaluation at that level to figure out which areas are accessible, and add in terrain features. One of the things I want to do is generate a couple of background layers: one that gives caves a back wall, and then another layer or two that represent far-away mountains (and maybe move with some parallax).

Gatling Gears

Rose accidentally bought Gatling Gears on the PS3, so I played it. It's a twin-stick shooter in the Robotron vein, set in a steampunk world.



Copious, slow-moving patterns of bullets (“bullet hell” I think I've heard it called) are a game mechanic that came out of games like Raiden. This mechanic seems to be getting mixed in to more things these days; Outland combined it with side-scrolling platforming (and Ikaruga's phase-changing) recently, for instance.

Unfortunately Gatling Gears looks unfinished in some respects. The gameplay apart from the bosses is very monotonous. I actually found myself looking forward to the bosses which is a reversal from the usual.

The story is nearly nonexistent. There are story cards inserted between the half-dozen chapters, and printed dialog exchanges at points during the gameplay, which you're apt to miss if you are busy. What story there is seems trite and predictable. You're best off reading Scott Westerfeld's Leviathan series (my review) and imagining that story overlaid on this game. It works pretty well.

The graphics are lovely, though. I am going to go back through the game and try to figure out how the environments were assembled.

Stealing the computer away from my daughter's Minecraft session to make a quick post.

I did some work on learning Blender and straight-away ran into something it can't do: individual edge/vertex beveling. It has an overall bevel modifier which can accept per-edge weights but it is not something you'd use as a poly modeling tool. Searching on the forums reveals that this has been a long-standing lack. Sigh. Well, Maya has a similarly baffling omission; you can't do proper insetting in a face in stock Maya. So they're all lacking something.

Salvage and rescue is the theme I'm working with at the moment. I'm trying to imagine how a spaceship would decompose into constituent parts in a 2D world. Here is some amateurish concept art:



I'm thinking there would be a couple of layers of spaceship: some skin pieces that could be removed, and then various modules underneath that could be salvaged for money. There might be an inaccessible background layer to the spaceship that has its skeleton, too. With 2D art it's not clear to me yet how this all goes together. Maybe the skin parts should just blast off and disappear; otherwise people will expect them to tumble like metal sheets, which they can't do.

Blender 2.5, Planning

I've spent this week doing some planning. One of the things I'm thinking about is how to streamline the process of putting new things into my game. Being able to author the physical parts of them in a modeling program is one way the process could be improved. Yes: the dreaded art pipeline approaches. (Some of my friends who have been involved in startups say that the art pipeline took a lot more engineering resources than they anticipated.)

I have worked extensively with 3D Studio Max in the distant past (I used it for versions 1-3 or so), but the last eight years I've worked with Maya. Of course they're both owned by the same company now. A legitimate copy of Maya runs about $3500, so I'm going to pass on that for now. Blender, the open-source equivalent, looks like it ought to fill my needs. I've been spending time learning how to get around in it.

Blender 2.5 switches to Python 3, with considerable API rework at the same time. This makes a lot of the example code on the net obsolete. Documentation is still a work in progress, so get comfortable with the dir, list, and help commands in Python.

There are a couple of possible ways to export geometry. I'm going to experiment with having the makefile detect when a source Blender file has changed and run Blender at the command line to export it to an intermediate file. The command looks something like this:

blender -b input_file.blend --python my_export_script.py

Restarting Lander Development

The past six months have been very busy at work. We also experimented with having my computer out in the family room, where the TV is.

Now it's back in the bedroom, and work's less hectic. I'm restarting work on my Thrust-alike with an eye toward getting something done and released, even if it is dirt simple.

There are so many things that need to be done it's been hard to decide where to start. At the moment I'm sorting out issues with having planets of different radii. Gravity ramps up linearly as you move from the center of the planet toward the surface, then falls off quadratically as you rise above the surface. The planet's radius was 1.0 which made that pretty simple.

After that, I will probably put a bit of effort into coming up with slightly more interesting planets to fly around. The camera continues to be a problem spot, so I'll keep trying things there.

Animal Crossing --> FarmVille

I have been telling game developers for years that they were leaving money on the table by not making more games like Animal Crossing. My wife pointed out this morning that FarmVille and its ilk are pretty direct descendants of Animal Crossing, and they are indeed taking that money. I don't know how I missed that before; the similarities are obvious once you think about it.

Couple of uploads

Work on various things is ongoing. In the meantime here are a couple of downloads:

A version of the Lunar Lander game that uses 16-bit vertex indices instead of 32-bit indices. May be more generally compatible. Also includes a very basic (read: annoying) rocket noise.

RelativeNeighborhood Starmap experiment. Left-click and drag with the mouse to rotate. Press space bar to generate a new map. The A key toggles between distributing stars on the surface of a sphere and in the volume of a cube.

Also, I finally bought Slay, and recommend it highly. It has a free demo of one map.

Interlocking Orbits

This week has focused on figuring out whether having planets move around the sun can be fun.

Moving planets complicate the trajectory plots in a couple of different ways. The simplest is that I need to move the planets while calculating the trajectories. The harder problems are that:

• Close to a planet, the trajectory ought to be plotted relative to that planet's local reference frame.
• When traveling long distances, the trajectory doesn't help rendezvous with moving planets since it doesn't indicate where they will be in the future.

Moving planets also complicate the construction of the solar system, because each planet needs a path that won't collide with any of the others. They may need to be spread out more from each other. To experiment, I adapted my orrery program to generate random solar systems instead of reading data about the real one.



This one really needs to be seen in motion to appreciate it. Here's a Windows executable.

This program is just generating random orbit parameters and then using brute-force searching to see if the new orbit collides with any of the existing ones. I could undoubtedly do better but it proves the basic concepts. I do some simple checks: if one orbit's minimum distance exceeds the other's maximum distance, they can't possibly collide. Otherwise, I figure their common period (m * n / gcd(m, n)) and then integrate along that period in small steps, checking the distance between the planets at each step.

The random orbits are all generated such that their periods are all integral multiples of a common base (the innermost planets' period). There are ten discrete possible periods in the current solar system, which helps me ensure that they will interlock. I'm currently using a bit of a binomial distribution on planet size and orbit eccentricity, so you'll see few eccentric orbits and few large planets.

The current problem of interest is what gameplay purpose planetary motion ought to serve. Does territorial control mean anything in a solar system? If the planets were stationary I could imagine having planetary defenses that would form a “wall” of sorts along the boundary of a controlled region. With the planets swirling around it's not nearly as clear how that would work.

There are points in time where it is definitely cheaper to go from one planet to another; this is why Mars missions are launched approximately every two years, for instance. I don't know if having a delay element like this in a game would be fun at all, though.

“Disneyland” Solar System

Following a suggestion from Kometbomb I've been experimenting with artificially attenuated gravity. Results have been encouraging. I have an attenuation factor that smoothly cross-fades a planet's gravity to zero at a finite distance from it. (It's the usual 3u² - 2u³ cross-fade, although maybe linear would be fine too.) This allows planets to have strong surface gravity without affecting distant areas, so I can pack them more closely together. It's like a Disneyland version of a solar system (or a bit like Super Mario Galaxy, as Owen suggests.)

The cross-fade attenuation doesn't start until some distance above the surface. As long as you stay under that height you can enter stable orbit around the planet.

At the moment I have all the planets sitting still. The next experiment will be to see if motion can be made to work. Planets will need to be arranged so they can't ever collide with each other, so things may end up getting spaced out more. If motion doesn't make it more fun I think the multiple planets will still be all right. I can see interesting gameplay being built from this.

Multi-planet prototyping

The past couple of weeks I've been working on a prototype of multi-planet gameplay for my lunar lander game. Results are not terribly encouraging, so far.

One of the big problems is figuring out how to miniaturize the solar system without getting totally wacky gravity. On Earth's surface (if I've done my calculations right) the acceleration due to the sun is about 1600 times weaker than the acceleration due to the Earth itself. Thus it doesn't much matter where the sun is in the sky; up is always pretty much the same direction.

I would like to have a smaller, denser solar system to cut down on travel times between planets. Unfortunately in my experiments so far this results in slanted gravity as the sun and other nearby bodies move across the sky.

Our solar system has about 99.9% of its mass in the sun. Thus, there's very little gravitational influence from one planet to another. As I distribute more of the solar system's mass to the planets this makes it harder to fly between them due to the perturbations. (It would also make their orbits unstable but I'm restricting them to only pay attention to the sun's gravity.)

I'm also hitting numerical precision issues as I expand the play area, so I'm trying to track those down.

I may end up falling back to having an “overworld map” for travel between planets, similar to Gravitar. This would lose some of the wow factor that continuous flight between planets would have, but you could operate on different time scales in the two modes and reduce boredom and precision problems.

Planning for 2011

In addition to working on sound over the holidays I did some unsuccessful further experiments with the game camera. I want threats to be visible on-screen whenever possible. What I tried was to collect up any turrets that are close enough to hit the rocket, and include them in the set of things that the camera frames. Unfortunately this introduces big discontinuities in the framing circle's position and size as turrets enter and leave. I have camera smoothing, of course, but even so it is much jumpier than I would like. Maybe I need different "frequency bands" of smoothing, with the threats coming and going on a much lower-frequency smoother. I don't know.

I'm in the middle of planning for the upcoming year. At my day job we are in the last couple of months of development on Infamous 2, so that will demand a fair amount of time. Nevertheless I'm going to attempt to devote an hour a night to work on my own projects; this is what novelists with day jobs do, and I'm not going to get much of anywhere on less time than that.

I'm giving up any TV watching that I used to do, as well as most videogame playing that isn't with my daughter. (By the way: it seems to me there is a major dearth of games that are great for playing with your five-year-old. Currently I'm working through Lego Harry Potter with her. This seems like a potentially underserved market.)

In the near term on the lunar lander game, I'm going to do some experiments to determine the feasibility of having multiple planets that you can fly between. This is the major purpose of rockets, after all, and it's a feature most people who've played it have suggested. The big questions are:

Will this work with the physics engine? I'm going to have several very complex objects moving around (the planets) where I used to have most of the complexity in the static part of the world.

How will gravity work out? Currently the gravity all comes from a single point source, so orbits are straightforward ellipses, and are stable. I'm not too worried about having multiple gravity sources for the player; the rocket flies around under power most of the time and doesn't care if its orbits aren't stable. The mothership can stabilize its own orbit with its thrusters; it's already doing that to some extent. I will probably have to fudge the planets themselves so that they don't affect each other, to ensure that they have stable orbits.

How will the camera work out? Currently the camera rotates so that "down" is down. If I have multiple sources of gravity then there will need to be transitions between orientations so I'll have to figure out how that works.

I will reduce the planets to simple circles for purposes of the experiment, to work out travel times, camera, and so forth.

Treasures of a Slaver's Kingdom is Now Free

Good news, everybody! S. John Ross' magnificent text adventure Treasures of a Slaver's Kingdom is now free.

• Play This Thing review by Emily Short
• My review (not nearly as well written as Emily's)

Enjoy!

Vorbis decoding working

OK, I feel like an idiot. Finally ran down the problem with my decoder, and it turned out to be due to accidentally reading the file as text rather than binary. One of the oldest mistakes in the DOS/Windows-programming book. As soon as the file read encountered the magic DOS end-of-file character it quit reading.

I still think the Ogg format's unnecessarily complicated, and I'm not sure Vorbis is the best choice for dialog lines. I don't want to pay ~4 KB per line of dialog in my game for a bunch of identical decode tables, along with the CPU and memory to unpack them every time I play a line. You could imagine putting all the lines in one Ogg stream and then seeking to the appropriate line, but that would require creating an index, something that Ogg itself doesn't provide. I may take a look at using GSM-style linear prediction compression if I can find a decent implementation.

Ogg = Lame

On further debugging I am forced to conclude that the Ogg container format is lame. This is not saying anything about the Vorbis compression format; I haven't delved into that other than to note that it has quite a bit of overhead for small files, at least the way Audacity encodes it.

Here is a good explanation of the ways in which the container format is unfortunately designed. For my purposes, the main problem has to do with how packet size is encoded. They didn't want to put a fixed-size 32-bit value in the packet header because they expected typical packet sizes to be under 256 bytes. Never mind that they have at least three other wasted bytes in their header, and they chose an encoding scheme that made their header variably-sized. The encoding scheme for packet length is this (feel free to laugh): first, a count byte. Then an array of that many bytes. Each byte represents a part of the size count; to get the full size, add them all together. You are expected to set the first N-1 bytes to 255 and the last byte to the remainder. It's sort of the inverse of compression, really. They should have thought very, very hard before making their packet headers variable size. And then if they really, really thought it was a good idea they could have used the UTF-8 style of encoding arbitrary-size numbers.

The decoder I was reading followed the spec in that it assumed that a non-255 value indicated the end of the array (it isn't paying attention to the count as far as I can tell). However, all the files I've encoded with Audacity have an early packet with a non-255 value in the initial byte, followed by a bunch of 255s, followed by a non-255 final byte. The initial non-255 byte is causing the decoder to prematurely think it's reached the end of the packet.

It's telling that Wwise (an audio middleware provider with which I am familiar) supports Vorbis compression but wraps it in a RIFF-style container format (what .wav files use) instead of using the Ogg container format. (Confusingly they retain the .ogg file extension, though.) It'd be nice if there was a standard for this; I'll have to investigate.

Ogg Vorbis

I have been debugging stb_vorbis.cpp, Sean Barrett's Ogg Vorbis decoding library. Somehow it is not unpacking the Huffman code tables correctly. Since it is broken on every .ogg file I've tried I think it must be somehow related to the way I'm compiling it.

Digging into the .ogg file format has been interesting. All the audio I record has identical code tables on the front (I'm encoding with Audacity), which amount to about 3.5 KB. Ogg is different from other compressed audio formats in that it doesn't have any assumed decoding tables; they all have to be embedded into the file. If you put individual lines of dialog into their own .ogg files that adds up to quite a bit of overhead (about 20% for my lines which are currently around 17 KB each).

A tidbit I learned: DVD audio is sampled at 48 KHz, rather than being the same rate as CDs (44.1 KHz). I'd wondered why PS3 games had 48 KHz audio; now I know why.

I've been thinking about how to complete my lunar lander project so I can move on to others. Part of the problem is that I haven't really settled out which direction I want to take the gameplay. More later; have to go to work now.