Here I Go Again!

[GuyPerfect]

Got it! The hecka funky compression algorithm is actually kinda clever, though I'm not sure why they didn't stick with LZ like the first Lemmings... Basically, the system defines single-byte symbols that represent multi-byte values. So you could make 0x03 represent 0x12 and 0x34, for instance. Symbols can be composed of other symbols, too. So 0x04 can be made of 0x03 and 0x56... but since 0x03 is already defined as 0x12 0x34, the definition for 0x04 thusly becomes 0x12 0x34 0x56. A neat little setup.

The part that was throwing me off is that symbols can be redefined as the decoder works down the definition list. With the example above, I can re-define 0x03 as 0x04 0x04, which overwrites the old 0x03 definition with the new one: 0x12 0x34 0x56 0x12 0x34 0x56. So now we have a one-byte symbol that represents six bytes.

This dynamic setup makes the task of coding an optimal compressor quite a daunting one that will take many hours or even days of careful engineering to design and implement...... ooooooor, I could just store new level data in the files as raw data and bypass the dynamic symbol list altogether. I mean, we're not interested in saving file space, right? Just patching new levels to the game? (-:

I'll write a decoder and simple raw encoder and see about getting an 8-bit paletted OpenGL context set up. I still need to hack the graphics, but it won't be long before I can display levels. And then it's just a little interface programming before we can make levels.

Concerning your question, Dullstar, it's something that can take up a whole 'nother thread, so I'll have to get back to you on that.

[Dullstar]

Video games or off topic?  It's about a game, so...

[ccexplore]

In particular, I found that they used a commercial utility called PKLITE <snip>

You really should learn to use the internet better, instead of just reflexively sneer your nose at things like say Wikipedia or the C FAQ (I do understand your reasonings to be skeptical and it's good to have a healthy dose of skepticism, but still...)

In the case of pklite, a quick search with Google or similar years ago quickly led me to a program called "unpklite" which will readily undo the compression of PKLITE on the Lemmings executable.  This is how I managed to reverse engineer enough of the game to accurately reproduce the game mechanics for benefit of projects like Lemmix's playtesting features (as well as the all-important compression algorithm for the game's data files).

I should note though that for some reason unpklite fails to work on Xmas Lemmings, and I still haven't found a program that works.  But if you have a debugger, it looks like a close enough alternative would be to just run the program through a DOS debugger, and then examine the memory after the program exits--most if not all of the code, in uncompressed form, will still be there.

That said, like Clam, I'd rather you work on Lemmings 2 anyway.  And I probably can answer all the questions you may have on Lemmings 1, given that I've done a whole bunch of reverse engineering of the EXE already.  (Plus, some of the information like the formula for passwords to next level is actually already information available in, you guess it, the internet.)

[ccexplore]

This dynamic setup makes the task of coding an optimal compressor quite a daunting one that will take many hours or even days of careful engineering to design and implement...... ooooooor, I could just store new level data in the files as raw data and bypass the dynamic symbol list altogether. I mean, we're not interested in saving file space, right? Just patching new levels to the game? (-:

I agree.  Compression was mainly for the era when games still ship in floppy disks.  Unless the poorly compressed data is causing problems with the game, I suggest start simple and come up with the simplest compression scheme that works, no matter how suboptimal it is space-wise.  LemEdit for example have a similar poor compression scheme compared with the actual game's, and that hasn't hurt anything.

[GuyPerfect]

You really should learn to use the internet better, instead of just reflexively sneer your nose at things like say Wikipedia or the C FAQ (I do understand your reasonings to be skeptical and it's good to have a healthy dose of skepticism, but still...)

Holy grudge, Batman! That thread almost made it out un-jacked!

While you may have perfectly valid and substantiated assertions that I am incapable of conducting significant independent research and am afflicted with ethical depravity for failing to embrace a subjective work as a basis for one of my philosophies, I'm afraid you are nonethless missing the point.

If my goal consisted entirely of producing level editors for Lemmings games, I'd hunt down all manner of existing documentation and tools that do the hard work for me so that I don't have to do it myself. However, I find much joy in hacking these things, and the true reward for me comes from creating systems that take everything I've learned into account to accomplish whatever thing I was after in the first place. That is to say, I'm in it for the hacking, not the level editing.

Decompressors already exist for Lemmings and Lemmings 2 (heck, I was easily enough able to find documentation for the algorithm used in Lemmings), but I have nonetheless spurned such solutions in favor of figuring things out on my own. It's fun on the one hand, practice on the other, and the whole exercise is one that I greatly enjoy. But since I'm not after the decompressed data itself--and indeed, not after the decompressed executable--it's not a matter of knowing how to use Google; it's a matter of using the opportunity to put my skills and one of my favorite activities to good use.

With an unPKLITE'd Lemmings program file, any edits wouldn't fully be something that I've done, and that's one of the bigger points of doing this in the first place. I wish for my efforts to be comprehensive in hacking these games, and that's not something I can do without programming it into the project myself.

IN OTHER NEWS...

I've got a decompressor written up for Lemmings 2. I accidentally pulled a Nintendo and wound up using strncpy() instead of memcpy() in one spot, but found out what was going on during debugging. Making a raw data encoder was a trivial accomplishment, so the next step is graphics. I'll do that tomorrow, though... Been staring at hex numbers all day.

[ccexplore]

Oh okay, well, to each his own.  I personally find pklite to be an obstacle rather than an enjoyment, but hey, clearly someone somewhere had to have cracked pklite themselves to come up with unpklite in the first place, so if that's your cup of tea, go for it. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />

Just remember that when/if you do get tired of it, and you're still philosophically opposed to using unpklite, remember what I told you about examining the memory after the program has run--let pklite unpack the program for you.  (Not sure where that falls under your philosophy......)

I accidentally pulled a Nintendo and wound up using <snip>

I have to admit I never heard that expression.  What debacle of Nintendo's is the expression specifically referring to? http://www.lemmingsforums.com/Smileys/lemmings/huh.gif" alt="???" title="Huh?" class="smiley" />

[Simon]

Dear holy knight of the char*, you realize that re-solving the known stuff again (compressor algos?) might cost you precious time, which you might use hacking on something all-new for the community instead. You choose to hack Lemmings games after all...

I've written DAT decompressor code, with using the available docs. But it was just because the existing tools were either under the GPL or the ask-ccexplore license, both too restrictive for a http://sam.zoy.org/wtfpl/" class="bbc_link" target="_blank">WTFPL project.

Good luck on L2, I'm looking forward to your results.

-- Simon

[GuyPerfect]

I have to admit I never heard that expression.  What debacle of Nintendo's is the expression specifically referring to? http://www.lemmingsforums.com/Smileys/lemmings/huh.gif" alt="???" title="Huh?" class="smiley" />

Looking up what happened in the first place, it seems my recollection was a bit off. Nintendo's fluke happened with using strcpy() instead of strncpy(), but the resulting bug was still because of assuming 0x00 as a null terminator.

What happened is that people loaded up their Twilight Princess save file in a hex editor and changed the name of their horse to something that didn't end with 0x00. The game loaded the horse's name with strcpy(), which doesn't check the length of strings, and the result happened to end up as a stack overflow. While I'm not intimate with the coding of the game, I'm aware that this enabled hackers to execute their own code from the SD card, which was how homebrew on the Wii was originally made possible.

My bug came from the behavior of strncpy() in that any "copied" bytes after a null terminator are simply padded up with 0x00 to fill the destination buffer. It ended up making 00 00 9F get copied into a new buffer as 00 00 00. memcpy(), on the other hand, will copy all bytes intact.

Dear holy knight of the char* [...]

That's high lord of the unsigned char*, thank you very much. (-:

[Dullstar]

Well, good luck with that...  If you CAN program something like a level editor...  Video Games Board time!

[geoo]

A lemmings 2 editor? Oh wow, that would be asbolutely amazing if you made one and I'd probably get back into level editing if that were the case.

I love your enthusiasm; I'm not sure whether you were active when I released that provisional Lemmings 2 editor, so just in case not, if the price you are willing to pay for editing levels is high enough (i.e. a user unfriendly interface, having to decompress files first, setting the skillset with a hex-editor), you might try http://henriwatson.com/lemmings/index.php?topic=361.0" class="bbc_link" target="_blank">this as a temporary solution - with the afore mentioned issues.

(I intend to start learing to use Qt till the begin of the next semester, and might try re-writing this as an exercise for it. But hopefully anything of that will be made redundand by whatever GuyPerfect will be able to come up with.)

(And finally, sorry for sort of hijacking this thread.)

[GuyPerfect]

Sorry for the delay. Every couple of years I get the Paper Mario bug and just have to play through the Nintendo 64 title again. They just did so many things right in that game that it's one of my favorites.

Anyhow, I've got the level data partially decoded... it's actually more than it looks, but things like palettes and tile pixel arrangements go on behind the scenes and you can't really see how much work that was just by looking at the pictures. But whatever the case, I can now output images of the levels sans steel blocks, water, special objects et al. This is just the normal terrain.

Behold!

What I've decoded:
http://perfectkiosk.net/lemmings/HackinGood.png" alt="" class="bbc_img" />

The original:
http://perfectkiosk.net/lemmings/levels/l2/Classic03.png" alt="" class="bbc_img" />

Check out those extra tiles on the top and bottom. Intriguing, no? It's always fun to hack levels in video games and see just how much unnecessary garbage there is in the level data that's usually leftovers from level creation. Lemmings 2 is certainly no exception. See all those blocks making up the floor and walls? In the final version of the level, those are steel blocks. Yeah. So them being there is just taking up file space, as the level would play just the same without them.

Take special notice of the few blocks jutting out the top, because they're there for a reeeeeeeally interesting reason. Notice how they graphically connect to the pixels below them? The level designers had pre-set blocks and said "I want a vertical block right about there, going off the top of the screen." The upper part of the vertical block is still stored in memory, though.

Now get this...

The levels, much to my surprise, are not built of these pre-set blocks. They are explicitly defined on a per-tile (in this case, 16x8 pixel) basis. ALL the extra tiles that you'd never see can easilly be removed to allow the data to be compressed more.

Having said that, we seem to be very fotunate in this case. Turns out the developers left those pre-set blocks in the game for us to use! They're completely unnecessary for the program to function, and indeed only waste file space in the end, but they're defined in the STYLES directory and we'll be able to use them in our own levels without doing the work to reconstruct them ourselves.

With those pre-set block definitions, I'll be able to make the editor run a pass through the decoded level data and match up applicable tile combinations with the presets to make level editing MUCH easier. As it is, it's just a grid of 16x8 tiles, and that's not easy to edit at all. If I can do the math backwards and turn those tiles back into block presets, we can move them around just like the level designers did when making the levels in the first place.

This is a rather exciting turn of events that I wasn't expecting, but I am very much interested in making it work. Oh yes, and rest assured that when the editor I make outputs level data to file, it will remove extra tile information that isn't needed. (-:

[Dullstar]

I have a question...  are those blocks actually useless, or do the metal blocks function as visible steel areas (say, if the blocks hidden by the steel weren't there, would the lemmings just fall through?)

[Dullstar]

Sorry to double post, but I really don't think 16x8 tile grids would be hard to edit.  You should probably get it to work with the 16x8 tile grid first, and then update it to use the preset blocks.  It could allow for some interesting formations not possible with the presets (or not, it depends how they'd line up).

Have you gotten levels in any other tribes decoded?

[Pooty]

I have a question...  are those blocks actually useless, or do the metal blocks function as visible steel areas (say, if the blocks hidden by the steel weren't there, would the lemmings just fall through?)

The blocks really are useless because the Lemmings will interract with the steel blocks whether there is terrain beneath it or not. Shadow 10, for example, has some steel blocks that you are expected to stand on after you finish pouring glue, but there is no terrain underneath them.

[Dullstar]

Oh, has this been proven?  Ironically, both of the L2 levels mentioned in this thread today, I beat today.  Classic, I think 3, and Shadow 10.

Man, the solution for Shadow 10 was odd...  I NEVER would have thought of the piece of game mechanics used to solve the level.  I had no idea it was possible to use a builder as a platform for the glue from the glue pourer to function.  Well, if any other levels use that, I won't have to use the Lemmings Encyclopedia to find that out.