2d array max

[Ninjabba]

I started a new project recently in which I define several tile-based worlds. From the few things I've learned about game programming, one of them is that you want your world defined in a 2d array. Since bigger is better, I would like as much matrices defined as possible for my different worlds. However, I found out I can only store one 100x100 array or about 12 40x40 arrays before running out of . I was wondering if someone can suggest me something for defining a large number of worlds?

 

Thanks in advance!

[GroovyBee]

How complex is the "world" you are trying to create? Could it be tiled into such a way as to make meta tiles? Lets say you have your 100x100 unsigned char array. Each byte in the array is used to index a 2x2 meta tile that is made up 4 normal tiles.

 

E.g. If you access the tile at [50][50] and get the value 37. Value 37 would be a meta tile composed of four smaller tiles.

 

+----+----+
| 23 | 18 |
+----+----+
| 48 | 99 |
+----+----+

 

You could probably write something in C/C++/Perl etc. to parse your level data and create meta tiles from it.

 

Depending on the style of game run length encoding might also help.

[RevEng]

If some of the arrays would be used for generating repeatable but unpredictable data, like unique scenery or enemy placement, you could probably instead use a LFSR seeded with the player position.

 

Pitfall used this to great effect on the Atari 2600, to generate 255 unique screens with a small amount of rom. A 16-bit LFSR can produce 65535 unique values.

[Wookie]

So here's how I was thinking I would do a "continuous" tiled world. The Lynx resolution is 160x102. If you choose tiles as 20x20 pixels, you get 8 across and 5 down. If you have 255 different tiles you just need a single byte as your tile index. To make a world that can scroll in any direction, you need to think in terms of the virtual screen. The virtual screen consists of "guard bands" of tiles surrounding the virtual screen. The guard bands contain the tiles that will be partially shown when the world scrolls a few pixels in any direction. The guard band consists of two bands of tiles, the immediately visible tiles (BB) and the next to be loaded tiles (NN). In sheer number of pixels, the virtual screen is 240x180 pixels.

 

    +----+----+----+----+----+----+----+----+----+----+
    | NN | NN | NN | NN | NN | NN | NN | NN | NN | NN |
+----+----+----+----+----+----+----+----+----+----+----+----+
| NN | BB | BB | BB | BB | BB | BB | BB | BB | BB | BB | NN |
+----+----+====+====+====+====+====+====+====+====+----+----+
| NN | BB I    |    |    |    |    |    |    |    I BB | NN |
+----+----+----+----+----+----+----+----+----+----+----+----+
| NN | BB I    |    |    |    |    |    |    |    I BB | NN |
+----+----+----+----+----+----+----+----+----+----+----+----+
| NN | BB I    |    |    |    |    |    |    |    I BB | NN |
+----+----+----+----+----+----+----+----+----+----+----+----+
| NN | BB I    |    |    |    |    |    |    |    I BB | NN |
+----+----+----+----+----+----+----+----+----+----+----+----+
| NN | BB I    |    |    |    |    |    |    |    I BB | NN |
+----+----+====+====+====+====+====+====+====+====+----+----+
| NN | BB | BB | BB | BB | BB | BB | BB | BB | BB | BB | NN |
+----+----+----+----+----+----+----+----+----+----+----+----+
    | NN | NN | NN | NN | NN | NN | NN | NN | NN | NN |
    +----+----+----+----+----+----+----+----+----+----+

 

You kick off the loading of the NN tiles as soon as the first pixels of the BB tiles becomes visible.

 

The representation of the world tiles can be stored as an array that is 70 bytes long plus 4 arrays, 2 that are 7 bytes long, and 2 that are 10 bytes long for storing the sprite indexes of the outer bands of tiles. Any given tile's location in the array can be calculated by (10 * y) + x. If the upper left corner tile is the first item in the array, then x goes right and y goes down.

 

The real trick with this kind of system is knowing how many unique tiles you can have in memory at one time and how to manage loading in the outer bands of tiles and updating the 70 byte world array when needed. If you had a unique sprite for every tile in the 70 byte array and they weren't compressed in any way, you'd use up something like 20K of the 64K of memory. So if you limited yourself to 16 or even 32 unique tiles, that would mean your world would only take up 6400 bytes or 12800 bytes respectively if the sprites aren't compressed in any way.

 

I'll leave it as an exercise to the reader to figure out how to manage the number of unique tiles in memory at once. So let's explore the limits of a system like this. Let's assume you're making a 512KB game. Your pages use all 11 bits of the page address and are therefore 2 KB in size. 256 x 2KB pages gives you the 512KB ROM size. If you set aside just one page, 2KB to store a tile map, you could have a world that is roughly 45x45 tiles which is 4.5 lynx screen widths by 9 lynx screen heights. If your game engine scrolled at 1 tile (20 pixels) per second, then the player could walk from one side to the other in 35 seconds. If you kept your world map square and dedicated half of your ROM space to just the tile map, you could have a world that was 512 tiles on a side. Scrolling at 1 tile per second would mean the player could walk from one side to the other in 8 minutes, 22 seconds. That's quite a trek. I'm sure that you can figure out a good game that will fit in a world that large.

 

But we don't need to use that much memory for the tile map. With the meta-tile idea suggested above, you can define meta-tiles that are 16x16 tiles in size. That takes up exactly 256 bytes of memory. With a world definition consisting of meta-tile indexes and their locations in the world you don't need very much memory, a few hundred bytes, to specify the location of several hundred meta-tiles. More importantly, the world map need not be square. You can create arbitrary shapes by placing and overlapping meta-tiles (more on this later).

 

Here are more details on this design:

0. There is a maximum of 128 unique tile sprites. This means a 7 bit sprite index and a single bit for walkable. The Lynx encodes collision data directly into the sprites so the 1 bit for "walkable" is used to tell the sprite engine to not do any collision processing making the drawing of "walkable" sprites 1/3 faster.

1. The world map has a maximum width and height of 256 tiles. This is so we can use a single byte to represent the X and Y coordinates of the upper-left corner of each meta-tile. If you wanted to make meta-tiles only placeable at even tile coords or even every 3rd or 4th tile you could make the world 2, 3, or 4 times as big without needing any more bits to store the meta-tile coordinates.

2. Each tile is 20x20 pixels.

3. Each meta tile is 16x16 tiles in size.

4. The world map consists of an array of 4 byte tuples that reference and place each meta-tile. The first two bytes specify the meta-tile's location in the ROM (10 bits) and any flags (the remaining 6 bits). The plan is to only dedicate the upper half of the ROM space to meta-tiles and world maps. A 16x16 meta-tile takes up 256 bytes of memory giving 8 meta-tiles per 2KB page. That means I need a 3 bit index into each page and 7 bits to tell which page to look in. The flags are used for specifying draw order (3 bits) for overlapping meta-tiles and palette index (3 bits). The palette index allows the same sprites to be drawn in different palettes (e.g. daytime sunny, daytime rainy, night time, night time rainy, under world, etc).

 

Like I said above, meta-tiles can overlap. If we have meta-tile 1 located at 10,10 and meta-tile 2 located at 20,20, it would look like this:

 

  10                                      20
10 x---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
20 +---+---+---+---+---+---+---+---+---+---xxxxxxxxxxxxxxxxxxxxxxxxx---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 x 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  +---+---+---+---+---+---+---+---+---+---x---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 x 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  +---+---+---+---+---+---+---+---+---+---x---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 x 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  +---+---+---+---+---+---+---+---+---+---x---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 x 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  +---+---+---+---+---+---+---+---+---+---x---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 x 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  +---+---+---+---+---+---+---+---+---+---x---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 x 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
  +---+---+---+---+---+---+---+---+---+---x---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                                          | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
                                          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

 

Again, the upper bits in the level definition array that specified each meta-tile would specify the draw order. So if meta-tile 1 in the level has a draw order of 0 and meta-tile 2 has a draw order of 1, then we would draw the tiles from meta-tile 2 instead of the tiles from meta-tile 1. This is arbitrary, I'm just decided that there will be 3 bits of draw order and that larger numbers mean closer to the viewer.

 

This is just one way of doing it but the numbers work out nicely this way. You can play around with them of course. There is no reason a meta-tile can't be 8x8 tiles or even 32x32 tiles.

 

To figure out what to draw, the game just has to maintain the player's current X,Y in tile space (i.e. which tile in the level it is on) and what U,V in pixel space the tiles are scrolled so that they can be rendered correctly. From the X,Y coords, it's trivial to calculate which meta-tile the player is on.

 

It is important to remember that the game engine will only have the level definition and, if meta-tile overlap is minimized, at most 3 or 4 meta-tile definitions. So if there are 4 meta-tile definitions in RAM, that's only 1KB of memory. For each meta-tile the level definition needs to have 4 bytes of RAM. So in a world with 64 meta-tiles, that's only 256 bytes plus the 1KB for the meta-tile definitions. Then of course you need to have the tile sprites in memory but if you limit yourself on the number of unique sprites you'll be able to make them fit.

 

Now, if all this can be done in a 512KB ROM, image what could be done with a 1MB ROM or even a 16MB ROM that uses an i2c I/O expander chip to expand the ROM address bus.

 

--Wookie

 

BTW, hex tile maps can be done the exact same way except that you need three rows of guard band tiles instead of just two because every other row of hex tiles is offset by half a tile.

Edited September 11, 2010 by Wookie

[Wookie]

I should note that when I say a tile is 20x20 pixels, that's the rough footprint of a tile if the world is rendered top down. The sprite itself does not have to be limited to a 20x20 box. For instance, isometric tiles will be 20 pixels wide, but the oblique angle of the tile means that it is squashed. But still, if the tile has a tree on it, it may actually be 30 pixels tall in total. The 20x20 rule is just a rough grid that is a clean multiple of the Lynx screen resolution and it makes math easier in the rendering engine.

 

--Wookie

[Ninjabba]

Thanks for the ideas!

I'm aiming at making some simple RPG, but would love to put a lot of exploration in it.

My tileworld consist of 16x16 pixels which is quite a standard in tile-games, and I have my character walking around using some smooth-scrolling over the world map at this point. I am considering to generate dungeons procedurally using some maze-generation algorithm, but I don't feel like generating the world map since it needs to be fixed. And I want it to be big.

 

The meta-tiling sounds like an idea I could implement without too much trouble, and I'll have to read into the rest with more care to understand the ideas.

 

I'm not using any compression for my sprites and I'm not very good at bit/byte math, which is quite worrying for me because I'm afraid half way the project I'm going to encounter some "out of memory" error.

Edited September 11, 2010 by Ninjabba

[matashen]

Thanks for the ideas!

I'm aiming at making some simple RPG, but would love to put a lot of exploration in it.

My tileworld consist of 16x16 pixels which is quite a standard in tile-games, and I have my character walking around using some smooth-scrolling over the world map at this point. I am considering to generate dungeons procedurally using some maze-generation algorithm, but I don't feel like generating the world map since it needs to be fixed. And I want it to be big.

 

The meta-tiling sounds like an idea I could implement without too much trouble, and I'll have to read into the rest with more care to understand the ideas.

 

I'm not using any compression for my sprites and I'm not very good at bit/byte math, which is quite worrying for me because I'm afraid half way the project I'm going to encounter some "out of memory" error.

 

You can reload your World from Cartridge, then you need only two chars or int where you hold your position in the big world. So you can load the map for example 10x10 tiles set the counter to x=0 and Y=0means load from cartridge byte 0-99. need the next block in x, you load the next 100 bytes from the same memoryblock... etc

 

loading some byte are not very timeconsuming.

 

Only a idea from me, i dont testet it, cause i dont wrote such a game.

 

Regards Matthias

[+karri]

I'm not using any compression for my sprites and I'm not very good at bit/byte math, which is quite worrying for me because I'm afraid half way the project I'm going to encounter some "out of memory" error.

 

You will run out of memory very fast with graphics.

 

When I wrote solitaire I had to read in many cards during every display cycle. The whole card deck is much bigger that the Lynx RAM.

 

Basically I had a function that returned me a pointer of the sprite to be drawn.

 

If it happens to be in memory - nice.

If not, then load it in over some other sprite and draw it.

 

You can even make space for just one tile and use a loop like:

 

while ( ...) {
  load_tile();
  draw_tile();
}

 

The most important thing is to plan memory use. The main game engine can reside in memory forever.

 

It is a good idea to have a separate segment that can be read in on demand so that it overwrites some other data that is not needed. Example:

 

Startdreamer 3D flying and fighting, trading, browsing galaxy map all share the same memory area.

 

switch (mode) {
case FLYING:
   load(flying_segment);
   starfly(); // Enter flying program
   break;
case TRADING:
   load(trading_segment);
   trading(); // Enter trading program
   break;
case MAP:
   load(map_segment);
   map(); // Enter galaxy map browsing program
   break;
}

 

All C-libraries, shared variables etc remain in RAM at all time. Only routines that are not shared between different subprograms are put in segments.

 

When I compile my code in cc65 I declare some parts of the code to reside in some segment like:

 

CODE_SEGMENT=STARFLY_CODE
DATA_SEGMENT=STARFLY_DATA
RODATA_SEGMENT=STARFLY_RODATA
BSS_SEGMENT=STARFLY_BSS

objects= \
       matrix.o \
       trig.o \
       vbasis.o \
       zeropage.o \
       starfly.o

SEGMENTS=--code-name $(CODE_SEGMENT) \
       --rodata-name $(RODATA_SEGMENT) \
       --bss-name $(BSS_SEGMENT) \
       --data-name $(DATA_SEGMENT)

# Rule for making a *.o file out of a *.c file
%.o: %.c
       $(CC) $(CFLAGS) $(SEGMENTS) -o $(patsubst %c, %s, $(notdir $<)) $<
       $(AS) -o $@ $(AFLAGS) $(*).s
       $(RM) $*.s

 

 

The linker has then info of where to place the segments. It is clever enough to re-use the memory space for all the functions. It is up to me to read in the segment before I start calling functions in it. If I forget then the CPU will jump into garbage.

 

MEMORY {
   ...
   BANK8: start = $6A40, size = $2315, define = yes, file = %O;
   BANK9: start = $6A40, size = $2315, define = yes, file = %O;
   BANK10: start = $6A40, size = $2315, define = yes, file = %O;
   ...
}

SEGMENTS {
   ...
   # Stardreamer galaxy map
   STARMAP_CODE: load = BANK8, type = ro, define = yes;
   STARMAP_RODATA: load = BANK8, type = ro, define = yes;
   STARMAP_DATA: load = BANK8, type = rw, define = yes;
   STARMAP_BSS: load = BANK8, type = bss, optional = yes;

   # Stardreamer flying
   STAFLY_ZP: load = ZP, type = zp;
   SERZP: load = ZP, type = zp;
   STARFLY_CODE: load = BANK9, type = ro, define = yes;
   STARFLY_RODATA: load = BANK9, type = ro, define = yes;
   STARFLY_DATA: load = BANK9, type = rw, define = yes;
   STARFLY_BSS: load = BANK9, type = bss, optional = yes;

   # Stardreamer trading
   STARTRA_CODE: load = BANK10, type = ro, define = yes;
   STARTRA_RODATA: load = BANK10, type = ro, define = yes;
   STARTRA_DATA: load = BANK10, type = rw, define = yes;
   STARTRA_BSS: load = BANK10, type = bss, optional = yes;
   ...
}

Edited December 16, 2010 by karri

[Ninjabba]

Thanks for the explanation Karri! But since this post I've dived into your template pretty deep, and I have now about 30 banks switching all the time to have it all fit in memory. Granted, it could be optimized a lot to fit more than I have now, but I'm quite pleased how its working out. Couldn't have done it without your template, so many thanks for that.

 

PS. I'm really looking forward to the StarDreamer project you're working on. I actually accidentally bumped into Ian Bell a few months ago on a conference and had quite some interesting talk with him and eventually did a small interview on Elite. During my conversation with him I mentioned this project as well I think.

[+karri]

Thanks for the explanation Karri! But since this post I've dived into your template pretty deep, and I have now about 30 banks switching all the time to have it all fit in memory. Granted, it could be optimized a lot to fit more than I have now, but I'm quite pleased how its working out. Couldn't have done it without your template, so many thanks for that.

 

PS. I'm really looking forward to the StarDreamer project you're working on. I actually accidentally bumped into Ian Bell a few months ago on a conference and had quite some interesting talk with him and eventually did a small interview on Elite. During my conversation with him I mentioned this project as well I think.

 

Nice! The power behind Elite was the open-ended design. You could become a honest trader or a pirate looting others. This part of Elite is something I would like to keep. Elite was just so slow to play compared to modern games. My opinion is that one mission should be playable in a few minutes. Nobody wants to fly without anything happening for 10 minutes.

 

Naturally modern games influence my opinions and Zaku really set a new standard in playability and eye-candy for the Lynx. So StarDreamer won't come out in 2011 except perhaps some alpha-release.

 

Another thing is that I am much involved in navigation design of ships. So the craft is likely to have all kind of modern features that make flying and target handling easier than in Elite. The crew can then concentrate on the missions (like pirating innocents traders).

 

The whole game should also be playable by joypad plus A and B. With only single click actions.

 

--

Regards,

 

Karri