Sunday, April 25, 2010

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.


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.

Sunday, April 11, 2010

Spiral Galaxy Hack

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:
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.

Monday, April 5, 2010