Star Fighter 3000 is a three dimensional flying shoot-em-up game (I won't call it a flight simulator, because it doesn't have much in the way of physics). It was published in 1994 for 32-bit Acorn computers. In this game, the ground is represented as an infinitely repeating flat texture map which is 4096 by 4096 texels in size, and has a colour depth of 8 bits per texel. You don't have to be a genius to calculate that an ordinary bitmap image of this size would require 134,217,728 bits of memory (which happens to be exactly 16 megabytes).
Given that this game was designed for machines with only 2 MB of memory, how was this achieved? The answer is a clever trick that was used in many games of that era, although more commonly in those that featured a two dimensional world. Instead of storing a single huge texture, Star Fighter 3000 uses a much smaller map that has only 256 by 256 elements. Each element is a reference to one of up to 256 tiles. The tile graphics are stored separately, and each one is only 16 by 16 texels in size.
Each map location is represented by a single byte, so the memory required for a ground map is only 524,288 bits (64 kilobytes). The game only allocates space for up to 192 tiles rather than the theoretical maximum of 256. This adds a modest 393,216 bits (48 KB) to the total. Thus the total memory usage has been reduced from 16,384 KB to 112 KB; a compression ratio of almost 1:146!
Naturally there are drawbacks to this approach: Specialised tools are required to edit the game maps, and each set of tile graphics must be painstakingly designed. As a compression method, it only works with images that contain many areas of similarity (ideal for an aerial view of a landscape, but not for complex images). On the plus side, the same map can easily be given a new appearance by rendering it with a different set of graphics.
Several years ago, I became interested in the possibility of generating Star Fighter 3000 maps automatically. I don't mean random maps, such as those generated by Sim City 2000. I mean taking a photographic image, identifying areas of similarity, and generating a map and associated set of tile graphics from it. Naively, I even thought that this might be viable method of (lossy) image compression.
The programs available here allow you to do just that; decompose an image into a mosaic of smaller tiles, from which an approximation of the original image can subsequently be reconstructed. The results are not as good as I had hoped; my method certainly isn't going to supplant JPEG image compression. A reconstructed image tends to resemble a collage of little bits of paper (if you ever did one at school then you will know what I mean) except at very low compression ratios. So this is perhaps a warning of how not to write an image compression algorithm. There are several improvements that could be made, such as allowing the same basic tile to be used in different ways (rotated, flipped, internal shifts). However, this would increase the memory and time required to encode images (which is already costly).
|
|
This is part of a map which is featured in a tutorial for the Draw application (from the RISC OS User Guide). I think it is a fairly typical vector graphics image. Unlike most photographic images, it has very high contrast (it mainly consists of black symbols on a white background). This makes it quite resilient against different areas of the image being merged even when very low quality output is specified. The repeated symbols were identical in the original vector graphics format but have become slightly distorted during rasterisation. Unfortunately they are not aligned with each other, otherwise it would have been amenable to encoding using very few tiles. The image is is 256 by 224 pixels in size (exactly 56 KB at a colour depth of 8 bits per pixel). |
|
|
This is the same image after it was converted to a mosaic of 32 by 28 tiles, each tile being 8 by 8 pixels. The default 'quality' setting of 98 was used; this means that areas were merged only if their similarity was greater than 99.9%. Despite this, it was still possible to reduce the number of unique tiles from 896 to 350 (mainly by merging large monochromatic areas). Although not identical to the original image, any reduction in quality is invisible to the human eye. The combined size of the map and tile images is 24,192 bytes, which is 42.1% of the size of the original image. This may sound impressive, but PNG (a popular image format with lossless compression) can compress the same image to 7.6% of its original size! |
|
|
This a mosaic of the same image, but this time generated with the 'quality' parameter set to 50. This means that areas were merged only if their similarity was greater than 97.5%. This allowed the number of tiles to be further reduced to 296. The combined size of the map and tile images is 20,736 bytes, which is 36.1% of the memory required for the original image. This saving has been achieved at the cost of a visible reduction in image quality; the line of the river is broken in several places, and the edge of the lake has started to look a little ragged. |
|
|
This is how the mosaic looks with 'quality' set to 0, meaning that areas were merged only if their similarity was greater than 95%. The number of unique tiles has been slightly reduced to 228, but at a terrible cost in image quality (i.e. probably not worth it). The map is half the size of that generated in previous tests, because each tile number can now be stored in a single byte. The combined size of the map and tile images is 15,488 bytes, which is 27% of the memory required for the original image. However, the line of the river has almost vanished, its name is illegible, and there are many visual artefacts. |
| Quality | Map size | No. of tiles | Memory required | Compression |
|---|---|---|---|---|
| 98 | 1792 bytes | 350 | 24,192 bytes | 42.15% |
| 75 | 1792 bytes | 329 | 22,848 bytes | 39.15% |
| 50 | 1792 bytes | 296 | 20,736 bytes | 36.13% |
| 25 | 1792 bytes | 272 | 19,200 bytes | 33.45% |
| 0 | 896 bytes | 228 | 15,488 bytes | 26.98% |
For your viewing pleasure, I have also made an animation that shows the gradual deterioration in image quality as the threshold for merging similar areas is lowered.
|
This is a publicity photograph of the actress Sophie Aldred, who starred opposite Sylvester McCoy in seasons 25 and 26 of the BBC television series 'Doctor Who'. I think she is quite cute. For some reason, my goal when I originally had the idea of creating mosaics from images (several years ago) was to turn this photograph into a Star Fighter 3000 map. Unlike the example vector graphic images, it does not have any large monochromatic areas. The image is 256 by 192 pixels in size (exactly 96 KB at a colour depth of 16 bits per pixel). |
|
This is the same image after it was converted to a mosaic of 32 by 24 tiles, each tile being 8 by 8 pixels. It looks almost identical to the original image except that shading of the skin above her decolletage is very slightly blocky. The default 'quality' setting of 98 was used, meaning that areas more than 99.9% similar were merged. This allowed a modest reduction in the number of unique tiles from 768 to 690. The combined size of the map and tile images is 89,984 bytes, which is 91.5% of the size of the original image. This does not compare well with either PNG or JPEG which can compress the same image to 62.65% or 14.6% of its original size, respectively. |
|
This is a mosaic of the same image but generated with a 'quality' of 88, meaning that areas were merged only if their similarity was greater than 99.4%. This minor change to the merge threshold allowed the number of unique tiles to be halved to only 350. The combined size of the map and tile images is 46,336 bytes, which is 47.1% of the memory required for the original image. However, the image quality is noticeably much worse; whole areas have become blocky and the overall effect is artistic rather than practical. |
|
This mosaic was generated with a 'quality' of 75, meaning that areas were merged only if their similarity was greater than 98.75%. There are now only 143 unique tiles but there has been a commensurate drop in image quality. The map is half the size of that generated in previous tests, because each tile number is now a single byte. The combined size of the map and tile images is 19,072 bytes, which is 19.4% of the memory required for the original image. However, it is getting difficult to distinguish the outline of objects; in particular, her hair has merged with the garden behind. |
|
This is how the mosaic looks with 'quality' set to 63, meaning that areas were merged only if their similarity was greater than 98.15%. The number of unique tiles has been halved again to 63. The combined size of the map and tile images is 9,984 bytes, which is 10.2% of the memory required for the original image. It is no longer possible to identify the face of the person in the photograph. If you want to see what happens next then look at the animation (but I warn you, it isn't pretty!) |
| Quality | Map size | No. of tiles | Memory required | Compression |
|---|---|---|---|---|
| 98 | 1,536 bytes | 691 | 89,984 bytes | 91.54% |
| 88 | 1,536 bytes | 350 | 46,336 bytes | 47.14% |
| 75 | 768 bytes | 143 | 19,072 bytes | 19.4% |
| 63 | 768 bytes | 72 | 9,984 bytes | 10.16% |
| 50 | 768 bytes | 48 | 6,912 bytes | 7.03% |
| 38 | 768 bytes | 34 | 4,352 bytes | 4.43% |
| 25 | 768 bytes | 24 | 4,352 bytes | 3.91% |
| 13 | 768 bytes | 15 | 2,688 bytes | 2.73% |
| 0 | 768 bytes | 1 | 896 bytes | 0.91% |
For your viewing pleasure, I have also made an animation which shows the gradual deterioration in image quality as the threshold for merging similar areas is lowered.
What every man really wants - a woman who can be seen from space!
|
|
This is an example of the kind of fun you can have in conjunction with Star Fighter 3000 and my desktop applications FednetCmp and SFToSpr. My image-to-mosaic compression program has several special options to facilitate generation of maps and tile graphics for Star Fighter 3000. However, the raw map data still needs to be compressed by FednetCmp, and tile graphics sets must be converted to game format by SFToSpr.
There are two separate programs which are designed to complement each other. Both must be run from the command line (there is no desktop interface). SprToMap decomposes an input image into a mosaic and outputs separate files containing the map and set of tile graphics. MapToSpr reconstructs an image from a specified map and tiles set and outputs a file containing the reconstituted image.
I have tried to write portable code; you should be able to compile and run it on any system that supports ISO 9899:1999 standard 'C'. However, as supplied, my programs only understand new-style RISC OS sprite files. This is a bitmap image format defined in volume 5a of the RISC OS 3 programmers reference manual. I suspect that it would not be too difficult to adapt the code to use a less esoteric bitmap graphics format.
If you are interested then you can download a Zip archive containing the two programs, full source code, licence details and documentation (52 KB).
|
Designed by Christopher James
Bazley using a RISC
OS workstation and HTML³. Background pattern is © Sophia Field. |
|
