Tummai Games

In my first post about Explorer’s room data format, I said that I used 4 bytes to store the wall/gap information for each room. After some thinking, I realized that this was wasteful, as rooms will share wall data with their neighboring rooms. For example, look at these two rooms:

These two rooms share a wall.

They share a wall. The south wall of the top room is the same as the north wall of the bottom room. With my old format, I’d be storing the data for this wall twice: once in the data for the top room and once in the data for the bottom room. Not very efficient. If you imagine a 3×3 (9-room) floor you can see that the room in the middle will share ALL of its walls! Yet here I am wasting 4 bytes of ROM space to declare them for that room.

I was going to hold off on fixing this until later in the project, but Roth left a comment with a great idea for a solution. Here’s what he said:

About the data redundancy deal, I’m not quite sure how this could be approached off the top of my head, but what about making a separate map? For instance, I would guess that you have an overall table map that describes what room is what:

.db $30,$31,$20

or whatever. What if there was a second map, but it was a mapping of the openings?

.db %00100100, %00011000, %00011000, %00011000

So when you go into whatever room, read from that offset and subtract/add to get to be able to get all four sides maybe?

This idea of separating the wall data completely from the room data was just what I was looking for! Each floor would have a lookup table of wall bytes, and I’d index into it based on my room coordinates. I worked it out on paper to see what kind of savings I could get and the difference was huge.

These are my actual notes. Look at the savings!

God forbid I ever make a floor with 400 rooms, but if I did I’d save myself 840 bytes on the wall data! Assuming a square floor where “x” is the length of each dimension, the old method uses 4x^2 bytes to store all of the wall data. The new method uses 2x^2 – 2x. In other words, take 4x^2 and cut it in half, then subtract more! 50%+ savings. Thanks Roth!

This method saves me on bytes in two ways:

1. redundant wall bytes – each wall is declared one time instead of two times.
2. perimeter walls – since lookups are based on room coordinates, I can assume a solid wall if x=0 or y=0 or x=max_x or y=max_y. I don’t have to store any perimeter walls!

My test data has 3 floors. Each floor is 3×3 rooms. My wall data dropped from 108 bytes to 36 bytes! :)

Implementation

I found that it was less headache to calculate indexes if I separated East-West walls from North-South walls and made two lookup tables for each floor.

Click to enlarge.

The cost of this approach is that I have to store pointers to two tables per floor instead of one, but I think the tradeoff is worth it at this stage.

Implementing this couldn’t be easier. First I add wall table pointers to my floor data:

;----------------
; floor data
floor_map0:
    .byte $03, $03 ;dimensions of floor
    .word floor0_ew_walls ;ptr to ew wall lookup table
    .word floor0_ns_walls ;ptr to ns wall lookup table
    .word f0_r00, f0_r10, f0_r20 ;ptrs to room data
    .word f0_r01, f0_r11, f0_r21
    .word f0_r02, f0_r12, f0_r22

Next I update my load_floor routine to read these new pointers and store them in RAM:

;----------------
; load_floor expects the floor number in A
load_floor:
    sta map_floor   ;current floor
    asl
    tay
    lda map_ptr   ;this is a pointer to the floor lookup table
    sta temp_ptr2
    lda map_ptr+1
    sta temp_ptr2+1

    lda (temp_ptr2), y   ;get the pointers to the floor data
    sta floor_ptr
    sta temp_ptr1
    iny
    lda (temp_ptr2), y
    sta floor_ptr+1
    sta temp_ptr1+1

    ldy #$00     ;now let's read and set the floor's dimensions
    lda (temp_ptr1), y
    sta floor_dim_x
    iny
    lda (temp_ptr1), y
    sta floor_dim_y
    iny

    lda (temp_ptr1), y ;store the ptrs to the wall tables
    sta ew_walls_ptr
    iny
    lda (temp_ptr1), y
    sta ew_walls_ptr+1
    iny

    lda (temp_ptr1), y
    sta ns_walls_ptr
    iny
    lda (temp_ptr1), y
    sta ns_walls_ptr+1
    iny

    tya  ;update floor_ptr to the first room after the header
    clc
    adc floor_ptr
    bcc @done
    inc floor_ptr+1
 @done:
    sta floor_ptr
    rts

Then I modify the wall-building routine to calculate indexes and read from the wall tables. The last step is to reorganize my data: remove wall bytes from the individual room data and stick them in tables. Very quick fix.

Conclusion

Separating the wall data from the room data is going to save me a lot of ROM space. It also prevents the possibility of non-matching shared walls (I’m still entering all the data by hand, and I mistype from time to time). It’s sped up the map-building process too.

Come to think of it, I might try to implement something similar for stairs. Stairs_up and stairs_down need to line up on the z-axis. In a way the ceilings and floors are like walls themselves, just with fewer openings (stairs) across the whole map. I’ll save that battle for another day.

Thanks again Roth!

Last time I talked about how I store walls in my map data for Explorer. Today I’m going to talk about how I store tiles for the room interior.

After the walls are put down, there is a 12×11 field of floor space for me to work with for the room interior. This picture should make it clear:

The room interior is 12x11 metatiles big

The basic way I place a tile on the map interior is with a coordinate byte. A coordinate byte has the x-coordinate in the left nibble and the y-coordinate in the right nibble. For example, let’s say I want to place a tile in the spot designated by the blue square in the following screenshot:

The blue square is at coordinate (8, 7)

This spot is 8 to the right and 7 down, so the coordinates would be (8,7). The byte I use to represent this position is $87. If I wanted to place a tile in the very top-left square, I’d use the byte $00. The bottom-right-most square is $BA. So using the values $00-$BA, I can represent any single position on the map interior.

It would be wasteful if I declared each and every tile one byte at a time. I should try to save bytes by somehow compressing repeating data. I currently do this by drawing lines. After a coordinate byte in the room data, there can be an optional run byte. A run byte tells the map engine which direction to draw a line and how many tiles long that line should be. The left nibble represents the direction:

C=Right
D=Down
E=Left
F=Up. (That’s F’ed up.)

The right nibble tells how long the line should be.

For example, let’s say we are drawing block tiles. In our room data we encounter the bytes: $11, $CA. The first byte says “place a tile at (1,1).” The second byte says “draw a line to the right, 10 tiles long.” This screenshot shows the result of these two bytes:

2 bytes make a line of tiles

Run bytes can be tagged onto the end of other run bytes. In this case, the starting point of the new line is the ending point of the previous line. Check out these five bytes: $11, $CA, $D9, $EA, $F8. If you were to translate these bytes into English, they’d say:

“Place a tile at (1,1), then draw a line to the right, 10 tiles long. Then draw a line down, 9 tiles long. Then go left 10 tiles, and finally up 8 tiles.”

The result:

5 bytes makes a box

Implementation

My test data currently has 7 possible tiles it can use in the room interior. They are:

.enum
    floor
    wall
    block
    water
    block_breakable
    stairs_up
    stairs_down
.endenum

I store my room data as a series of strings. The first byte in the string tells which tile to use. Next comes a series of coordinate bytes and run bytes. Finally, a string is terminated with $FF. A list of strings is also terminated with $FF. Here’s are some example strings:

    .byte block, $11, $CA, $D9, $EA, $F8, $FF
    .byte water, $22, $C8, $D7, $E8, $F6, $C7, $D5, $E6, $F4
        .byte $C5, $D3, $FF
    .byte stairs_up, $00, $45, $FF
    .byte block_breakable, $02, $20, $FF
    .byte stairs_down, $BA, $66, $FF
    .byte $FF  ;no more strings
    

That data will generate this room interior:

A full room. Careful, those steps might be slippery.

Here is my code that parses the inner room data.

    ldy #$ff
@mainloop:
    iny
    lda (temp_ptr1), y  ;which tile?
    cmp #$FF
    beq @end            ;FF terminates the room
    sta map_temp1     ;store tile number in a temp variable
    iny
    lda (temp_ptr1), y ;coordinate byte
@innerloop:
    iny
    jsr calc_room_position ;will take the coords in A and 
                           ;calculate an offset, output in X
    lda map_temp1    ;our tile number
    sta room, x

@run_check_loop:
    lda (temp_ptr1), y  ;peek at the next byte
    cmp #$FF
    beq @mainloop   ;FF terminates a tile string, so loop to 
                    ;the next tile string
    cmp #$C0
    bcc @innerloop  ;if less than $C0, there is no tile run, 
                    ;so loop back to get a new coordinate byte
    jsr tile_run  ;else we have a run.  This will take the 
                  ;run byte in A and draw a line in our RAM 
                  ;copy of the room.  We still have x loaded
                  ;with our offset.
    iny

    jmp @run_check_loop  ;check for another run byte

@end:
    rts

Conclusion

I don’t know if this is the best way to do it, but it works! I’m always looking to improve, so if you have any better ideas for compressing the room data, let me know in the comments!

Speaking of better ideas, Roth left a comment on my last post with a cool idea for saving bytes on my wall data. I’m talking hundreds of bytes. I’ve already implemented it and I’ll talk about it next time. In the meantime, feel free to subscribe to the RSS feed.

Today I’m going to talk a little bit about the format I use to store my room data. In Explorer, the player views rooms from the top. The background doesn’t scroll at all when the player moves. Everything stays put until the player hits the edge of the screen. When that happens, a new room is loaded and drawn to the screen.

A consequence of this style of gameplay is that rooms will have many things in common. For example, they will all be the same size. They will all be enclosed by walls. They will all have gaps somewhere in the walls to allow passage between rooms. They will all have floor space.

To avoid having redundant data for every room in the game, I have a blank room stored uncompressed in ROM. It looks like this:

This is the default blank room. It has 4 solid walls enclosing a field of floor tiles.

When I load a new room, the first thing I do is copy this blank room into RAM. Then I read the data for the new room and write the new data over the copy of the blank room in RAM. This saves me a lot of bytes in ROM, as I don’t have to store all of those wall and floor tiles in the data for each individual room. I assume four walls and a floor and draw the extras on top.

Gaps in the Walls

The default room is nice, but it traps the player inside. There are no gaps in the walls. So my map data needs a way to tell me where to stick gaps so that player can navigate to other rooms.

Explorer is a puzzle game. It’s a maze. I can’t just have one exit per direction ala Zelda. I need each wall to potentially have several exits. Some will lead to dead ends, some will allow access to areas that others won’t. I want a lot of flexibility but at the same time I don’t want the wall-gap data to take up too much ROM space. There are going to be hundreds of rooms, so I want to keep them as compact as possible.

My current solution is to use 4 bytes, one per wall. Each bit represents a gap. Look at this picture:

Each wall has a byte telling where the gaps are. The numbers in the picture show which bit represents which gap.

The numbers in the above picture show which bit controls which section of wall. For example, if my byte for the north wall of a room were #%10000001, the gaps marked 7 and 0 would be open, while 1-6 would be blocked, like this:

The north wall is represented by the value #%10000001

The first four bytes in a room’s data are the wall/gap data, in order of North, South, West, East. North and south have the same bit mapping scheme, as do west and east.

Let’s take a look at the room I posted up in my post about attributes:

A nice room

The first four bytes in the room data are: %00100100, %00011000, %00011000, %00011000. Notice how the set bits correspond to the gaps in the room.

Code Sample

The code to generate these walls is pretty straightforward. First I read the byte from the map data, then I call a subroutine which will translate that byte into a buffer of wall/floor tiles. This subroutine just shifts out the bits one at a time and plugs the appropriate value into the buffer. Here’s the version for making north-south walls:

    lda (temp_ptr1), y ;read the top wall byte
    iny
    jsr room_build_ns_wall ;this fills a buffer which we can 
                           ;copy to the tile map in RAM

room_build_ns_wall:
    sta map_temp1

    ldx #$0B

@loop:
    cpx #$01  ;these four positions are always walls.
    beq @wall ;they are not controlled by the wall byte.
    cpx #$03
    beq @wall
    cpx #$08
    beq @wall
    cpx #$0A
    beq @wall

    lsr map_temp1 ;shift a bit out
    bcc @wall     ;if it's zero, wall
    lda #floor    ;else it's a floor
    beq @write
@wall:
    lda #wall
@write:
    sta room_wall_buffer, x
    dex
    bpl @loop ;end the loop at x==$FF
    rts

Once I have my buffer filled, I copy it onto the blank room in RAM.

The west-east wall version is almost identical, it just has different “always-wall” values.

If you are wondering what #floor and #wall are, they are just constants. I try to avoid hard-coding values whenever possible. My tile ids are declared using ca65’s .ENUM directive:

.enum
    floor
    wall
    block
    water
    block_breakable
    stairs_up
    stairs_down
.endenum

#floor will evaluate to #$00, and #wall will evaluate to #$01.

Conclusion

I think I can improve even further on this wall/gap format. There is a lot of redundant data still. For example, adjacent rooms will have the same byte values for their shared wall. If I can come up with a scheme to eliminate this redundancy, I can save even more bytes. That’s a battle for another day though. This format works for now and I’m going to move forward. But if you have any suggestions, please let me know!

Next time I’ll talk about the rest of my room format: ie, how I store tiles in the room interior.

I put off doing attributes for a long time because I didn’t want to face the nightmare. When I finally sat down to do it the other day, it was extremely fast and easy to implement. The reason? No scrolling.

What’s an Attribute?

The NES has 4 screen-sized pages that you can draw background tiles to. These pages are called nametables. Each nametable has an attribute table associated with it. An attribute table specifies what palettes are used for the different tiles in the nametable. So basically the nametables control what tiles are seen, and attribute tables control what colors those tiles are.

The NES PPU (Picture Processing Unit) maps the attribute tables to the nametables in a very unintuitive way (see this tutorial), which makes working with attribute data a real pain. This is especially true when scrolling is involved as you may have portions of two different nametables on the screen at the same time. The ultimate nightmare is four-way scrolling where you can cross horizontal and vertical screen boundaries at the same time. I foolishly attempted a four-way scrolling engine as my first NES project and attribute tables left a bad taste in my mouth. So I wasn’t looking forward to dealing with them again.

Leftover attribute nightmare from my first attempt at a 4-way scrolling engine.

But as I mentioned, attributes aren’t so bad when there is no scrolling going on. The Explorer game I’m writing shows one room at a time, and I don’t think scrolling will be necessary when changing rooms. I think I will be able to get away with turning off the PPU, drawing the new room in one go, and then turning the PPU back on. This will cause the screen to black out when changing rooms, but only for a second. I don’t think it will be too distracting. We can take a peek at Sivak’s platformer demo to see how this method looks:

Looks just fine to me! So Plan A is to ditch scrolling altogether and instead toggle the PPU off and on when changing rooms. This should save me some headaches when dealing with the attribute tables.

Implementation

When I load a new room, I turn off the PPU. Then I draw the room. Then I color the room (write the attribute data to the attribute table). Then I turn the PPU on. The trickiest part of this process is figuring out what to write to the attribute table.

My test data consists of rooms built from seven possible 2×2 metatiles (16×16 pixels). The first thing I do is assign each metatile a palette number. I don’t like to hardcode any number values in my data, so I give everything an alias using ca65’s .ENUM directive. First the tiles ids, which are used in the map data:

.enum
    floor       ;these are my tiles, numbered $00-$06
    wall
    block
    water
    block_breakable
    stairs_up
    stairs_down
.endenum

Then the palette ids:

.enum
    orange ;my four bg palettes from $00-$03
    gray
    blue
    brown
.endenum

Finally, the attribute assignments for each tile in order:

tile_attribs:
    .byte gray    ;floor
    .byte brown   ;wall
    .byte orange  ;block
    .byte blue    ;water
    .byte orange  ;block_breakable
    .byte gray    ;stairs_up
    .byte gray    ;stairs_down

With this setup, I can read a tile number from my map data and then use that value as an index into the tile_attribs table. Once I’ve read the palette number from the tile_attribs table, I can do a shift/roll combo to sneak that 2-bit value into an attribute byte:

;-------------------------------
; make_attrib takes a map index in x and creates an attribute
; byte for the metatile box (32x32 px). x is the top-left tile.
make_attrib:
    lda room, x  ;top left
    tay
    lda tile_attribs, y  ;get the palette number
    sta map_temp2
    lsr map_temp2  ;shift a bit into the carry flag
    ror map_temp1  ;roll the carry flag into a temp var
    lsr map_temp2  ;and repeat for the second bit
    ror map_temp1

    lda room+1, x  ;top right
    tay
    lda tile_attribs, y
    sta map_temp2
    lsr map_temp2
    ror map_temp1
    lsr map_temp2
    ror map_temp1

    lda room+16, x   ;bottom left
    tay
    lda tile_attribs, y
    sta map_temp2
    lsr map_temp2
    ror map_temp1
    lsr map_temp2
    ror map_temp1

    lda room+17, x     ;bottom right
    tay
    lda tile_attribs, y
    sta map_temp2
    lsr map_temp2
    ror map_temp1
    lsr map_temp2
    ror map_temp1
    rts
    

Looping across the room data I can build a full attribute table in RAM. Then I can simply copy it over to the PPU when PPU rendering is off. It works!

Before:

Here's what a room looks like before attributes

After:

Here's how the room looks with proper attribute data.

Please forgive the ugly tiles. I’m no artist. They will all be replaced in the future. :)

Conclusion

Attributes are done! Room decompression works! I can display rooms correctly! The next step is to design a multi-floor, multi-room test level and make it possible to navigate between rooms. That will likely take me some time, so my next few posts will be about my room data format.

The game I am currently working on is called Explorer. That’s the working title, not the final one. I originally started to work on it as an entry to a Retro Coding Competition, but I got busy and couldn’t make the deadline.

Story and Gameplay

Explorer is a puzzle game. Not the kind of puzzle game where you stack blocks, but the kind where you navigate a labyrinth. The basic storyline is this:

You are a guy who has been one-upped all your life by a clever, handsome, ambitious man who is now a world-famous archaeologist. You decide that the only way you can make up for a lifetime of failure and humiliation is to finally get a one-up on him. You must beat him at his own game. To do that, you follow this archaeologist around the world, sneaking into his excavation sites and stealing the ancient treasures hidden within before he can discover them.

The game will be a series of top-down labyrinths, similar to the dungeons in Zelda or the overland map in The Guardian Legend. Each room will take up a full screen and have exits on four sides to other rooms. There will be multiple floors, pitfalls, buttons/switches, locked doors, puzzles, traps, changing terrain, special items, etc. For each excavation site you will have to navigate your way through the labyrinth, find the ancient treasure, and get out without getting caught.

Specs

I’m programming the game using the UNROM mapper. This gives me:

• 128k of PRG-ROM
• CHR-RAM

128k of PRG-ROM is probably more than I’ll need. If I end up having a lot of free space, I’d like to include support for user-made labyrinths. I’m thinking I’ll include a map editor and a utility that will stick a user-made map right into the ROM file.

My assembler of choice is ca65, part of the cc65 package. You can find that here.

And much thanks to SecretServiceDude for posting his UNROM linker config on the nesdev forums. The one I use is based off of his.

Progress

As of today, I’ve written:

• UNROM support
• a basic music engine
• the beginnings of a map engine

The map engine deals with a few types of data:

• dungeon
• floor
• room

Each dungeon has one or more floors. Each floor has one or more rooms. A room is a represented by a single screen. Right now the map engine is capable of loading any room in a dungeon and displaying it on the screen. The biggest success for me here is that I am able to read and decompress the room data format I came up with. So far all of my test data is showing up correctly on screen.

See you next time where I’ll get into attribute data (coloring background tiles)!