Fez PAK file Unpacker

I really like the game Fez for so many reasons and I am also the kind of guy that likes to take apart the things I like in order to understand them better.

This morning I decided to poke around at the data for Fez and see what I could discover.  As it turns out there are only like 3 files, large ones (~150mb), with the extension ‘.pak’.  For games, these large ‘.pak’ files are often used to collect many small game assets into large files, which has many advantages, such as easier distribution, faster loading, file system abstraction and patching.

Opening up ‘Essentials.pak’ in HxD hex editor, I saw the following:

Image

The abundance of strings was a good sign tipping me off that this data is not compressed in any way, making my job of extracting the files vastly easier.  The first thing I went after was the path ‘other textures\fullwhite’ since it seems like the name of the first file in the ‘.pak’ file.  The string was missing a null terminator, so the size must lurk somewhere else.  Preceding the string, was a singe byte 0x18, which sure enough matched the length of the string.  I now understood the name of each file in the ‘.pak’, but I still need to know the length of the file itself.  Scanning down the file, I can see what looks like the start of another entry, which is good, since it gives me an idea of the length of the first file.  The next file starts at 0xE0, so the length of the file must be smaller, and smaller still when we remove the size of the name and ‘.pak’ file header.  In total I expect it to be around 0xC0 in size, and sure enough after the string there is 4 bytes with 0xCB.

Its worth noting that any assumptions I make I am sure to verify by looking at other entries in the ‘.pak’ file and seeing if the rules I can see still hold tight.  In this case, they do!

I could write a program to start extracting data out of the ‘.pak’ file until it fall off the end of the file, but there will most likely be a way to find the number of files within this ‘.pak’ file.  Most likely it is at the start of the file, generally known as a header.  The rest of the file has been very simple so I wouldn’t expect this to be any different, the first 4 bytes seem suspiciously close to being a file count.

Below I have colored the hex view to highlight the interesting parts.  In blue is the file count.  Light orange is the string length.  Green is the file name and path.  Darker orange is the file size in bytes.  The data between two entries is the file data itself.

Image

It didn’t take long to code up a simple extractor for these ‘.pak’ files.  Some of the goodies inside are all of the stems for the music tracks stored as Vorbis (ogg) streams.  These have no file extension, but VLC is able to figure out how to play them just fine.  I will in time try to poke around at texture, trixel and the map data.

The source can be found here:  FezUnpack.cpp

An executable is here: FezUnpack.exe

Advertisements

Lode Storm – Implementing classic fog of war

Last night I couldn’t sleep, and one of the reasons was that my mind was busy trying to explore the problem of how to implement FOW in my game Lode Storm for this months 7 day mini Ludum Dare.  I got up again and at 1:30am set about solving this problem in a nice manner.  After about two hours, the results looked suitably retro and I had some fun designing a neat algorithm in the process.  Here is the result:

fogofwar

Any RTS game aspiring to the classics of the genre would not be complete without some Fog of war (FOW) effect.  Warcraft Orks and Humans is a game that very much rely on FOW, and has a great rendering style for it too.  I took this as my basis and set out to mimic the visual effect.

It is immediately obvious that in this case, the FOW is just another tile map, as an overlay to the main game map.  While each tile is either in fog or not (binary), some extra processing has occurred to make a visually smooth transition around the hard boarder.

The stages seem evident:

  1. Within the game logic update the binary FOW map
  2. Process the binary FOW map to derive a visual FOW map
  3. Render using the same process as a regular tile map

Stages 1 and 3 are quite clear and shouldn’t require much discussion.  Stage 2 is however much more illusive and I will show you how I solved that in just a moment.

For stage 3 we require a visual overlay that will be rendered with a transparency mask to provide a pixel dissolve effect for the transition.  I spent some time in Photoshop and knocked up the following map:

Image

All of the tiles needed for a complete FOW effect are there, and in fact there is a little duplication in the corner tiles, but that is not important.  In stage two we need to take the binary FOW map and through analysis of each game time, produce and index corresponding to a tile in this image.

For stage 2, a few ideas to explore came to my mind.  I remember coding up a demo that performed terrain analysis using a Sobel filter, a very similar operation, however that code was written long ago and is on an eternal hard drive I don’t have access to at the moment.  Browsing over the Wikipedia page, it wasn’t immediately clear to me how to approach the problem with a Sobel filter.  The second option that came to mind is to employ a variation of the Marching Squares algorithm.  I haven’t programmed anything using this technique before, however it has always been something I have kept in mind to try one day.

As I understood it Marching squares assigns a unique code to each tile based on the tile values sampled at each corner.  To clarify this point, for each corner of the a tile we set it to true if it touches any other tile that is in FOW, otherwise false.  The image below shows that if any of the yellow squares have their bit set in the FOW map, then the corresponding code will be set to true.  This can be done by summing each tile around the corners using a bit wise OR operation.

marchingsquarescode

Once these four Boolean values for the quadrants A, B, C and D have been found, we can proceed to produce the marching squares code.  This can simple be done by shifting and summing each of the bits, to produce 16 possible values.  Therefore the output value would be:

int out = (A<<3) | (B<<2) | (C<<1) | D;

The last step is to take the marching square code and use a translation table, mapping each marching squares code to a FOW image index.

In the end here is the code I came up with.  Please note that, ‘conv’ is the conversion table for the marching squares code to the image map.  In the current version of Lode Storm I used a modified version of the above FOW image, so it does not correspond to that.  You will notice that I perform a binary AND with 0x8, in the final step of my marching squares code computation, and this is because my FOW map is stored in one bit of a larger array of flags for each tile, so the 0x8 isolates only the FOW bit.

//
// tile byte flags layout
// 
//    0xF                  0x0
//    Z  L  0  0  H  C  W  E
//
//  0x80 - Z - tile locked for units    (unit on tile)
//  0x40 - L - lode locked              (lode on tile)
//  0x08 - H - human fog of war         (binary, not the aesthetic map)
//  0x04 - C - computer fog of war        " "
//  0x02 - W - water                    (block move not LOS)
//  0x01 - E - elevation                (block move and LOS)
//
//
//
inline int fog_getIndex( int x, int y )
{
    // marching squares conversion table
    uint8 conv[] =
    {
        13,  1,  0,  8,
         2, 13, 10,  4,
         3,  9, 13,  5,
        11,  7,  6, 12
    };
    // convenience
    uint8 *t = tile_flags + (x + y * 32) - 33;
    // surrounding squares
    uint8 q[ 8 ] =
    {
        t[00], t[01], t[02],
        t[32],        t[34],
        t[64], t[65], t[66]
    };
    // sum to find out quadrant values
    int a  = q[0] | q[1] | q[3];
    int b  = q[2] | q[4] | q[1];
    int c  = q[7] | q[6] | q[4];
    int d  = q[5] | q[3] | q[6];
    // turn into marching square code
    int v  = (a & 0x8) >> 0;
        v |= (b & 0x8) >> 1;
        v |= (c & 0x8) >> 2;
        v |= (d & 0x8) >> 3;
    // index conversion table
    return conv[ v ];
}

Additionally, there is one small omission from the code above.  If a tile has its FOW bit set in the FOW map, then it should immediately skip this processing and be set to straight black.  Tiles should only be processed using the above method if they are not part of the hard FOW.

Lode Storm – 7 Day RTS Compo

I have for the last few days been squinting in the dark at my monitor in the early hours of the morning.  I couldn’t resist entering this months Mini Ludum Dare since the challenge was to make a RTS game in 7 days.  An RTS game is something that I have always have wanted to make, from a technical point of view as much as anything.  I spent countless hours playing C&C, Dune2 and dungeon keeper in my childhood and the AI in this genre in particular always fascinated me.

My initial research on RTS AI directed me to some great papers written about potential fields and their use in the RTS genre.  This is a method I had read about previously, but these papers really gave me the vision for just how powerful they could be.  The papers can be found a the bottom of this great article at AIGameDev. http://aigamedev.com/open/tutorials/potential-fields/.

All the programming I had done on my framework is now being tested to the limit for this project, and so far (touch wood) it hasn’t failed me. Additionally, I am particularly proud of my efforts on this project because I have made all of the graphics myself from scratch and this really is my most complete game to date, since I usually get sidetracked while working on the technical details of a project.  Provided below is a screenshot of the current work in progress.  Several potential fields are being displayed for debugging by eye in the lower left corners.  Top left shows the fog of war maps for both the human player and the AI player respectively.

lodestorm

Binding Tiny C Compiler

Years ago I found a interesting library called TinyCC, which provided a simple and small C compiler with one major twist…  it can be embedded inside another application.  Because of this, a program can compile new functions for itself at run time and call them using function pointers.  In a sense it can be used like an immensely powerful scripting language, with the benefit that there is no speed hit due to interpretation or emulation.  Its weakness as a scripting language is that you have to account for portability and security problems due to the execution of these ‘scripts’ running as native code on the host processor.

So far, I have used TinyCC for a few projects in the past and recently in a texture generator as well as my text adventure engine.  The reason for this post however, is that TinyCC is not the most intuitive thing to embed into a windows application, so I wanted to take a moment to explain one clean method to do so.

There is no static library for use with visual C++ so that option is out, however since a fully compiled DLL file is included in the download package, it seemed that it would be easiest to dynamically link the DLL through code at run time.  This requires loading the DLL and requesting all of the functions that are exported from it which is a fairly easy operation on any platform and generally differnt OS’s have much the same interface for doing so. The only tricky part is actually specifying all of the annoying function pointer casts correctly during binding.

Without farther talk, here is some straight forward code to load TinyCC and bind the interface for you. Which I hope it should all be fairly straight forward and easy to understand.

libtcc_bind.h

libtcc_bind.cpp

Shadows and Gradients

Again, I have produced a small demo of the Tengu Engine as my own way of experimenting with what may be possible as it progresses along its development path.  While work is already under way on the hardware renderer, it still has not been integrated into the main code so this demo here still uses SDL for all of the rendering. What it shows is a top down perspective using a destroyed space ship tile set I made recently.  There are ray traced shadows as well as what I refer to as gradients, or distance based mask pattern selection, to give the illusion of light or visibility falloff, which is a technique somewhat similar to dithering I suppose.

Laying Out The Plan

Mocup1

I have been working on some tiles for this project today to help me define a more solid overall look of the game.  The task for today will be to update the engine to support custom maps and these nice tiles.  The water rendering is also coming along so I am hoping I can have these things integrated by tomorrow.

Also, something that I have rarely seen in a platform game is genuine AI companions that can join the player on their journey.  I guess this is in part due to the fact that it can be hard to create an AI that can navigate and jump between platforms properly, however I have devised what could be a great solution to this problem.

Raycasting For Fun And Profit

One of my ambitions for a while was to create my own efficient ray casting function which I finally managed yesterday, which is great news because ray casting has so many cool applications.  There are so many basic uses for ray casting, for instance, in line of sight detection in the field of AI, detecting the collision points when shooting bullets and importantly for my game, detecting where to attach grappling hooks.  More advanced uses could be in inverse kinematic routines, procedural animation systems or even, as I eventually want to try, Wolfenstein style 2.5D ray-casting engines.  With some extensions It should be possible to modify a ray-casting algorithm to perform somewhat naive Voxel rendering, which is something else I really want to try.  Ever since I played Voxatron, I have since fallen in love with Voxels and its on my large project list to make something simmilar.

Over the last few years I have studied a large number of ray-casting algorithm available on the web and read many websites on the subject.  I would be lying if I said I really understood all of the approaches I have seen to ray-casting, but it is clear that the efficiency of them varies quite substantially, and in this regard they are easily examined.

Perhaps the most understandable and readable tutorial for ray-casting I could find was here, in article by Lode Vandevenne.  On the face of it, his algorithm seems very efficient and he talk in detail about the efficiency and speed concerns, and even in the main loop there is no multiply or divides used.  However, in exploring the code we can see that to initialize a ray cast, two square route functions are called, which adds up when you consider that two called are made for each vertical column of the screen.  Thus even at 320×240, 640 square route calls are made in rendering one frame.  Square route calls can be optimized somewhat by approximation, or look-up tables, however this seems still like a weak point of the algorithm.

Another nice tutorial can be found here, written by F. Permadi.  In his tutorial he advocates mostly the same strategy as the above, but the formers square route calls are now replaced with a call to the tangent function, shown here.  This is more efficient, since the tangent function can easily be packed into a look-up table and accessed quite efficiently, just as I did for my sin wave approximation library.  Still this look-up costs space and has accuracy tradeoffs thus reducing the overall efficiency in other ways.

For my algorithm, I managed to avoid square routes and look up tables of any kind, in fact there are just four divides and six multiplies called for each ray cast, the rest being just addition and subtraction. The inner loop is entirely performed using addition and subtraction also, so the overall efficiency seems bloody high.  I do however test inside the inner loop to see if the ray has exited the map space, but if we can guarantee that a ray will hit a tile (such is the case, when the map is surrounded by tiles) then efficiency could again be dramatically increased by omitting these tests.  In the code below that I provided, you will find there is one multiply in each inner look, to perform the wall hit test, but this can be optimized away to equivalent addition and subtraction, as I have done in my own personal version.  In my scheme unlike that of Lode, I separate the ray cast into two stages, that of ray casting over the x-axis and next the y-axis.  Each of these steps may produce a hit, and at the end of the algorithm we can compare the squared distance to efficiently select the closest of the two hits.  I also break the ray cast through each axis into two parts, that for a positive increment, and that of a negative, since we can tailor the inner loop to be more efficient for each case.

I am sure this ray casting code will find loads of awesome use in Ninja Flare as well as my other projects.  I also need to find a better name for the game, other than Ninja Flare, which was chosen quickly for the deadline of Ludum Dare.

Source Code:

raycast.cpp