Author Topic: Memory Efficient "Room" Design  (Read 320 times)

0 Members and 1 Guest are viewing this topic.

Offline menegator

  • CPC464
  • **
  • Posts: 16
  • Country: gr
    • index.php?action=treasury
  • Liked: 8
Memory Efficient "Room" Design
« on: 02:56, 14 October 18 »
Hello,

Once upon a time I have started a game that needed a "room" design. The game consisted of 32 rooms that hero navigated and to do various things.

Anyway, suppose each room is 24x24 tiles and each tile can be of 6 types (1 wall, 1 free space,  4 objects)

The most obvious design is to use an 24x24 array to represent each room, but that means 576 bytes per room. Not only it wasn't memory efficient but furthermore it also was not type-in efficient (back in time that was a serious consideration if you wanted to see your work published in a magazine)

What I thought was to split 24x24 tiles to a 3x3 blocks of 8x8 tiles, so each block could be represented by a single byte1  and that meant I needed 9 bytes for each mask. Doing the math each level could be represented by 54 bytes (9 blocks * 6 masks) which is more than 90% memory efficient than the obvious design.

But then life happened and I didn't manage to finish it.

Anyway, If I was to start again a "navigate in room" game, could you suggest some ideas or even a completely different approach to make room representation and drawing faster2 and more memory efficient?


1. Than needs an explanation: Each 8x8 tile cab be represented by a special special modified with "SYMBOL" character and then a block drawn according to symbol's mask. That of course means that some characters should be reused or the characters wouldn't be enough.
2. Function that reads character's definition and it draws to the SCREEN
« Last Edit: 12:27, 14 October 18 by menegator »

Offline andycadley

  • Supporter
  • 6128 Plus
  • *
  • Posts: 788
  • Liked: 345
Re: Memory Efficient "Room" Design
« Reply #1 on: 16:46, 14 October 18 »
Using bigger blocks constructed from smaller ones, as you suggest, is a common solution. Another is to have a list of "instructions" that define how to build up a room (i.e. draw a tree here, put a platform 10 characters wide here etc). And of course you can always just straight up compress the level data using a tool like Exomizer.

Offline Docent

  • CPC664
  • ***
  • Posts: 121
  • Country: pl
  • Liked: 90
Re: Memory Efficient "Room" Design
« Reply #2 on: 06:11, 15 October 18 »
Hello,

Once upon a time I have started a game that needed a "room" design. The game consisted of 32 rooms that hero navigated and to do various things.

Anyway, suppose each room is 24x24 tiles and each tile can be of 6 types (1 wall, 1 free space,  4 objects)

The most obvious design is to use an 24x24 array to represent each room, but that means 576 bytes per room. Not only it wasn't memory efficient but furthermore it also was not type-in efficient (back in time that was a serious consideration if you wanted to see your work published in a magazine)

What I thought was to split 24x24 tiles to a 3x3 blocks of 8x8 tiles, so each block could be represented by a single byte1  and that meant I needed 9 bytes for each mask. Doing the math each level could be represented by 54 bytes (9 blocks * 6 masks) which is more than 90% memory efficient than the obvious design.

This saving sounds huge, but you didn't take into account the 8x8 blocks itself. If you have 9 unique blocks per level, it still will take (assuming that you'll keep 8bit tile index)  9*8*8+9=585. The actual savings may appear after duplicating certain blocks on other levels.

You can keep your level walls and objects in separate tables. Use bits to represent walls and the whole level walls will take 72 bytes. Objects keep in a separate table packed into 16 bits - 2 bits of object index, 5 bits of x pos, 5 bits of y pos.
If you have 10 objects per level, the whole level description will take 92 bytes and you still have the space to add up to 60 more object types or encode some special actions on remaining free 4 bits of each object definition.

Offline Targhan

  • Supporter
  • 6128 Plus
  • *
  • Posts: 740
  • Country: fr
  • Liked: 658
Re: Memory Efficient "Room" Design
« Reply #3 on: 13:09, 15 October 18 »
Simply, as @andycadley suggested, use a custom format to encode each room. Another user had the same problem, which I answered here:
http://www.cpcwiki.eu/forum/programming/screen-encoding/msg114798/#msg114798


Hope it helps.

Offline menegator

  • CPC464
  • **
  • Posts: 16
  • Country: gr
    • index.php?action=treasury
  • Liked: 8
Re: Memory Efficient "Room" Design
« Reply #4 on: 23:40, 15 October 18 »
Simply, as @andycadley suggested, use a custom format to encode each room. Another user had the same problem, which I answered here:
http://www.cpcwiki.eu/forum/programming/screen-encoding/msg114798/#msg114798


Hope it helps.
Thank you very much.

Offline Sykobee (Briggsy)

  • 6128 Plus
  • ******
  • Posts: 662
  • Country: gb
  • Liked: 218
Re: Memory Efficient "Room" Design
« Reply #5 on: 23:43, 15 October 18 »
This is a fun aspect of programming an older system - how to fit large maps into small memories. Usually a tradeoff with flexibility (total freedom to place a block anywhere at will).


For example, how many 'items' are there on a screen? If there aren't many, their location can be stored separately. After that you have either walls of empty space, which you can represent as 1-bit per tile. Or you can have a list of commands (primitive Run Length Encoding): 25 walls, 22 floor, 2 wall, 22 floor, 2 wall, 2 floor, 18 wall ... etc - which may be more compact. Or you define 'supertiles' defining certain basic patterns (typically 2x2, 4x4 or 8x8 in size), and build your map out of these - the C64 SEUCK is an example, and many other games.

Offline menegator

  • CPC464
  • **
  • Posts: 16
  • Country: gr
    • index.php?action=treasury
  • Liked: 8
Re: Memory Efficient "Room" Design
« Reply #6 on: 23:47, 15 October 18 »
This saving sounds huge, but you didn't take into account the 8x8 blocks itself. If you have 9 unique blocks per level, it still will take (assuming that you'll keep 8bit tile index)  9*8*8+9=585. The actual savings may appear after duplicating certain blocks on other levels.

You can keep your level walls and objects in separate tables. Use bits to represent walls and the whole level walls will take 72 bytes. Objects keep in a separate table packed into 16 bits - 2 bits of object index, 5 bits of x pos, 5 bits of y pos.
If you have 10 objects per level, the whole level description will take 92 bytes and you still have the space to add up to 60 more object types or encode some special actions on remaining free 4 bits of each object definition.

The initial idea is to use a limited set of defined characters as bitmaps (20-30 characters) and use them repeatedly to produce different rooms. Using this approach you need only 54 bytes per level plus 270 [= (8+1) bytes to redefine the character * 30 (number of redefined characters)]

Your approach however is even better because it is memory efficient and doesn't limit the room design. Thank you very much!
« Last Edit: 23:50, 15 October 18 by menegator »