Huffman Coding – Compression results

Before the Christmas break I started writing a encoding/compression library based on a technique called Huffman coding. I’ve since completed and tested the encoder and decoder, today we’ll discuss the results of several compression tests in comparison to the RLE encoding technique. Here are links back to the posts for Huffman Coding and Run-Length Encoding.

So I’ve collected a few different types of data files with different characteristics. First up is a MS-DOS executable, these binary data files typically don’t contain runs of data and will tend to contain most if not all symbols. Next is a ASCII text file, which will typically only use alphabetic, numeric and punctuation characters. Lastly a small number of graphics files, in raw bitmap form, these particular images are fairly basic (only a handful of colours).

Here’s a table showing the results.

You’ll note that the Huffman encoder achieves better results in every example! The worst result for it being the MS-DOS executable, which is of course expected. I was pleasantly surprised that the small graphic files compressed quite well, this is likely because of how few symbols are in these files. If there had been a large variety of symbols the dictionary and the encoded data would be much larger.

Run-length encoding was obviously much worse, and in the case of ASCII text and executable data it actually increased the size of the data! Knowing how it works this is hardly surprising. I did expect RLE to perform better than Huffman coding for the graphic data, but I suspect the low colour count in these files is an influencing factor.

So I thought I’d create a graphic data file that had a higher colour count that would favour RLE to see if it can do better under specific conditions. The graphic data I created is a sprite 32×32 pixels with horizontal coloured stripes, each a unique colour. The size of the raw file came out at 1026 bytes.

The Huffman encoder produced a file of 766 bytes and the RLE produced one of 68 bytes! Whilst the Huffman encoder still managed to compress the data, it couldn’t match the best case scenario for RLE.

There are good reasons to use both compression techniques. Run-length encoding doesn’t require much CPU power to encode or decode, so it can be done on very weak machines (even old 8-bit machines), but it only compresses data with many runs in it well. This turns out to be useful for graphics and level data. Huffman coding will pretty much always reduce the size of the data encoded, sometimes significantly, but it is much more complex. It requires more RAM and CPU power to achieve this result, so it can’t be used on every machine, although most modern processors would have no trouble at all.

I’ve made the code for the Huffman encoder/decoder available in pascal for download. be aware the encoder still has some debug code in it that will write to the screen.

Xerix for DOS

The past week here the temperature has been hot, very hot. When it’s over 40 degrees every day it’s difficult to do much more than rest under a fan, unless of course you have air conditioning. Not even playing a computer game is on the books when it’s that hot, but luckily a cool change came through recently providing relief, so today I took the opportunity to play a game which is called Xerix.

Xerix was made in 1992 by Brenden Reville who at the time was 15 years old. It is probably one of the better examples of a teenage-made home-brew game. Whilst not being up to the same standards of commercial or professional shareware from the era, it does have some decent features, partly due to the libraries used in its development.

The Xerix Story

The graphics support is VGA in both colour and monochrome (64 level grey-scale). Obviously the colour graphics are better, the grey scale graphics suffer from objects being difficult to differentiate. I’d say it simply uses a graphics filter rather than having a separate graphic set. In terms of artistry the graphics are quite good, with nicely drawn sprites and animations, although within each level there isn’t a whole heap of variety.

The sound system supports PC Speaker, Ad Lib, and Sound Blaster devices. Sound effects are fairly basic, but the music is much more developed. It’s not amazing, but reasonably good, it is played during the title and story sequences but not during levels oddly.

The first Boss

The game-play is probably the part that could have used the most work. The controls work quite well, but the enemies are quite simplistic. There are two basic enemies, a ball that bounces up and down the screen towards you (sometimes at speed) and stationary turrets that shoot along the diagonals.

Yet more story…

The bouncy balls move exceptionally quick and seem to have a random initial speed and angle. They move so fast that it is often a matter of luck whether you’ll be able to dodge them or not. The turrets behave much more reasonably, being much easier to avoid shots. However the graphic for the turret isn’t obviously one and is used in places where no turret is programmed into the level.

Balls!

There are only two levels, each ending with a boss, which are both essentially balls that move extremely quickly in a pattern. The only danger they offer is collision with them, so once you work out the pattern they aren’t terribly hard.

The Second Boss.

Unfortunately this is another game where one hit results in your death, and it will happen frequently. Enemies that are destroyed remain on screen for a moment whilst they explode and remain dangerous whilst they do. If you play in the expert difficulty level you only get a few lives (with no feedback about how many) so you don’t last long, but luckily there is a Novice difficulty level with unlimited lives.

I know it sounds like I don’t think the author did a good job, but I’m holding the game to standards of game-play that we’d expect from a professional developer, as most people playing it would. The truth is it’s really quite a good effort for a 15 year old high school student, some-one who would be new to making games.

Victory!

Something that does shine as quite exceptional is the technical aspects of this game. The graphics animate and scroll smoothly and the sound system performs quite well. Normally it would take quite some time to write the code needed to drive the graphics and sound, but the author has opted to use some external libraries, in this case Fastgraph and the Creative Labs developer kit. I think that this was a good idea, as it must have saved development time and allowed more effort to be put into the art for the game. This is generally the norm for games developed with modern tools.

Death!

Whilst this isn’t a game you’d play and enjoy on the same level as a commercial or shareware release, it is exceptionally good for a home-brew game made by a student. You have to remember that little information about game programming was readily available and making this would have taken considerable effort.

 

 

This slideshow requires JavaScript.

Xatax for DOS

Today’s game is called Xatax and is a shoot-em-up made in 1994 by a company called Pixel Painters. I hadn’t heard of them before which is unsurprising as they only made 3 games during the MS-DOS era.

The story in Xatax is fairly simple like most shooters. Humanity disarms after many years of peace and is attacked by something not surprisingly called the Xatax. It absorbs the biomass and materials of anything it encounters and adapts based on the knowledge it acquires in the process. Humanity restores a star fighter stored in a museum so you can fight back.

The game supports VGA graphics and has some quite good art, the artist favouring the use of gradients quite a bit. The animation and scrolling seem to be implemented nicely and move smoothly with no flicker. The sound system supports Adlib, Sound Blaster and Sound Blaster Pro cards utilising FM synthesis rather than digitised effects. The music sounds quite decent, but is a little repetitive whilst the sound effects are fairly simple.

Running the gauntlet

The controls work quite well, although if you don’t get the rapid fire upgrade you have to mash the fire button quickly to achieve a good rate of fire. The power-ups come out of enemies when destroyed and come in a few different flavours which are picked randomly. This can be a blessing and a curse as you might get a good power-up early on or ones which don’t help all that much. The missile power-up is probably the most useful.

Missiles FTW!

When you collide with an enemy or the scenery you’re destroyed straight away and if you’re hit by a projectile you lose one of your power-ups and are destroyed when you have none. This in combination with the rarity of power-ups means you’re usually destroyed in one hit which makes the game quite punishing. It does have the option to change the difficulty level, but that only seems to change how many shots are required to destroy enemies.

Big O’s!

The main obstacle in the levels I’ve played are mostly defensive guns fixed to the scenery of the level. They shoot at regular intervals so you can get through their line of fire if need be, but it’s usually better to destroy them if you can, especially where there are a number of them. You can use a bomb to destroy everything on screen if you’re in real trouble, but like the power-ups there aren’t that many bombs to pick up.

Xatax is mostly fun, but punishing when you make any kind of mistake. I would have preferred a shield or energy system so I could keep the power-ups. I found it difficult to get through many levels because of how many times I died. Progress is difficult to make which can lead to the game being a little repetitive. It’s not bad by any means, just not as good as it could have been.

This slideshow requires JavaScript.

Another Belated Xmas Post: Holiday Hare 1995

Christmas time was particularly busy this year for me. Just managing to get all the shopping and family stuff done alone whilst my partner continued to work took up most of my time. Now having finally some time to rest and take a holiday from the holiday I can write the first post for the new year.

Over the Christmas break I did manage to find some time to play a Christmas themed DOS game. This time it was Jazz Jackrabbit Holiday Hare 1995. Obviously it will have much in common with the original shareware Jazz that I played last year.

The graphics and sound are of the same level of quality as the shareware game, that is to say the graphics and music are both very well done. The music in game consists of remixed christmas music such as Carol of the Bells and what I think is Little Drummer Boy.

There are two new worlds to visit, Candion and Bloxonius, each with two levels. Candion is themed with Christmas candy and is filled with blind mice as enemies. Bloxonius is themed around toys, lego mostly, but has enemies like rag dolls throwing bombs and toy planes. All the levels are reasonably large and reasonably challenging, with the last of the set being the most difficult.

I quite enjoyed playing Holiday Hare 1995, the music probably being the highlight as it definitely gave the game a very Christmas atmosphere. It manages this with-out losing the spirit of how the original game felt, enhancing it rather than replacing anything. Some of the same annoyances are still here, such as Jazz’s speed making avoiding enemies difficult, but this is easier to deal with as you learn the levels.

This slideshow requires JavaScript.