The Making of Dungeons


Code by Trodoss

Art by JO3RI


The Making of Dungeons


"Dungeons" was started life as an experiment in scrolling (horizontally and vertically).  We both liked the look of it so much that we started thinking about making an actual game from it.  JO3RI had already been working on graphics for a fantasy game, so we started putting that together.  



The First Hurdle - A Map!


We had a working prototype of a scrolling, and had high ambitions of making a very large game, so we set out on the task of finding a way to make that work on "Dungeons."


On another project I was able to compress 8 32x32 maps into 3713 bytes of data, and was fairly sure similar compression could be applied on this project.  The reason for 32 as a dimension is that size fits 8-bit numeric boundaries, and is then easier  to manipulate/compress.


In our research we happened upon "Geomorph Mapping," where a series of tiles could be arranged in any order.


See:

http://www.1km1kt.net/geomorph/

http://rpgcharacters.wordpress.com/maps/geomorph-mapping-project/


We had briefly considered a randomly generated map each time, however we wanted to ensure that every map was "playable" (meaning that the player could traverse the entire map without having their path blocked in some way).  We decided on 8x8 "blocks" as a standard, and had determined that we would make a set of these that could be assembled to make the maps in the game.


JO3RI set out on the task of building a map generator that could take 8x8 "blocks" of map, and generate a playable map as output. He was able to make a complete Arduino (Gamby) application that could generate these maps.  Because each map was made up of these blocks and that made each actual map relatively small, we were able to fit *hundreds* of pre-generated maps in the game.


So let’s explain this a bit more. One level is 256x256 in pixels or bits, that is 65536 pixels or bits, which makes 8192 bytes or 8KB. Dungeons has 250 unique levels ! if all were just bitmaps, that would be a whooping 2000 KB, not nearly fitting the 32 KB we can use. And that is even without gameplay or characters.


So the first thing we did, was to think of it like puzzle pieces. you have corners, side pieces and the middle parts. We made a grid of 4x4 and started to make those pieces, we call blocks. This way each unique level was represented by a small grid of 16 bytes, like this:

00  |  06  |  05  |  20


                                            map_layout[] = {

35  |  46  |  44  |  16                00,06,05,20,

                                                35,46,44,16,

                                                37,57,63,17,

37  |  57  |  63  |  17                33,28,26,20

                                                };


33  |  28  |  26  |  20

We created a total of 64 blocks (4 types for each corner, 6 types for each side and 24 for the middle pieces). 1 block representing 64x64 pixels (4.096 bits) or 512 bytes. So let’s calculate again, we have 250 levels, using 16 bytes (4x4 grid). That makes 4000 bytes. We also need to take those 64 blocks (puzzle pieces) into count. That would be 64x512 = 32.768 bytes, making a total of a bit less than 33 KB. We just went from 2000 KB to 33 KB !


Still to much to get all level data into the 32 KB, so we continued to compress. So the second thing we did was using tilesets to create walls and floors. Every tile is 8x8 pixels, 64 bits or indeed 8 bytes. We made 5 different tilesets, used randomly, so walls and floors would change over levels, making the game look more variable. Now by using tilesets, we can now make a block (puzzle piece) consist out of 8x8 tiles. Each tileset itself

is 16 tiles wide, or 128x8 pixels (or bits). Or 128 bytes for every tileset and thus a total of 640 bytes for all tiles in total.

09 | 05 | 05 | 05 | 05 | 05 | 05 | 05

02 | 16 | 16 | 16 | 16 | 16 | 16 | 16

02 | 16 | 16 | 16 | 16 | 16 | 16 | 16

02 | 16 | 16 | 16 | 16 | 16 | 16 | 16

02 | 16 | 16 | 16 | 09 | 05 | 05 | 05

02 | 16 | 16 | 16 | 02 | 16 | 16 | 16

02 | 16 | 16 | 16 | 02 | 16 | 16 | 16

02 | 16 | 16 | 16 | 02 | 16 | 16 | 16

00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15

This also means that those 64 blocks no longer are 512 bytes each, but only 64 bytes ! Being 4.096 bytes in total for all the blocks, 4000 bytes for the levels and 5x128 bytes for all our tiles (640 bytes).


Hurray we just got every thing needed for 250 unique levels crammed into 8736 bytes or about 9 KB. But we didn’t stop there, we also wanted a to show a mini map of the current level you are playing. So we reused de blocks (puzzle pieces) to put 8x8 tiles on the screen. That makes mini maps of 64x64 pixels. So this adds 64 tiles of 8x8 pixels for mini map creation, being 512 bytes.


That’s it, 250 levels and mini maps fit into a total of 8608 bytes, leaving us “plenty” of room for gameplay, bitmaps and characters.


The Second Hurdle - Making it Fit


We had created various working "parts" of the game, however it was not all put together. JO3RI had working screens for the main  menu, maps, "Game Over", etc., and Trodoss had created the game play elements.  Once we started putting the elements together we quickly found out that it wasn't all "fitting" into the amount of space the Arduino had available.  


We started removing and optimizing the code (with the goal of not removing any of the levels, graphics, or gameplay elements). Our goal continues to be to fit in as much as possible, and we continue to find creative and inventive ways of making the code"fit".



The Third Hurdle - Sound


We made progress, but not much ... we simple didn't have much room left, so we added some blibs and blobs, but that's it.