Here I Go Again!

[GuyPerfect]

You're writing the GUI from scratch (apart from relying on OpenGL)?

I built a cross-platform API for creating and managing windows and OpenGL contexts (as well as enabling the POSIX TPC/IP API and will get around to audio eventually) to run on Microsoft Windows and any installation of Linux running the X Window System. Because of this, any user interface stuff needs to be in my programming and cannot rely on system APIs to produce buttons or menus for me.

Being into algorithms, I can imagine writing a compressor fun as well; not having looked into it, from your description it sounds like Huffman compression?

Not Huffman. It'd be easier to just give you my notes than to explain what else it could be:

Code: [Select]

Data types
  String*X    A string consisting of X bytes. No null terminator.
  Byte        An 8-bit, unsigned integer.
  UInt16      A 16-bit, unsigned integer. Little-endian.
  UInt32      A 32-bit, unsigned integer. Little-endian.
  Type[]      Indicates an array of type Type. Size may vary.


Format specification

Element            Type        Size     Note
--------------------------------------------------------------------------------

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

Chunk
=====
Last Chunk Flag    Byte        1        Last chunk 0xFF; 0x00 otherwise
Symbol Count       UInt16      2        Number of symbol definitions
Symbol List        Byte[]      Count    Destination symbol names
Symbol Values A    Byte[]      Count    First byte of symbol
Symbol Values B    Byte[]      Count    Second byte of symbol
Data Size          UInt16      2        Number of bytes in encoded data
Data               Byte[]      Size     Encoded data bytes

--------------------------------------------------------------------------------


Remarks

There are 256 symbols at all times: 0x00 to 0xFF. Before decoding each chunk,
all symbols should be intitialized to one-byte values matching the symbol ID
itself. That is to say, the symbol with ID 0x00 should represent the byte 0x00
and so-on.

For each chunk, the Symbol List is an array of symbol IDs that will be
redefined before decoding the chunk. All symbol redefinitions come in two
parts, which are stored in Symbol Values A and Symbol Values B. Assuming
concatenation being represented with the + operator, then for each symbol X
from 0 to SymbolCount - 1:

  Symbol[List[X]] = Symbol[ValueA[X]] + Symbol[ValueB[X]]

The encoded data bytes are a list of symbol IDs to be copied to the output
buffer. Compression is made possible by the fact that the symbols themselves
can represent very large arrays of bytes.


Example

Consider the following data as a compressed file:

00000000  47 53 43 4D 0E 00 00 00  00 03 00 00 01 02 41 00  GSCM..........A.
00000010  01 42 43 01 05 00 00 01  02 44 45 FF 00 00 01 00  .BC......DEÿ....
00000020  01                                                .

The first four bytes, 47 53 43 4D, represent the string "GSCM" and the file can
be identified as a Lemmings 2 compressed file. The next four bytes,
0E 00 00 00, specify that the final Unpacked Size of the decoded data should be
14 bytes.

Since this is the beginning of a new chunk, we initialize all symbols.

The next byte, 00, indicates that this is not the last chunk in the file.
The next two bytes, 03 00, specify that there are 3 symbol definitions in this
chunk.

Symbol List becomes     00 01 02
Symbol Values A becomes 41 00 01
Symbol Values B becomes 42 43 01

Symbol 00 is redefined as Symbol 41 + Symbol 42, which is 41 42
Symbol 01 is redefined as Symbol 00 + Symbol 43, which is 41 42 43
Symbol 02 is redefined as Symbol 01 + Symbol 01, which is 41 42 43 41 42 43

The next two bytes, 05 00, specify that there are 5 bytes of encoded data:

00 02 01 44 45

Symbols 00, 02 and 01 are defined as above, which results in the following
being written to the output buffer: [41 42] [41 42 43 41 42 43] [41 42 43].
Symbols 44 and 45 are still initialized to 44 and 45 respectively, which means
only 44 45 is copied to the end of the output buffer to create the following
output: 41 42 41 42 43 41 42 43 41 42 43 44 45.

This is the end of the chunk.

Since this is the beginning of a new chunk, we initialize all symbols.

The next byte, FF, indicates that this is the last chunk of the file. The next
two bytes, 00 00, specify that there are no symbol redefinitions in this chunk.
The next two bytes, 01 00, specify that there is 1 byte of encoded data:

01

Since Symbol 01 was initialized at the beginning of the chunk, it no longer
contains the data it did in the previous chunk. Its current value is simply 01.

This byte is written to the end of the output buffer, creating this final data:

41 42 41 42 43 41 42 43 41 42 43 44 45 01

This is the end of the chunk.

This is the end of the encoded file.

Since this is 14 bytes--the same amount specified in the file header for
Unpacked Size--we can assume that the file was decoded correctly.

[GuyPerfect]

Hey Spaminator... I know this forum system isn't particularly verbose, but you've got a PM. I am in need of your brainpower.

[Dullstar]

Uh, where did I get the idea there wouldn't be a problem?  *smacks self in face*

By the way, the way you say you're writing the GUI, I would expect the following OS's to be able to do it:

Linux
Mac OS X
Windows
*BSD systems?
ReactOS?

Some have question marks by them, meaning I'm not entirely sure.

[ccexplore]

It's quite impressive how much progress you've made in such a short time.  I was rather worried when you said you'd put "figuring out pklite" ahead of other stuff that progress on the actual editor programs would be more, well, glacial, but looks like at least for Lemmings 2 this isn't the case.  Keep up the good work!

Those are, by definition, part of the development process. I have no intention of making either of those public.

It depends on how exactly you define "alpha/beta" (such designations make more sense when you actually start with some sort of feature spec of the final product as they do in the commercial software business), but while it's a waste of time for everyone involved to release something to the public that crashes half the time, at a certain point, it would probably be more efficient to shift some of the testing effort from yourself to the general public, or at least to a larger number of users than 1.

[ccexplore]

The editor will show things like water and flames animating while you're editing. What you'll look at is for all intents and purposes what you'll play when you load up DosBox.

Hey, that's a nice touch. Lemmix and other level editors do look rather lifeless...

To be fair, Cheapo's level editor also animates the water etc.  I do wish more level editors do that, because it's the only way to accurately assess how those objects would look with the surrounding terrain.  Even when there's a playtesting feature, it can still be inconvenient when you're still in the middle of doing things like shifting terrain pieces etc.

LemEdit doesn't do it probably because it was designed for an earlier time with lower-end PCs, and Lemmix, well, it was only written to the point where it's functional for what Eric set out to do, so there's clearly plenty of room to improve.

[ccexplore]

Not Huffman. It'd be easier to just give you my notes than to explain what else it could be:

This reminds me, it would be really great if you can release all or most of your notes on all the stuff you've discovered about level file formats etc.  While someone like you might not want such notes, I hope you can appreciate that there are a lot of other people that would.

[ccexplore]

The sorry loser who coded the STYLES decoder was either drinking heavily, high on some kind of substance, or most likely some obscure combination of the two. <snip>

I don't know the details of the tables you're referring to, but it's quite possible that the "pointer table with number of entries" was originally programmed for use by the editor used by the developers of Lemmings 2.  In the context of level editing, knowing how many tile entries are in any single table can be useful if, say, they want to display the full list of tiles for "one style" or something in a toolbox window or similar.  In the context of the game itself however, it might not need to care about such groupings of tiles, and therefore has no need to respect the number of entries in each pointer table (ie. it most likely just loads all the tables as one array and work off that).

Not knowing the history of how a piece of code came about, I personally would refrain from calling the developer a sorry drunk loser even in jest, but meh.

[GuyPerfect]

It depends on how exactly you define "alpha/beta" (such designations make more sense when you actually start with some sort of feature spec of the final product as they do in the commercial software business), but while it's a waste of time for everyone involved to release something to the public that crashes half the time, at a certain point, it would probably be more efficient to shift some of the testing effort from yourself to the general public, or at least to a larger number of users than 1.

The alpha stage of development is when the software is a work in progress by the organization creating it and isn't at a point that would be considered for release. The beta stage is when the product is considered more or less finished and is distributed to a group of people for testing, who then provide feedback in the form of opinions and bug reports.

I have a few people in mind to help with the beta phase, but I just meant I won't be releasing that build or builds to the general public, so you guys (the general public) will need to wait a little while.

This reminds me, it would be really great if you can release all or most of your notes on all the stuff you've discovered about level file formats etc.  While someone like you might not want such notes, I hope you can appreciate that there are a lot of other people that would.

Fret not, for I do not consider hacking notes profane in any sense of the word. I just ignore the work of others when I feel like doing it myself... That said, I fully intend to release full documentation as it pertains to what I've found in my hacking sessions.

I don't know the details of the tables you're referring to, but it's quite possible that the "pointer table with number of entries" was originally programmed for use by the editor used by the developers of Lemmings 2.

What happens in there is that there's a table with two-byte tile counts, and each tile ID is 2 bytes. Something like this:

03 00 - List 0 tile count
12 34 - Tile 0
56 78 - Tile 1
9A BC - Tile 2
02 00 - List 1 tile count
98 76 - Tile 0
54 32 - Tile 1

That's basically what's in the STYLES directory. Now, in those same files, something might reference that very table with the value 06 00... which refers to Tile 0 of List 1... Huh? That 0x0006 is to be interprated as the data offset in those tile lists without the tile count values in the data. Indeed, if you snipped that 03 00 and 02 00 out of the picture, the byte at offset 0x0006 is the first byte of the tile ID for Tile 0 in List 1.

Granted, this doesn't mean anyone's cognition was incapacitated, but even the game's own decoder has to handle that mess, which makes me wonder exactly what was going on upstairs. Then again, they shouldn't be expected to make things easier for hackers, but that's not the point. (-:

[GuyPerfect]

Got another progress report as I'm working mid-build, here.



While this image looks more or less like the last one I posted except with the level picture in the middle and the white pixels replaced with grey pixels, there's actually been a lot of work done behind the scenes:

• All tiles and level objects reference each other in a linked list. This allows new elements to be added, or existing elements to be reordered or deleted without manipulating big arrays of data. Easier to code, and easier on the processor.
  
• The OpenGL code was optimized a bit. Though it doesn't look it, the pixels drawn to the screen are in a very real way the representation of textured, 3D polygons. I've got all tile graphics loading into individual textures, then the textures being mapped to little 16x8 rectangles when drawn to the screen. The optimization uses what's called a display list, which basically stores the drawing instructions in graphics memory so that I don't have to make the program interact with the graphics card every time a vertex needs to be sepcified. Now, I just need two lines of code: Use texture X, and draw it.
• Obviously, graphics and levels can be loaded from file and decompressed.
• Zoom functionality is implemented. Levels can be drawn from 1x to 8x, though any factor is possible. I don't suppose anything more is necessary.
• This build cycles betwen the Classic levels. Don't have to stare at just one anymore. (-:
• Clicking and dragging anywhere in the window will pan the view around. Useful for when the zoom causes parts of the level to go off-screen.
• Those dotted lines represent the level boundaries. I'm working on those right now. You'll be abl to click and drag those lines to make the stage bigger or smaller.

.
Well, back to work. I have things to code!

[Dullstar]

Well, eventually I hope you release a demo before it's done.

[GuyPerfect]

It's almost done as it is. It'd be kinda pointless to release a demo.

Basically you just drag graphics onto a grid. It isn't any more involved than, say, arranging your desktop icons. I've been taking a brief break from programming, but the project as a whole is a very minor undertaking.

[Dullstar]

ALMOST?!   
Awesome...  can you give a progress report?

[GuyPerfect]

Imagine the image above, except that you can resize the stage, reposition the default screen coordinates, and write levels to file. I'm finishing up the code that lets you select, move and delete existing elements and add new ones. It's all boringly simple and merely takes time to do, and once that's done, it'll be a fully-functional level editor/creator.

Although, using the keyboard to determine which objects and tiles to place isn't the pinnacle of user-friendliness, so there will be another little branch of the project to take care of before releasing it. There are two windows to implement, yet. One for the open/save features, skills and starting new levels among other things... and one for selecting objects and tiles to put in the level. Neither is difficult, and neither will take very long.

Also also, I wish to design and implement a custom file format for storing custom levels that will add a layer of abstraction between the user and the actual game data files, provide for distribution of whole level packs, etc. Another one-day project.

Though like I said, progress doesn't move forwards very fast while I'm taking a break. (-: To be honest, I haven't worked on this since Friday and had I been, I'd probably be done with everything mentioned in this post by now. I was approaching the legendary "project burnout" since every step up had another step in the way before I could really do anything with what I was making. I've learned over the years that if I just take a few days to forget all about whatever I'm working on, it's so much more entertaining when I get back to it.

Just before logging on right now, I wrapped over the story from Paper Mario: The Thousand-Year Door and got into the little "do whatever you want after you beat the game" phase. Normally I'd call it quits here, but there's still something I've never done... I'm gonna beat Bonetail, which is the game's optional super-boss that makes even the final boss look like easy beans. But since the final boss was easy beans (two Power Plus badges, P-Up D-Down, Jumpman, Soft Stomp and Rally Wink make for a good 40 damage to the enemy every turn), I doubt it'll take me very long.

Once I'm done with Bonetail, I can put the game back in its box for a few years and get back to work on my Lemmings project. (-:

[chaos_defrost]

I'm amazed at how quickly you can implement each stage of this project, and how easy it seems for you.

Very much looking forward to this once it is released!

EDIT: Also, as a Mario fanatic, Bonetail isn't that hard if you take proper precautions first. If you have the item that allows you to hold 20 items instead of 10 (at floor 50 of the Pit), it's even easier.

[GuyPerfect]

Yup, I went in and got the Strange Sack before heading to the Glitz Pit the first time around. I hate the 10-item limit. Though I went in thinking it was at level 20... Well, I stuck it out anyway. Wasn't too tough.

Bonetail's dead, too. As is Ms. Mowz... Sad story, really. I told Mario to use an item, but he turned around and stomped his mousie teammate for a good 8 points of damage. The battle was much more interesting than the Shadow Queen at the end of the game. It wouldn't have taken so long if I wasn't confused all the time, but it turned out alright. Went through three Zess Deluxes and five Jelly Ultras, but only one Trial Stew! So now that I have the Return Postage badge, I can delete my save file and put the game away for a few years. (-:

Guess tomorrow is back to work on Lemmings!