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.