Archive for the 'Bob’s Fury' Category

30
Nov
15

Huffman Coding

Quite some time ago I did a short post about a compression technique called run-length encoding (or RLE), that was a commonly used compression method for graphic and level data. At the time I wrote and implemented it for the graphics and level data for my home-brew game Bobs Fury with quite the success, significantly reducing the disk space required for the base game.

I do however have some files left, which are largely just ASCII text, that don’t compress well or at all using that technique. I’d like to make them smaller, and of course harder to read as they contain story text, not that my game has a brilliant story, but you get the idea. Step in an encoding technique called Huffman coding.

Essentially the encoding algorithm encodes symbols as a variable length stream of bits. The most frequently used symbols are represented by shorter bit streams, whilst the least used have longer ones. Normally in a computer each symbol would be encoded as a fixed number of bits, such as say 8-bit or 16, so this results (hopefully) in shorter encodings for most symbols, and longer ones only for the rarely used ones.

The tricky part is creating the Huffman tree, which is basically a code-book representing how each symbol is encoded or decoded. Here is a quick tutorial on how they are created, which will also give you a feel for how the encoding works. It’s also commonly known as a dictionary, or code book.

A fixed tree can be used for everything, but would not do the best job for every set of data being compressed. So typically a tree is created and stored along with the encoded data to achieve the best compression possible. This of course does add some overhead, which could be a problem if the resulting encoding isn’t much shorter than the original.

Huffman coding typically works poorly when the symbols all appear in the text at roughly the same frequency. The worst case being everything with exactly the same frequency. Notably it won’t produce an encoding that is longer than the original data, although with the overhead of storing the tree, you could end up with a larger data file. In practise this rarely happens.

Other data such as English text stored in ASCII actually compresses quite well. As usually not all the 255 characters are used, most encodings will be shorter than 8 bits per symbol. Also because natural language uses some letters more than others the average encoding length for all the symbols will be shorter.

Huffman coding was actually invented quite some time ago (1951) by David Huffman, well before it came into common use. Check out the Wikipedia page for more information. It’s a part of many commonly used compression programs and formats such a Zip and Bzip. Older 8-bit machines typically weren’t powerful enough, so it wasn’t commonly used until more powerful machines with more memory became available.

It took me much longer than usual to write this post primarily because I began the process of writing an encoder and decoder, but because of the complexity, it’s taken up much more time than I expected. Currently I have just finished the encoder, but have yet to test it. I had hoped to get the code running first, but that will have to wait.

Advertisements
16
Dec
14

Improving Joystick support for Bob’s Fury

Some of the hardware support within Bob’s Fury has been far from ideal, the joystick/game pad being one such device. I had only added support for a simple 2 button joystick, as that’s all I had when I first wrote the code a long time ago. It proved to be inadequate as there just simply wasn’t enough buttons to support all the functions in game, and you couldn’t choose what the buttons do.

Old Joystick Configuration

Old Joystick Configuration

So with the aid of a real machine and a Gravis game pad I worked out how the basic 4 button devices work. It turns out they aren’t much different. I had originally coded my interface to expect two joysticks, each with 2 axis and 2 buttons. It turns out that the buttons on the second joystick correspond to the 3rd and 4th buttons on the Gravis game pad, which means it was fairly simply to allow such a device to support 4 buttons with a minimal effort. I re-wrote the joystick hardware code to be a single joystick with 4 buttons and axis which should support most devices.

New Configuration Screen

New Configuration Screen

Once I got the joystick code re-worked I didn’t want to give fixed functions to the buttons, so I had to recode the configuration interface to allow changing what the buttons do, which funnily enough took longer to get right than the hardware side of things. After some testing in Dosbox I’m pretty happy with the result. I still need to test on some real hardware to make sure everything works, and I need to test a two button joystick to ensure that still works as well. I’ll update the download once I’ve tested it on real hardware.

11
Nov
14

Download for Bob’s fury

This week, after much time thinking about it, I decided I’d finally offer my old school platform game, Bob’s Fury for download. I originally wrote it in Qbasic back when I was 14 with the help of my younger brother who did some of the graphics, levels and helped play test it. The idea for making my own platformer had grown out of playing two of my then favourite games, Xargon and Hocus Pocus.

VGA Screenshot

VGA Screenshot

I originally had much larger plans for it, I had wanted to make water levels and puzzles like those in Xargon and run and gun sections like those in Hocus Pocus. At this stage I was still using gwbasic and I found that it was difficult to store enough graphics and tile information for one screen, it seemed like I wasn’t going to be able to build anything at all when I discovered Qbasic on the school computers.

Qbasic had many advantages, it supports a better graphics mode which allowed 256 colours at 320×200, then a common resolution for most PC games. The interpreter also had roughly twice the memory available to it which allowed me to use many sprites and get two screens per level. It took me roughly a year to build the engine and most of the levels. It was still quite limited in many aspects and didn’t live up to the original dream, but it was still a significant achievement.

Later in high school I had a computer studies teacher who did a bit of programming themselves. I know it seems odd, but not that many teachers of computer studies could actually program in those days. Anyway I was lucky enough that he gave me a copy of Borland Turbo Pascal 6.0, which was to be the first compiler I’d get to use. It was a bit of a learning curve, but I managed to learn pascal much quicker than either basic. I decided I wanted to port Bob’s fury as Pascal was a much faster language and wouldn’t be as limited as Qbasic.

EGA Screenshot

EGA Screenshot

I had a few problems however when I learned the graphics library. Firstly I hadn’t encountered pointers before, and they were required for bit mapped graphics. So I experimented with some simple vector graphics at first. Also Pascal didn’t have any support built-in for the graphics modes I wanted to use. So I put off making a port until I could learn more about the language.

Shortly after I went to University and got internet access I was able to solve some of these problems. I practised and learned how to use pointers in general and I found files that provided support for the graphics modes I was after. By 1999 I had built much of the tools and libraries for graphics and a few ancillary libraries needed. I’ve been working on this port sporadically since then.

I’ve been reluctant to release it for a few reasons. The first one being it’s quite unfinished. I haven’t really made enough new levels, I’m only really half way through making the first episode. The bulk of the levels are actually from the original Qbasic version, which are obviously quite limited. I’ve built a system for playing Adlib music, but haven’t made any music yet, appart from tracks for testing the software anyway.

CGA in game.

CGA in game.

So why am I releasing it? Well because despite the limitations it’s pretty cool, and I have fun playing it. (one of the reasons progress has been slow!) I want to motivate myself to get busy making more levels, now I realise there will probably be little interest in it, but stuff that I post about on my blog tends to get worked on. So having it here is a great motivation for doing more work and perhaps reporting progress as I get more done.

I’ve put a ZIP file on my download site here.

 




Blogs I Follow

Enter your email address to follow this blog and receive notifications of new posts by email.


Mister G Kids

A daily comic about real stuff little kids say in school. By Matt GajdoĊĦ

Random Battles: my life long level grind

completing every RPG, ever.

Gough's Tech Zone

Reversing the mindless enslavement of humans by technology.

Retrocosm's Vintage Computing, Tech & Scale RC Blog

Random mutterings on retro computing, old technology, some new, plus radio controlled scale modelling.

ancientelectronics

retro computing and gaming plus a little more

Retrocomputing with 90's SPARC

21st-Century computing, the hard way

lazygamereviews

MS-DOS game reviews, retro ramblings and more...