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.

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.

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

Monday, March 29, 2010

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.

Monday, March 22, 2010

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.

Monday, March 15, 2010

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.