Best way of rendering Lemmings levels?

Started by covox, July 17, 2006, 03:21:31 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

covox

Hi all. I'm working on a clone in Python. As most of the internal data structures, global caches etc. have been written, I'm up to the bit of making the graphics start to work (the gui and the playfield, essentially). However, I'm a bit puzzled as to the correct order of adding terrain pieces onto a freshly-made playing field.

In my current system, I thought I had it nutted so that I only had to blit (simply put, pasting an image onto another) images, and not in reverse - that is, paste an image right behind another. For terrain pieces, this meant going through each piece in order, and either rendering it to a canvas if it was ordinary/black, or adding it to a list if it had the No Overdraw flag set. Afterwards, it reverses this list, renders these pieces in the new order to a second canvas, then blitting the first canvas on top of the second.

And it worked, in a roundabout way. Until I saw what happened with "If only they could fly"



For reference, here's how it should look:


After some thinking, I think the proper method of doing things is "go through pieces in order, if No Overdraw is selected simply blit underneath surface instead of on top".

This might account for really weird situations caused by the subtractive terrain handling, such as how a visible terrain piece can be in front of another visible terrain piece, yet with some layer changing the frontmost piece can be wiped out by a black piece stationed behind the two without affecting or appearing behind the second one.

Is this rendering philosophy correct? Also, is there a neater way of blitting images behind one another than, say, "take sample of the area about to be changed, position terrain piece on an area of the same dimensions, blit the sample area over the terrain piece, clear the changed square on the main image and blit in the new sample".

ccexplore

Quote from: covox on July 17, 2006, 03:21:31 PMAfter some thinking, I think the proper method of doing things is "go through pieces in order, if No Overdraw is selected simply blit underneath surface instead of on top".

Yep that's correct.̆ Your original two-canvas idea falls apart in the presence of subtractive pieces.̆ For example, say we have terrain pieces A, B, C, with A and C No-Overdraw and B black.̆ B only affects A, not C.

If you want to keep your two-canvas system, you will need to treat black pieces by saving partial results.̆ For example, say we have A,B,C,D,E with B and D black, and the rest No-Overdraw:

1) For the bottom-canvas list, you need to include black pieces as well, so the list you have after reversing is E,D,C,B,A.

2) Draw E on bottom canvas.

3) Since D is black:̆ capture the current pixels on bottom canvas which are in the subtractive area of D.

4) Draw C on bottom canvas overwriting.

5) Since B is black and there was previously another black piece (D):̆ draw the capture from D over the canvas.̆ This will erase everything except E, since we saved pixels of E during step 3.  Another way to look at this is that instead of every subtractive pixel of D being black, the ones that overlap with E, you apply to the canvas the capture (which has E's pixel) instead of blackness.

After this, capture the current pixels on bottom canvas which are in the subtractive area of B, similar to step 3.

6) Draw A on bottom canvas overwriting.

7) We reached the end of list and there was an unhandled capture from step 5, so handle it by drawing the capture from B over the canvas.̆ This will erase everything except C and E, since pixels from those were saved during the capture in step 5.

Note that I haven't tested this, this just came straight off my head right now.̆ I think if the simple approach of always drawing No-Overdraw pieces behind existing terrain is fast enough, you should use that approach since it's guaranteed correct, easier to understand and therefore less likely to have bugs.

covox

Aha. Cheers for the info. Method 2 seemed the simpler one in principle, I just felt that writing a specific method to blit objects behind was somehow sacriligeous (needing four blits instead of one! FOUR!).

I wish I knew how to do proper masking. Pygame doesn't seem to have anything in the documentation mentioning a right or wrong way (not sure how it was originally done, but my subtractive terrain handling takes unfair advantage of how an RGBA canvas can also have a transparent colourkey)

I'll say bon voyage to the two canvas system, which was at best slightly hackish. Hopefully the new method won't be too burdensome on the CPU :undecided:

STT

*unrelated*

Covox, are you running Lunix? Those screens look very lunixy.

0xdeadbeef

Quote from: covox on July 18, 2006, 12:57:16 AM
Aha. Cheers for the info. Method 2 seemed the simpler one in principle, I just felt that writing a specific method to blit objects behind was somehow sacriligeous (needing four blits instead of one! FOUR!).
Rendering the level is quite a CPU burden since some things have to be done on a per pixel base. Then again, you do it only once and before the level is actually played. So it shouldn't be a problem.

Quote
I wish I knew how to do proper masking. Pygame doesn't seem to have anything in the documentation mentioning a right or wrong way (not sure how it was originally done, but my subtractive terrain handling takes unfair advantage of how an RGBA canvas can also have a transparent colourkey)
The original versions used a paletted color model, so there was no alpha transparency. Instead there is a transparent color index used to decide whether a pixel of the background image is a "brick" (Lemmings can walk on it) or not.

Be aware though that you might need a "collision stencil" anyway, depending on how you realize rendering, especially one-way bricks (arrowed bricks), traps and animated objects. At least I use one and I know the original game used one (though somehow different from my approach).

Quote
I'll say bon voyage to the two canvas system, which was at best slightly hackish. Hopefully the new method won't be too burdensome on the CPU :undecided:
As I said - this should be no issue since the level is only rendered once.

BTW: why is everybody starting his/her own Lemmings remake now? Is this only the PSP success?

Mindless

Quote from: STT on July 18, 2006, 05:41:21 AMCovox, are you running Lunix? Those screens look very lunixy.
Linux... but I agree, it looks quite gnome-ish.

covox

Quote from: Mindless on July 18, 2006, 12:32:45 PM
Quote from: STT on July 18, 2006, 05:41:21 AMCovox, are you running Lunix? Those screens look very lunixy.
Linux... but I agree, it looks quite gnome-ish.

Very perceptive :laugh: Yep, that's Ubuntu Dapper, running GNOME + the brand new whizbang OpenGL eyecandy layer. With the world's greatest music player in the background :winktounge:

Quote from: 0xdeadbeef on July 18, 2006, 08:59:46 AMBe aware though that you might need a "collision stencil" anyway, depending on how you realize rendering, especially one-way bricks (arrowed bricks), traps and animated objects. At least I use one and I know the original game used one (though somehow different from my approach).

Sounds very similar to my current plan, which was to have a seperate offscreen surface the size of the playfield, and organize the RGB values in such a way to reference stuff like ground, steel areas, trap + object number etc, with allowances made so multiple values can coexist (so going under the assumption that if two interactive objects are around with overlapping hotspot rectangles, the frontmost one gets priority). The only alternative I can think of is having lots of rects for each specific area and polling each lemming, but that would require a metric arseload of comparisons compared to 1.

Quote from: 0xdeadbeef on July 18, 2006, 08:59:46 AMBTW: why is everybody starting his/her own Lemmings remake now? Is this only the PSP success?

As corny as it sounds, I've been stewing over ideas for one long before I heard of Lemmini or the PSP remake, and it gets easier to develop as the more tedious stuff is pushed out of the way.

Somewhat off topic, has anyone ever had a crack at extracting the high-resolution graphics from Mac Lemmings? I only got as far as writing a tool to parse the resource fork before giving up at the ominous-looking packing format.

ccexplore

Quote from: covox on July 18, 2006, 04:37:47 PMSomewhat off topic, has anyone ever had a crack at extracting the high-resolution graphics from Mac Lemmings? I only got as far as writing a tool to parse the resource fork before giving up at the ominous-looking packing format.

No, but then again not many of us use Macs.  The fact that you have a way to parse the resource fork is already a good step forward to the rest of us with file systems that don't normally use forks.

Given the ease at which Volker Oth cracked WinLemm's graphics format, perhaps cracking the Mac format is not far behind (though it's most likely not identical to WinLemm's).  Anyway, if you make the parsed resource fork available as a bunch of files maybe someone here will make an attempt at it.  Just maybe......

0xdeadbeef

Quote
As corny as it sounds, I've been stewing over ideas for one long before I heard of Lemmini or the PSP remake, and it gets easier to develop as the more tedious stuff is pushed out of the way.
Well, it's at least a year ago or so that I began researching in Lemmings topic. At that time, nobody spoke about the PSP version or other remakes and nothing was known about the SPR format. And now, in a few weeks, three more remakes are announced. Well, whatever.

Quote
Given the ease at which Volker Oth cracked WinLemm's graphics format, perhaps cracking the Mac format is not far behind (though it's most likely not identical to WinLemm's).
But I was pretty motivated then, didn't waste my time with Oblivion and the temperature in my appartment was about 10 degrees lower ;)

covox

Old Mac files have two independant halves: the data and the resource fork. The resource fork is a sort of compartmentalized treasure map that's bolted onto most old Mac files. It provides a standard way of holding standard structures (like colour palettes, dialogs, machine code) and also for referencing information packed in the data part of the file.

This actually makes the data part of the file quite underused, as it's easier to keep most things in the resource fork. (The Lemmings executable, for instance, is just one large resource fork). Which, unfortunately, is a bit of a pain, as by default the resource fork is sheared off on a non-Apple filesystem.

Thankfully by packing the Mac files into a data-only format (in my case, BinHex .HQX files), it is possible to read both the data and resource fork on any platform. Of course, the resource fork is only read by the Apple system libraries and developer tools like ResEdit, so it doesn't look very nice as one long string.

Right now my tool just converts the above gibberish string into a more human-readable data structure. So it's only really useful if you're extracting data or poking around for information.

The executable has a little bit of useful information (such as the single colour palette used by Lemmings), however the Graphics file is much more cryptic. All the resource fork contains is a single table of 12-byte tuples, flagged with interesting names like "Psygnosis0", "Logo0", "Grounds1", "Special2" etc. I think the first 4 bytes references an offset, second 4 bytes references a length (all referring to the large data part of the file), but I have no idea what the last 4 bytes represent. Presumably it is an amount, as the highest two bytes always represent a small number, but it doesn't steadily increase/decrease down the list and it's always larger than the image size. As for the graphics data itself, all I know so far is that there is the occasional raw palette index, making it possible to identify sections of the image in a paint-by-numbersish way.

If anyone out there is mad enough to try it, you don't even need a real Mac to check out Lemmings with ResEdit (Basilisk II, a starter kit and a copy of HFV Explorer will do the trick).

covox

Aha. Wrote the new method and found out that the problem was fixed by  changing the colourkey to transparent immediately after each addition of a black terrain piece. And better still, it now uses one surface instead of four  :laugh: Thanks for the advice.

ccexplore

Quote from: covox on July 18, 2006, 04:37:47 PMSomewhat off topic, has anyone ever had a crack at extracting the high-resolution graphics from Mac Lemmings? I only got as far as writing a tool to parse the resource fork before giving up at the ominous-looking packing format.

I doubt anyone cares about this anymore, but I am currently taking a stab at doing just that through reverse engineering of Mac Lemmings code.  No promises though, as I'm much less familiar with Mac internals, and freely available documentation on Mac programming is sparse.