This thread was split off from <a href="index0708.html?topic=784.0" class="bbc_link" target="_blank">that other thread</a> because it wasn't cool enough. (-:

Minimum skills required for getting just 1 Lemming to the exit in Lemmings 2 levels.

<span style="font-family: courier;" class="bbc_font">
 -----------------------------------------------
|Tribe    |  1  2  3  4  5  6  7  8  9 10 Total |
|---------|-------------------------------------|
|Beach    |  0  1  2  3  2  4  4  2  6  1   25  |
|Cavelem  |  1  5  1  2  2  2  4  5  2  4   28  |
|Circus   | -- -- -- -- -- -- -- -- -- --  ---  |
|Classic  | -- -- -- -- -- -- -- -- -- --  ---  |
|Egyptian | -- -- -- -- -- -- -- -- -- --  ---  |
|Highland | -- -- -- -- -- -- -- -- -- --  ---  |
|Medieval |  4  5  2  3  3  5  4  5  1  2   35  |
|Outdoor  |  0  0  1  1  2  3  2  4  4  1   18  |
|Polar    | -- -- -- -- -- -- -- -- -- --  ---  |
|Shadow   | -- -- -- -- -- -- -- -- -- --  ---  |
|Space    | -- -- -- -- -- -- -- -- -- --  ---  |
|Sports   | -- -- -- -- -- -- -- -- -- --  ---  |
 -----------------------------------------------
</span>

Like we did for Revolution, I'm starting a thread to document the Lemmings 2 data files and their contents. I am aware that there is existing documentation out there, but I don't feel that it's quite verbose enough to make full sense of what the files truly represent, so I'm starting from scratch. However, I would like to thank geoo, Mindless and any other contributors ahead of time, as I am using those documents for reference.
__________

Compression Format

Integer data types are little-endian.

File
===============================================================================
Identifier         String*4       ASCII "GSCM"
UnpackedSize       UInt32         Total size of decompressed data
Chunks             Chunk[]        Compressed data chunks
===============================================================================

Chunk
===============================================================================
LastChunkFlag      Byte           Last chunk = 0xFF; 0x00 otherwise
SymbolCount        UInt16         Number of symbol definitions
SymbolList         Byte[Count]    Destination symbol names
SymbolValuesA      Byte[Count]    First byte of symbol
SymbolValuesB      Byte[Count]    Second byte of symbol
DataSize           UInt16         Number of bytes in encoded data
Data               Byte[Size]     Encoded data bytes
===============================================================================

At the beginning of each chunk, a 256-symbol dictionary is initialized.
Dictionary entries are indexed 0x00 through 0xFF, and each symbol is
initialized to the single byte value that matches its index. The symbol
definitions are then modified by concatenating symbols as specified by the
lists in the chunk header.

For each entry according to the entries in SymbolList (by index) the symbol is
redefined by concatenating the values of the symbols according to
SymbolValuesA and SymbolValuesB (also by index). All three lists represent
items in parallel to one another: the lists are all the same length, and the
item at position X in one list is to be used with the item in position X in the
other two lists.

The following specifies the algorithm for each item X in the lists, from 0 to
SymbolCount - 1. Symbols must be redefined in that order. Let "+" represent a
byte-wise concatenation operator:

  Symbol[List[X]] = Symbol[ValuesA[X]] + Symbol[ValuesB[X]]

When bytes are processed from Data, they represent the indexes of symbols in
the dictionary. The symbols are copied wholesale, in the order they are
specified in Data, to the output. This takes place after the symbols are
redefined using the symbol lists.

Chunks will continue to be processed until a chunk with a non-zero
LastChunkFlag has finished processing.

In the event data is not compressed, it will not begin with the "GSCM"
identifier. Use the data as-is in this case. Both compressed and uncompressed
data can be used in most contexts, so they are processed according to whether
that "GSCM" identifier exists or not.

Hermann Schinagl made a LEMZIP utility for converting files to and from this compression format. It can be found at the following page:

http://www.camanis.net.ipv4.sixxs.org/lemmings/tools.php
__________

Data File

Many of the data files in the game are packed into a structured archive format, where the file is broken up into sections. This includes the .dat files for graphics and levels.

Integer data types are little-endian.

File
===============================================================================
Identifier         String*4       ASCII "FORM"
DataSize           UInt32         Size of the remainder of the file
DataType           String*4       ASCII identifier for the data file type
Section            Section[]      File sections containing additional data
===============================================================================

Section
===============================================================================
Identifier         String*4       ASCII identifier for the current section
DataSize           UInt32         Size of the remainder of the section
Data               Byte[Size]     Data specific to the type of section
===============================================================================

The number of sections in the file depends on the respective sizes of existing
sections as well as the total data size reported in the file header.
__________

Graphics Representation

For 256-color graphics, palettes are specified and pixels are plotted on the screen. Pixel information is specified in the "styles" data files as well as the full-screen background images. These images specify a particular pixel order, which is demonstrated with the following animation:



Pixels are drawn every fourth pixel, starting with the top-left pixel of the image. Pixels proceed left-to-right, skipping three pixels each time. All rows of pixels are drawn in this manner, from top to bottom. Once the end of the last row is reached, drawing moves back to to the top row, but starts from the second pixel from the left. As before, every fourth pixel is drawn for every row of pixels. After four passes, every pixel in the image has been drawn.

Let's say you have a byte buffer containing pixel data for an image. Each byte is one pixel. The pixel Byte within that buffer, designated as Data[Byte], can be translated to X and Y coordinates with the following general formula:

Operators:
= Assignment
/ Integer division
% Remainder division
* Multiplication
+ Addition

Stride = Width / 4
Pass   = Byte / (Stride * Height)
X      = Byte % Stride * 4 + Pass
Y      = Byte / Stride % Height
Here, Byte is the current byte in the buffer, starting at index 0. Stride represents the number of pixels drawn per scanline in a single pass. Pass indicates the current pass of drawing pixels for each scanline. Width and Height are the final dimensions of the image, and X and Y are the pixel coordinates within that image, relative to the top-left corner, of the pixel specified by the current byte.

Tiles in level data are 16x8 pixels in size. Plugging in those numbers produces the following formula:

Stride = 16 / 4
(Stride = 4)
Pass   = Byte / (4 * 8)
X      = Byte % 4 * 4 + Pass
Y      = Byte / 4 % 8

...

X = Byte % 4 * 4 + Byte / 32
Y = Byte / 4 % 8
This is a somewhat complex formula for the X and Y coordinates, but it cannot be simplified any. However, processing pixel data can be simplified by taking a different approach.

Let's now say that you read pixel data from the original byte buffer, called Data, and you want to re-order them and store them in a new byte buffer, called Output. To do this, we have the input byte index specified as Data[Byte], and the output byte index specified as Output[Pos]. From here, we get the simple end goal formula:

Output[Pos] = Data[Byte]
The calculation of Pos, therefore, is necessary. Using the earlier X and Y pixel coordinates, Pos can be calculated accordingly:

Pos = Y * Width + X
Substituting for X, Y and Width yields a pretty ugly expression, but it can be simplified. Take a look:

Operators:
<< Bitwise left shift
>> Bitwise right shift
|  Bitwise OR
&  Bitwise AND

Pos = (Byte / 4 % 8) * 16 +
      (Byte % 4 * 4 + Byte / 32)

...

Pos = (((Byte >> 2) & 7) << 4) +
      (( Byte       & 3) << 2) + (Byte >> 5)

...

Pos = ((Byte & 28) << 2) +
      ((Byte &  3) << 2) + (Byte >> 5)

...

Pos = ((Byte & 31) << 2) + (Byte >> 5)

...

Pos = Byte % 32 * 4 + Byte / 32
How 'bout them apples? Turns out both of those 32s in the expression come from the following expression:

Width * Height / 4
Meaning our final, unadulterated formula looks like this:

Quarter = Width * Height / 4
Output[Byte % Quarter * 4 + Byte / Quarter] = Data[Byte]
This works not only for the level tiles, but any of the graphics stored in the same general format:

So there I was, solving puzzles in Lemmings Revolution. I got all the way to the rightmost column, which are these big, long, hard levels that put the icing on the Lemmingsing cake. Just take a look at how daunting these levels can be:

Level: 12-7
The Long and Winding Road
20 Lemmings : Save 5
Time: 5:00
Skills: 10 of everything

(Don't mind the one going to explode there in a few seconds. I'll be using this as a promo shot for the Full Color hack)

Investigation into the problems with Lemmings Revolution on Windows 7 turned up some unfortunate results regarding how the game was designed to work with DirectX 7. The short description is that as DirectX continued to change and be updated, specific behaviors of DirectX 7 were either deprecated or fixed, resulting in a Lemmings game that has been falling apart over time.

Since we're basically looking at a program that relies on a deprecated specification, fixing it will be a time-consuming endeavor. Basically what's required is that we create our own versions of the DirectX DLLs that behave in the way DirectX 7 did back in the day, then feed them to the Lemmings Revolution EXE in place of the modern DLL files.

Lemmings Revolution fortunately has a fairly rudimentary construction, so it's not necessary to re-implement the entire DirectX API. It doesn't even use Direct3D proper (instead deferring to DirectDraw's basic 3D functionality), so the subset of DirectX that needs to be replaced for Lemmings Revolution to function properly is pretty much this:

• DirectDrawEnumerate
• DirectDrawCreate
• IDirectDraw (and all its methods)
• DirectSoundEnumerate
• DirectSoundCreate
• IDirectSound (and all its methods)

If we can produce a couple of replacement DLLs, say ldraw.dll and lsound.dll, we can circumvent the problems cropping up due to DirectX's updates and pull Lemmings Revolution back into the realm of things that will continue to work according to current API specs.

Such an initiative I would refer to as DirectL. (-:

EDIT: Renaming thread

It's a nice day in northwest Oregon today: 51 degrees and sunny. For a cold-blooded person like me, that's not even jacket-worthy weather.

A year ago, I had just made my way to Washington from Illinois for undisclosed reasons. I was staying with a family during the month of February, but after that I was out on my own with no job and no place to live. I spent March and April living in the back of my van until I had enough money to move into an apartment. I would spend all day at the public library with my laptop, and I'd buy some quick fast food and retire to the back of the van every night. From a dieting perspective, it was the fastest way to lose 30 pounds ever conceived. (-:

I remember sitting there in the library on a day much like today, learning about the then-upcoming A Boy and His Blob video game for Wii. That's the day I made my current avatar. Also in that library, I remember playing through days and days of Lemmings Revolution while waiting to hear back from prospective employers.

It was becoming autumn by the time I moved to Oregon, and it only took three weeks before I had a place to stay this time around. This is the first time the weather has been like this since I got here, and while I was driving to get some lunch today, I realized "I'm reminded of Lemmings. The weather is reminding me of Lemmings." Indeed, I remembered this place. My time in the library eventually led to me discovering the "Lemmings Community forums" and, of course, I've had my head poked in here ever since. I remember getting home from work on days like today, looking at these forums for whatever the latest Lemmings trend was.

The last year has been a pretty rough time; being homeless wasn't so bad considering, but there were other circumstances that made life less than desireable. But this is where I'd go to get away from the world and recollect all of the things I enjoy. So since the sun has reminded me of the people I appreciated at a time when I needed them, I figured I'd just take a moment to thank everyone for sharing in my enthusiasm for this quirky puzzle game of ours. (-:

My Metroid project is being organized in a modular fashion that essentially connects the inner workings of multiple programs into a root system that uses them each in combination or in some cases even interchangibly. And with my purist mentality when it comes to programming and my stubborn unwillingness to use anything other than the C language, my solutions often spread into areas unseen by coders who work under the banner of the accursed class. And I wouldn't have it any other way!

In this case, though, I want to construct a simple system that incorporates several smaller systems into a singular workload processor. And the exercise is one I'm sure will be welcome in this community: Lemmings level editors!

Normally, level editors would be standalone programs, but I'd like to devise and implement a system that binds multiple editors together into a single structure, while still enabling individual parts to be detached or new parts to be introduced later on. This means I'll be able to work as hard as I want and once I get the system working, I don't have to do any more if I don't want to. (-:

Of course, the other side of that coin is that I can introduce new editors whenever I make new modules, so it should eventually become some sort of all-encompassing project that this community will be able to hold up to the rest of the internet and brag about. What fun!

I know that this project will be stepping on some toes, and I apologize for that in advance. If you've been working long and hard on a level editor for a Lemmings game and I come along and one-up you or your loved ones, bear in mind that it's all in good fun and in the name of computer science... Besides, I'll be back to making Metroid before long, so other people's toes will be stepped on instead of yours. (-:

Regretably, I'll be doing Lemmings the first first. It always gets all the attention! But, alas, it is likely the simplest, so it would be the best place to start.

Per request, I bring news of the in-progress Metriod project I started!

The idea was conceived originally after the release of Metroid Prime Hunters while I was playing a majoratively-unrelated game called Soldat. Soldat is an interesting production, because it's a side-scrolling multiplayer shooter, which isn't something you see much of anywhere. Soldiers fly around with jet boots shooting each other in a 2D environment and the hectic online interactions make it the perfect tool for wasting time.

One day while playing the game, I was picking my weapon and something triggered the thought of Metroid Prime Hunters's multiplayer mode where you... well, you can pick your weapon. This resulted in a constant stream of thoughts that incorporated Metroid elements into the Soldat gameplay and eventually I became inspired enough to make it a reality.

Now, try as I may, I can't seem to avoid having a life, and it keeps weaseling its way into my priority list. Curses! So development of the project has been limited, but its current progress is definitely promising. I decided it would be an opportunity to try my hand at both the technical and presentation sides of the video game coin, where I pull off all manner of programming tricks to accomplish some stylish feats as well as make a stylish game as a whole.

During production, I invented a concept that I'll probably stick with for the rest of my life: a sort of "seal" representing quality for the program code. When I write a function to do something, I make sure it's as simple as possible (since that makes an efficient program), and that it works correctly regardless of what parameters it receives. The end result is a highly-optimized function that performs flawlessly... and, as such, I have enough confidence in it that I venture to label it bug-free. Most people consider it folly to say that a program is bug-free, but I'm so totally gonna go there. I will not release a product unless every last function in it receives this "optimized and bug-free" seal, and should a bug ever be found, it will be recorded in a permanent register accessible by the public. Hopefully, I'll never have to start that register. (-:

The Metroid project takes the side-scrolling gameplay of Soldat and uses Metroid elements to define the experience. The terrain is composed of simple line segments that the characters and projectiles interact with. Pointing the mouse cursor anywhere on the screen becomes the location of the target, and firing a gravity-free projectile will fly straight through the cursor; such is how the aiming works. There will be various characters to choose from, and various pick-ups and terrain types to make life more interesting.

Expanding on the Metroid idea, the game maps will consist of multiple rooms to create VERY large areas, just like the Metroid games in general. In fact, the game is being designed as a general-purpose Metroid engine that could be used to produce custom single-player (or co-op) campaigns as well as competitive multiplayer situations.

One of the goals for the project is that it'd work for Microsoft Windows as well as any distribution of Linux running the X Window System, so the foundation of the project was a cross-platform API that creates UI windows and binds an OpenGL context to it. The API will also be responsible for enabling the POSIX-compliant IP networking API and whatever is needed to send audio buffers to the speakers for sound output. This API's been in the works for a few years, and its current state is one I'm comfortable with and it's being used in the Metroid project. The API will be maintained seperately from the projects based on it, and when it's completed I'll have a ready source of cross-platforming that will let me get my software running on multiple systems with minimal preparation.

Though I have a good understanding of the things that need to be taken care of to produce a game of this sort, all the nitty-gritty details and considerations of actually implementing it in programming aren't something that comes so readily, so I'm always thinking and experimenting with the best way to do things. The physics system is one of the major aspects of the program, and I'm still tinkering with different ways to make it work well and suit my needs. Once I get it situated the way I like it, a major chunk of the programming will be done and I can get to work on more interesting gameplay aspects.

The latest build of the progress is attached to this build (be sure to check readme.txt). But, again, due to life, it hasn't been worked on since July 4. But I'm looking into getting back to work on it!

And a picture:

I was playing through all the Lemmings Revolution levels and eventually quit playing. A month later, I went back to the game completely wondering why I stopped playing and remembered. The later levels require you to time your solutions in such a way that the Lemmings can pass a certain spot at a certain time, but all the while it needs to be done within the level's time limit.

An example is the very very last level, appropriately titled "It's Going to Take Time." In this level, at the very end, is a rotating log with spikes on it that moves ever-so-slowly and only cycles twice throughout the levels' time limit. For half of its cycle, it's down by the ground where the Lemmings walk, and the other half of the cycle it's up in the air so the Lemmings can walk under it. The rest of the level is a multi-layered puzzle filled with one-way walls, switch-driven platforms and even a bit of backtracking. I liked the level in and of itself, though upon reaching the end I found that my first solution was timed incorrectly and all the Lemmings got cut up by the spinning spike-log.

There are lots of levels later in the game that require proper timing like this. At least one level has some boxed-in weasels with switches that, as they walk left and right, enable and disable platforms. This requires the player to get the timing right in order for a Lemming to pass the platform without falling to its death, eventually to do away with the pesky weasel.

I've always considered Lemmings something that you could theoretically plan out from start to finish just by pausing the game at the beginning, but when things change depending on what time it is, it, for me, just throws in an element of irritation that I don't care for. So my question to you guys: is the idea of "proper timing" a reasonable consideration in the creation of Lemmings levels?