Chip 2003 August/Chip_2003-08_cd1.bin/oddech/maelstrom/maelstrom.exe/Maelstrom/Docs/Technical_Notes-v1.0

Text File | 1999-12-07 | 15KB | 261 lines

The first challenge was figuring out how to get the Macintosh resources
into a form that could be dissected from within UNIX.  First, I tried
copying files over from "Executor", a Linux based X11 Macintosh emulator.
Unfortunately, Executor wraps the resource fork in a special header,
rendering it difficult to decipher.  The solution was to BinHex the files
on a Macintosh, and then use the Linux utility 'mcvert' to extract the
resource fork from the archive.  I also used the ALPHA 'hfs' filesystem
for Linux, but got a file that was different than the one 'mcvert' unwrapped,
so I didn't trust it.

The second problem was finding out the format of the Macintosh resource
fork, so that the resources could be extracted.  This was solved by going
to the bookstore and looking it up in the "Inside Macintosh" series
published by Addison and Wesley.  This series has detailed specifications
on the internals of the Macintosh operating system.  This was pointed out
by Andrew Welch, the author of Maelstrom.

The next tricky part was after I had written code to look at the various
parts of the resource fork of the Maelstrom game, the values seemed way
too large to be correct.  The offset for the Resource Map was 4 MegaBytes
into the file, when the file was only .5 Megabyte large.  This was caused
by the fact that Linux is little-endian, while Macintoshes are big-endian.
This was solved by running ntohl() and ntohs() on the offset/value fields
of the resource fork.

I wrote a utility to list and extract all resources from a Macintosh binary
resource fork.

I extracted the sprites from the Maelstrom resources, and attempted to view
them in a VGA console, using custom-crafted bitmap viewing utilities.
The sprites appeared, but appeared in psychedelic colors.  Evidently,
the colormap was wrong.  I played with the colormap, setting it to the
standard colormap, which didn't help.  I used ResEdit on the Macintosh
to look into the ColorMap resources of Maelstrom.  ResEdit has a colormap
editor that can display and set the colormap of a Macintosh application.
I used it to find out the proper colormap for displaying Maelstrom sprites.

Next was the sounds.  I used the resource parsing code to extract the
sound resources, and then used "Inside Macintosh: Sounds" to look at
the format of the sounds used in Maelstrom.  It turns out they are all
either format 1 or format 2 sampled sound bites which can be directly
played on /dev/dsp under Linux.

Then, I worked with the colormap resources.  I found the format for the
colormap resources in "Inside Macintosh: Imaging with QuickDraw"
I used this description to write a utility that converts a binary clut
resource into a C header file describing the colormap.

Next was the PICT resources: the title screen, credits, and info screens.
I looked at the "Inside Macintosh: Imaging with QuickDraw" for the PICT
resource format, and freaked when I saw it was a collection of opcodes
for the QuickDraw routines.  Then I found that the first part of the
Maelstrom PICTs seemed to be a colormap.

The solution to the problem of understanding PICT resources was going
to     ftp.sunet.se:/pub/mac/mirror-umich/graphics/graphicsutil
and retrieving the programs "GraphicConverter" and "pictmanagementutils"
I used these programs to extract the PICT resources and save them
as raw PPM files.  Then I wrote a simple program to display raw PPM
files on the VGA console.

I copied the raw PPM files from the macintosh disk to the Linux system
by mounting it with the 'hfs' module loaded, and then doing a straight
copy of the data portions of the files.  The 'hfs' module for Linux
was written by Paul H. Hargrove, [e-mail]

I then translated PPM files to XPM format with xv, performing image
enhancement.  I then wrote a utility to merge the colormaps of the
pixmaps and perform a check to see if all the colors are in the
standard colormap of Maelstrom.  They are, so I can convert them all
into raw pixel data -- a form more suitable for blitting to the screen.
This form also takes less disk-storage than either the raw PPM data
or the textual XPM data.

When loading up Maelstrom, I thought it might be nice to create a color
icon for the window manager to use.  I created it by resizing and
simplifying the main title image of Maelstrom with xv and then turning
it into a standard colormap xpm icon.  The program 'xboing', written by
Justin C. Kibell, [e-mail], creates its own color icon.  I looked
at the code for this, and used the technique with Maelstrom.
The technique is basically to create a pixmap on the X server and then
tell the window manager to use it for an icon.  This must be done before
the window is mapped on the screen, otherwise the window manager ignores
its hint.

Then, I tried allocating a private colormap for displaying Maelstrom
graphics.  Well, that works, and the code is still in place to support
that, but the Maelstrom colormap turns the rest of the screen flourescent
colors.  I looked at the code for 'xv', written by John Bradley, and
found a good algorithm for mapping the colors needed to the existing
color palette.  I have ideas for more advanced algorithms of color
allocation, but the direct mapping method seems to work well enough for
me.  One problem with this approach is that once Maelstrom is started,
it locks all the colors in the colormap, preventing applications from
allocating new shared color cells.

One of the primary factors affecting game playability is the speed of
real-time animation.  One of the best ways to achieve high-speed animation
in the X11 environment is to use the MITSHM extension.  The standard
method of working with X shared memory is to create a small (300x200)
shared image, manipulate the image and then "put" it on the server
with XShmPutImage().  Reasonable speed can be achieved with this method,
however this is not fast enough for the needs of Maelstrom.  Maelstrom
is played in a 640x480 window, and copying a 2.5 megabyte image into
the screen contents would take way too long.  I get around this problem
by creating a shared Pixmap, and making it the background of the window.
Background pixmaps are tiled, so the background Pixmap has to be exactly
the same size as the window.  Now, the background of the window can be
directly manipulated, and refreshed with XClearArea().  This approach seems
to be much faster than working with an XImage, and blitting it to the window.
One side-advantage of this approach is that graphics can be drawn in
the foreground of the window, without affecting the animated background.
Another benefit of this approach is that a redraw on an expose event
simply consists of an XClearWindow() call, without having to redraw
the entire contents of the graphics window.

Next was sound mixing.  I used a simplified version of the sound mixing
code in 'sfxserver', written by Terry Evans, [e-mail], for
sound mixing.  Each loop of the mixer compiles multiple channels of
the sound mixer into a single chunk of sampled data which is sent to
the audio device.  The original idea was to have a continuous loop,
first checking for input, and then writing a chunk of sound (or silence)
to the sound device.  This resulted in slow response time, because the
a sound event had to wait the entire cycle of compiling the sound channels
until it could be acted upon.  I modified the original concept to support
asynchronous input.  Now, the loop has been simplified to a simple continuous
play of the sound channels, but at any time during the compilation of a
sound chunk, new sound data can be placed into channels, or removed from
the mixing channels.  This allows nearly instantaneous mixing of sound effects,
in response to sound events.

I decided to run the sound server as a separate process from Maelstrom.
The sound server has to continuously play sampled data (sound or silence)
and respond instantly to sound events.  Maelstrom has to continuously
update animated graphics.  I thought the best way to perform both of these
functions simultaneously was to do them in separately running processes,
communicating through a private UNIX domain socket.

PROBLEM: After we allocate a full colormap, Maelstrom wants to allocate
other colors.  We have completely filled the colormap, yet... what can
we do?  We can completely take over the root window colormap...
That's not polite, but what else can we do?

PROBLEM: After we allocate a full colormap, Maelstrom wants to allocate
other colors.  We have completely filled the colormap, yet... what can
we do?  We can completely take over the root window colormap...
That's not polite, but what else can we do?
... Try to allocate the closest color in the colormap and see what we
come up with...

The best thing might be to grab a copy of the current screen and see
what colors are actually in use, and reserve all the rest.  Hmmm??

Mapping to the closest color already in the colormap seems like it
works.  It's not perfect, but it is polite, and prevents lots of
gyrations trying to blend a private and public colormap.

I tried to allocate all the colors, and then map the ones that were
left.  That didn't work.  The colormap was left full, and the colors
that needed to be mapped didn't have any colors to map to.

I wrote a routine to convert the Macintosh color icon resource into
both XPM and Linux-Maelstrom sprite format.

The next challenge is the fonts...

I found a program called 'mac2bdf' that converts Macintosh FONT resources
into UNIX bdf fonts.  I'm using the information here to learn about the
Macintosh font format.  My plan is to write a "Font Server" that can
translate text, given font and pointsize, into a blittable Sprite.

The font server works nicely. :)

Next challenge is how to blit the sprites.  The best way is probably to
keep an off-screen buffer and save the area behind the sprites to this
buffer.  When the sprite is removed, the screen is restored from this
off-screen buffer.  If this "back-buffer" is too big, we can possibly
save a shred of the background in the Sprite data structure and use that
to restore the background.  The off-screen buffer is a more robust
implementation in that it allows graphics pen styles, such as XOR, OR,
etc.

Saving the back-buffer in the sprites is a bad idea because two or
three sprites may go over single point, and each would have a different
idea of what the background looks like.

The standard way of blitting sprites is to cycle through the sprite,
checking against the mask, and put the pixel if it is "live".  This
requires a loop iteration for each pixel in each scanline.  This can
be fairly time consuming.  A much faster method was outlined by Andrew
Welch, and that is to compile the sprite into a continuous stream of
pixels, arranged by a series of opcodes describing where the next pixel
should go.

    By compiling the sprites, I achieved a speed up of 45%
over the old sprite/mask method.  An additional advantage is that
the compiled sprites take much less storage space -- an average of
50% less space.

Sound:  Under certain conditions, Maelstrom wants to wait until a
sound is completed.  In the original code, Maelstrom looped, polling
the server, waiting for the sound to finish playing.  Unfortunately,
polling the server interrupts the write() which must be restarted.
In continuous polling, the write keeps having to be restarted and
the sound never finishes playing.  If the sound status is kept by
the Maelstrom process, with the sound server sending periodic updates,
then the sound server can be greatly simplified and will not be
continuously polled.  This is the new approach I will take.

This approach works well enough.  The sound server takes very little
CPU time, as most of it's time is spent waiting for device writes to
complete.  One of the challenges I ran into, in writing interactive
sound code, is you need quick response time to user events.  For example,
if the player presses the "Thrust" key, you need to be able to start the
thrust sound, and stop it almost immediately.  One of the parameters
you can tune to get this is the fragment size of the sound-card writes.
If you have a large fragment size, then large amounts of sound are
quickly processed and sent to the sound device.  Once it is in the
sound device buffer, the sound cannot be cancelled.  However, as the
size of the audio-fragment decreases, you begin to have better control
over the timing, starts and stops of the interractive sound.

    For Maelstrom, I found that a fragment size of 1024 (2^10)
was about right for good response time without instantaneous response.

    Instantaneous response is not, in general, a good way to
program an interactive game, such as Asteroids or Maelstrom.  The
player expects to see an organic, analog universe, not one that
reacts instantly to conditions.  In the real world, cause and effect
relationships are not instantaneous or even immediately obvious.
For example, when a jet passes overhead, the sound of the jet trails
the sight of the jet by a good distance.  Another example is acceleration.
When gravity takes hold of a body, the body gradually accelerates to a
maximum velocity -- it doesn't immediately reach its terminal velocity.
These organic and semi-random natural conditions can be simulated in
the computer using random vectors and calculated delays to produce an
environment more suitable for interactive play.

    Timing is a crucial part of interactive games.  In Maelstrom,
large portions of code are devoted to boundary condition detection and
timing conventions.  At each frame update, all sorts of time-dependent
conditions are checked -- how much time has it been since the last
screen update, is it time for a keyboard check, has the shield ran out,
etc, etc, all these are crucial components to a well-rounded game.
If things are handled too quickly, the player no longer enjoys playing
the game -- there is no time to repond.  If things are handled too
slowly, the game appears sluggish and is no longer fast-action fun.

    I'm working on clipping.  Right now, clipping is handled by
dynamically recompiling the compiled sprite when it's near the edge of
the clipping rectangle.  This is okay when there are only a few sprites
on the screen, but when there are more than about ten or twenty, this
becomes too slow.
    I'm going to try to add code that will detect if the sprite
is near the edge of the clipping rectangle.  If it is, it will call
the Blit_Sprite() function, instead of the Blit_CSprite() function.
It is faster to clip a pixmap than it is to recompile a compiled
sprite, I think.