Optimizing tilemapping / sd card access for large games

Libraries, utilities, bootloaders...

Optimizing tilemapping / sd card access for large games

Postby Sorunome » Sun Mar 20, 2016 11:09 pm

So, I thought, why not optimize tilemapping for large games?
By that I mean that quite a few people are complaining about the gamebuino not having enough ram, which i can totally understand, 2KB is very limited. Nevertheless I thought of trying myself on a simple tilemapper + moving engine which loads it's tilemap data off of the SD card, only to see actually how limited we are.

At the end of the game I ended up with 12,832 bytes of PROGMEM (41%) and only 874 bytes of ram for the global variables!

While I can clearly see the PROGMEM being an issue rather quickly, I am quite surprised (in a positive way) with how few RAM I managed to pass.


Now you are probably saying "wait a second sorunome, a screenbuffer is 512 bytes and sd card accessing needs a buffer of 512 due to the sector size....that alone already adds up to 1024 bytes"

Well, you are totally correct, but it turns out you don't really need that big of a buffer for the sd accessing, you might as well only store like the first 10 bytes of the sector and just ignore everything else, so on I went modifying tinyFAT for a read-only mode which allows you to specify buffers!

However, soon I ran into an issue: since I didn't want to look too deep into how FAT is working and copypasted a lot from tinyFAT the initializing and file searching would be quite hard with a buffer less than 512 bytes........my sollution was that for initializing the filesystem and searching for files I use the screenbuffer! Yes, this will corrupt the screen buffer every time you search for files, but I designed my custom file library in a way so that you can keep a file easily open throughout the whole game, the class only has one 2-byte variable so I guess that's about the size of ram needed to keep a file open, so the thought is to just open all the files in the beginning.

My demo with 874 bytes of ram include the following bigger chunks I can pinpoint easily:
512 (screen buffer)
96 (tilemap buffer)
24 (sprites)
--> 632 bytes --> 242 bytes used by misc. other stuff, such as camera position, open files, player positions etc. The gamebuino library itself also has quite some things.


For the sprites, I thought of maybe writing an engine which will dynamically flash the sprites to PROGMEM from the sdcard, so that a screen can maybe only consist of like 20 different sprites.


Anyhow, I will upload code once I got my sd library to not derp around if your program is larger than 512 bytes (one cluster), currently it assumes that data is in sequence while it may be fragmented. Or maybe I should leave it that way as game files aren't edited on the card thus fragmenting is way more unlikely to happen, what do you guys think?


Also, if people are willing to help (story + map + sprites + programming) I'd be willing to push this forward to an actual game! ^.^
Last edited by Sorunome on Mon Mar 21, 2016 1:09 pm, edited 1 time in total.
User avatar
Sorunome
 
Posts: 629
Joined: Sun Mar 01, 2015 1:58 pm

Re: Optimizing tilemapping for large games

Postby deeph » Mon Mar 21, 2016 5:43 am

Nice, can't way to look at your code :)

Are you using your asm sprite routine ? Because yesterday I tested the tillemapper I coded with it (well, a little enhanced, since I'm making a game with it), and I got strange sounds from the speakers and strange behavior when the player is either facing up or right with animated tiles. I can't understand why, I didn't experienced this with the classic sprite routine...

So do you plan on making your own game (RPG) ? With my game (a pokemon-clone), I'm actually at 14,128 bytes (43%) of PROGMEM and 1,237 bytes of RAM, which include the tilemapper, player handling, 3 maps, events handling (warps/dialogs...), and a start for the battle engine. I still don't know if I'll be able to put everything I need in the PROGMEM. I can show you the code eventually.
deeph
 
Posts: 52
Joined: Mon Jul 13, 2015 6:09 am
Location: France

Re: Optimizing tilemapping for large games

Postby Sorunome » Mon Mar 21, 2016 8:01 am

deeph wrote:Nice, can't way to look at your code :)

Are you using your asm sprite routine ? Because yesterday I tested the tillemapper I coded with it (well, a little enhanced, since I'm making a game with it), and I got strange sounds from the speakers and strange behavior when the player is either facing up or right with animated tiles. I can't understand why, I didn't experienced this with the classic sprite routine...

So do you plan on making your own game (RPG) ? With my game (a pokemon-clone), I'm actually at 14,128 bytes (43%) of PROGMEM and 1,237 bytes of RAM, which include the tilemapper, player handling, 3 maps, events handling (warps/dialogs...), and a start for the battle engine. I still don't know if I'll be able to put everything I need in the PROGMEM. I can show you the code eventually.


Do you have its map data being read off of the sd card, though? Because if so that is very impressive!

As for the sprite routine, the asm one I presented doesn't have clipping (it assumes the sprite is fully on screen). Lukily I found somewhere in that same thread a version with full clipping, the lower clipping was broken, though, so I fixed that. The sound was generated on your end as you overwrote random ram areas, probably those used for sound.

As for rpg-making, as mentioned I do not intend to push this very far if people wouldn't help me.
Thanks for your interest, though!
User avatar
Sorunome
 
Posts: 629
Joined: Sun Mar 01, 2015 1:58 pm

Re: Optimizing tilemapping for large games

Postby Sorunome » Mon Mar 21, 2016 12:09 pm

As promised, code time!

First off, the repo for the custom FAT library is here: https://github.com/Sorunome/GB_Fat

I have straight up a little optimization question about the library, as you can see here https://github.com/Sorunome/GB_Fat/blob ... #L127-L128 I need a uint8_t buf[2]; only to be able to generate a uint16_t, is there some way to implicitally cast a uint16_t to a uint8_t[2] ?

Anyhow, now on to the demo! It consists of two files:

main.ino:
Code: Select all
#include <SPI.h>
#include <Gamebuino.h>
#include <EEPROM.h>
#include <GB_Fat.h>
Gamebuino gb;
#define TILEMAP_WIDTH 12
#define TILEMAP_HEIGHT 8
byte camX = 0;
byte camY = 0;
byte sprites[] = {0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
                  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};

byte sprite_player[] = {0xAA,0x55,0xAA,0x55,0xAA,0x55,0xAA,0x55};
byte tilemap[TILEMAP_WIDTH * TILEMAP_HEIGHT];

GB_Fat sd;
GB_File file;

#include "graphics.h"

class Player {
  byte x=8,y=8;
  public:
    void update(){
      if(gb.buttons.repeat(BTN_RIGHT,0)){
        x++;
      }
      if(gb.buttons.repeat(BTN_LEFT,0)){
        x--;
      }
      if(gb.buttons.repeat(BTN_UP,0)){
        y--;
      }
      if(gb.buttons.repeat(BTN_DOWN,0)){
        y++;
      }
      sprite_xor(sprite_player,x,y);
      moveCam(x - (LCDWIDTH / 2), y - (LCDHEIGHT / 2));
    }
};

void setup() {
  // put your setup code here, to run once:
  gb.begin();
  gb.setFrameRate(40);
  gb.display.clear();
  gb.display.println(F("loading card..."));
  gb.display.update();


 
  if(sd.init(gb.display.getBuffer(),SPISPEED_VERYHIGH)!=NO_ERROR){
    gb.display.clear();
    gb.display.print(F("SD card not found."));
    gb.display.update();
    while(1);
  }
  gb.display.clear();
  gb.display.println(F("seaching for file card..."));
  gb.display.update();
 
  file = sd.open("DATA.DAT",gb.display.getBuffer());
  if(!file.exists()){
    gb.display.clear();
    gb.display.print(F("Couldn't open file."));
    gb.display.update();
    while(1);
  }
  gb.display.clear();
  gb.display.println(F("card found"));
  gb.display.update();
 
  file.read(tilemap,0,96);
  /*
  byte buffer[11];
  buffer[10] = '\0';
  file = sd.open("TEST.TXT",gb.display.getBuffer());
  if(!file.exists()){
    gb.display.clear();
    gb.display.print(F("Couldn't open file."));
    gb.display.update();
    while(1);
  }
  file.read(buffer,32768 - 5,10);
  gb.display.clear();
  gb.display.println(reinterpret_cast<const char*>(buffer));
  gb.display.update();
  while(1);*/
}
Player player;
void loop() {
  // put your main code here, to run repeatedly:
  if(gb.update()){
    drawTilemap();
    player.update();
  }
}


graphics.h:
Code: Select all
void sprite_xor(byte data[], byte xx, byte yy){
  int8_t x = xx - camX;
  int8_t y = yy - camY;
 
  uint8_t* buf = (((y+8)&0xF8)>>1) * 21 + x + gb.display.getBuffer();
  asm volatile(
  "mov R20,%[y]\n\t"
  "ldi R17,7\n\t"
  "add R20,R17\n\t"
  "brmi End\n\t"
  "cpi %[y],48\n\t"
  "brpl End\n\t"
 
  "inc R20\n\t"
  "ldi R16,8\n\t"
  "andi R20,7\n\t"
  "cpi R20,0\n\t"
  "breq LoopAligned\n"
  "LoopStart:\n\t"
 
    "tst %[x]\n\t"
    "brmi LoopSkip\n\t"
    "cpi %[x],84\n\t"
    "brcc LoopSkip\n\t"

    "ld R17,Z\n\t"
    "eor R18,R18\n\t"
    "mov R19,R20\n\t"
    "clc\n\t"
    "LoopShift:\n\t" // carry is still reset from the cpi instruction or from the dec
      "rol R17\n\t"
      "rol R18\n\t"
      "dec R19\n\t"
      "brne LoopShift\n\t"

    "tst %[y]\n\t"
    "brmi LoopSkipPart\n\t"
   
    "ld R19,X\n\t"
    "eor R19,R17\n\t"
    "st X,R19\n\t"
  "LoopSkipPart:\n\t"

    "cpi %[y],40\n\t"
    "brpl LoopSkip\n\t"
   
    "ld R19,Y\n\t"
    "eor R19,R18\n\t"
    "st Y,R19\n\t"

  "LoopSkip:\n\t"
    "eor R18,R18\n\t"
    "ldi R19,1\n\t"
    "add R26,R19\n\t" // INC DOESN'T CHANGE CARRY!
    "adc R27,R18\n\t"
    "add R28,R19\n\t"
    "adc R29,R18\n\t"
    "add R30,R19\n\t"
    "adc R31,R18\n\t"
   
    "inc %[x]\n\t"
    "dec R16\n\t"
    "brne LoopStart\n\t"
  "rjmp End\n"
  "LoopAligned:\n\t"
    "tst %[x]\n\t"
    "brmi LoopAlignSkip\n\t"
 
    "cpi %[x],84\n\t"
    "brcc LoopAlignSkip\n\t"
   
    "ld R17,Z\n\t"
    "ld R18,X\n\t"
    "eor R18,R17\n\t"
    "st X,R18\n\t"
  "LoopAlignSkip:\n\t"
    "ldi R18,1\n\t"
    "add R26,R18\n\t"
    "adc R27,R20\n\t"
    "add R30,R18\n\t"
    "adc R31,R20\n\t"
    "inc %[x]\n\t"
    "dec R16\n\t"
    "brne LoopAligned\n"
  "End:\n\t"
  ::"x" (buf - 84),"y" (buf),"z" (data),[y] "r" (y),[x] "r" (x):"r16","r17","r18","r19","r20");
}
void drawTilemap(){
  int8_t startDdx = (-camX) / 8;
  int8_t startDdy = (-camY) / 8;
  int8_t maxDdx = (LCDWIDTH + 8 - 1 + camX) / 8;
  int8_t maxDdy = (LCDHEIGHT + 8 - 1 + camY) / 8;
  if(TILEMAP_WIDTH < maxDdx){
      maxDdx = TILEMAP_WIDTH;
  }
  if(TILEMAP_HEIGHT < maxDdy){
      maxDdy = TILEMAP_HEIGHT;
  }
  if(startDdx < 0){
      startDdx = 0;
  }
  if(startDdy < 0){
      startDdy = 0;
  }
  for(byte ddy = startDdy;ddy < maxDdy;ddy++){
    for(byte ddx = startDdx;ddx < maxDdx;ddx++){
      sprite_xor(sprites + tilemap[ddy*TILEMAP_WIDTH + ddx]*8,ddx*8,ddy*8);
    }
  }
}
void moveCam(int8_t x,int8_t y){
  if(x < 0){
    camX = 0;
  }else if(x > (TILEMAP_WIDTH*8) - LCDWIDTH){
    camX = (TILEMAP_WIDTH*8) - LCDWIDTH;
  }else{
    camX = x;
  }
  if(y < 0){
    camY = 0;
  }else if(y > (TILEMAP_HEIGHT*8) - LCDHEIGHT){
    camY = (TILEMAP_HEIGHT*8) - LCDHEIGHT;
  }else{
    camY = y;
  }
}

As always, suggestions are welcome :P
You will find the required DATA.DAT file attached.

So, how does this thing work?
Including is quite obvious: #include <GB_Fat.h>

Next up you will need an sd handler, GB_Fat sd; This sd handler will be used to "open" files and to initialize.
The filehandler (GB_File file;) is ideally one per open file you need, the sd handler will create it.

Well, before you use the sd card you will need to initialize it: sd.init(gb.display.getBuffer(),SPISPEED_VERYHIGH)
Note how i set here gb.display.getBuffer() as a parameter, as already mentioned it uses external buffers, the init function requires a 512 bytes buffer. I just used SPISPEED_VERYHIGH because why not :P IDK really how much of a difference it makes, that is one of the parts copypasted from tinyFAT

The library will not make any checks later on for if you actually initialized the sd handler or not, so be sure to do so!

Next up we have file opening! file = sd.open("DATA.DAT",gb.display.getBuffer()); This again requires a 512 bytes buffer, ideal for the screen buffer.

Now is the key part: file.read(tilemap,0,96); first parameter is the buffer, as you can tell I didn't use the screen buffer so this line will not corrupt it! Next is the offset in bytes, and last is the size. So this will read 96 bytes starting from byte 0 into tilemap.
The library does not make checks if the end of the file was reached, due to how it works the buffer will end up with garbage if read beyond the file. However the library won't ever write any more than size bytes to the buffer! Yay!

Little tricks:
Due to how SD cards work you have the greatest peformance if you align your data to 512-byte blocks, that shouldn't make a big difference, though.
However, what would make a bigger difference is once your filesize hits more than 32768 bytes, as the library will internally need to perform an extra read.

DISCLAIMER: As this is something very low level I just wanne say that I am not responsible for any damage this would do to your gamebuino, even though I am positive that it won't do anything.
I already found it randomly when flashing that the screen wouldn't turn on, however once it turned on after flashing it stayed no matter how often I resetted the gamebuino, so I'll blame USB flashing for now. If it doesn't turn on I managed to get it back by flashing the LOADER.HEX (by holding down c while turning on) reptatitivly and re-inserting the card while turned on.
Attachments
DATA.DAT.zip
(186 Bytes) Downloaded 594 times
User avatar
Sorunome
 
Posts: 629
Joined: Sun Mar 01, 2015 1:58 pm

Re: Optimizing tilemapping for large games

Postby deeph » Mon Mar 21, 2016 5:09 pm

Sorunome wrote:Do you have its map data being read off of the sd card, though? Because if so that is very impressive!

No, I'm reading maps from the PROGMEM, but I don't foresee to have big ones for my game, so it's the best solution I guess.

Sorunome wrote:As for the sprite routine, the asm one I presented doesn't have clipping (it assumes the sprite is fully on screen). Lukily I found somewhere in that same thread a version with full clipping, the lower clipping was broken, though, so I fixed that. The sound was generated on your end as you overwrote random ram areas, probably those used for sound.

Nice, thank you for fixing it, but I think that you should update your post then ;)

Sorunome wrote:As for rpg-making, as mentioned I do not intend to push this very far if people wouldn't help me.

I'd like to make a game with you, and could reuse some of the tools/code I made for my own project :) Why not start a thread ?

I'll look more in details your custom library and clean my own code to post it when I have the time.
deeph
 
Posts: 52
Joined: Mon Jul 13, 2015 6:09 am
Location: France

Re: Optimizing tilemapping for large games

Postby Sorunome » Mon Mar 21, 2016 6:03 pm

deeph wrote:
Sorunome wrote:Do you have its map data being read off of the sd card, though? Because if so that is very impressive!

No, I'm reading maps from the PROGMEM, but I don't foresee to have big ones for my game, so it's the best solution I guess.
Well, if you run out of PROGMEM you might want to switch to something like this, then ^.^
deeph wrote:
Sorunome wrote:As for the sprite routine, the asm one I presented doesn't have clipping (it assumes the sprite is fully on screen). Lukily I found somewhere in that same thread a version with full clipping, the lower clipping was broken, though, so I fixed that. The sound was generated on your end as you overwrote random ram areas, probably those used for sound.

Nice, thank you for fixing it, but I think that you should update your post then ;)
Done!
deeph wrote:
Sorunome wrote:As for rpg-making, as mentioned I do not intend to push this very far if people wouldn't help me.

I'd like to make a game with you, and could reuse some of the tools/code I made for my own project :) Why not start a thread ?

I'll look more in details your custom library and clean my own code to post it when I have the time.

will do ^.^
User avatar
Sorunome
 
Posts: 629
Joined: Sun Mar 01, 2015 1:58 pm

Re: Optimizing tilemapping / sd card access for large games

Postby Sorunome » Tue Mar 22, 2016 8:57 pm

So, I benchmarked this library for read-speed now using three different sd cards and two different gamebuinos.

One 2GB micro sd card and two different 128MB micro sd cards, the ones that came with the gamebuino

Here are the raw results:
Code: Select all
Gamebuino #1:

2GB sd card:
Starting speed benchmark....
10000 times (5120000 bytes ) read in 34631636 microseconds
147841.68 bytes per second
144.38 kilobytes per second

128MB card #1:
Starting speed benchmark....
10000 times (5120000 bytes ) read in 31541664 microseconds
162324.98 bytes per second
158.52 kilobytes per second

128MB card #2:
Starting speed benchmark....
10000 times (5120000 bytes ) read in 32531620 microseconds
157385.34 bytes per second
153.70 kilobytes per second



Gamebuino #2:

2GB sd card:
Starting speed benchmark....
10000 times (5120000 bytes ) read in 34719360 microseconds
147468.15 bytes per second
144.01 kilobytes per second

128MB card #1:
Starting speed benchmark....
10000 times (5120000 bytes ) read in 31538812 microseconds
162339.65 bytes per second
158.53 kilobytes per second

128MB card #2:
Starting speed benchmark....
10000 times (5120000 bytes ) read in 32530728 microseconds
157389.65 bytes per second
153.70 kilobytes per second

What's interesting is that the 2GB has lowre read speeds, but speeds are pretty consistent accross multiple benchmarks (I did every benchmark three times, the difference was only a few microseconds every time)

I think it's fair to say that you can read from the sd-card atleast at a speed of 140KB/s which is probably more than enough for most scenareos
User avatar
Sorunome
 
Posts: 629
Joined: Sun Mar 01, 2015 1:58 pm


Return to Software Development

Who is online

Users browsing this forum: No registered users and 23 guests

cron