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!

Related Posts

1. Explorer: 3 – Room Data
2. Explorer: 4 – Inner Room Data
3. Explorer: 2 – Attributes
4. Explorer: 9 – Sprite Movement
5. Explorer: 7 – Sprite Time