array assignment?

Understanding the language, error messages, etc.

Re: array assignment?

Postby 94k » Thu Jul 31, 2014 12:57 am

yodasvideoarcade wrote:Yes, that's what I wanted to do, but you said 896 bytes would be too much, since there's only 1.5kb of RAM.

Is there another data-type I can use? The values are only 0-15, so I could use nibbles instead. Does that data-type exist? A nibble-array?
Or is a bit-array possible, so I can just store a "modified" bit for each position?

16 values need 4 bit, so you could store two values in each byte. You could access them with bitmagic like so:
Code: Select all
#get value of field 201 (odd)
value1 = field[201/2] & 0b1111;
#get value of field 200 (even)
value2 = field[200/2] >> 4;

or, more generally you could use a function:
Code: Select all
byte get(byte* field, int position) {
  if(position & 1) {
    #position is odd
    return field[position/2] & 0b1111;
  } else {
    return field[position/2] >> 4;
}

That way you could store the values of 896 fields in 896/2 = 448 bytes, which might fit.
It's only is a factor of 2, but maybe that's enough. rodot's method could work too, but you'd have to check each item to see if there's one on a specific field, depending on the amount of items this might be slow, the above method is faster at the cost of using more memory.
User avatar
94k
 
Posts: 44
Joined: Sun Jul 27, 2014 9:41 pm
Location: Germany

Re: array assignment?

Postby yodasvideoarcade » Thu Jul 31, 2014 1:25 am

Let's get it straight: It's PacMan, and there are 122 dots to eat, plus 4 power pills. There are 16 different types of tiles (corners, straights, dots, pills), a total of 896 tiles make the playfield.

The only way I can think of to handle which dots have been eaten, is to store them in a bit-array, if something like this exists.
User avatar
yodasvideoarcade
 
Posts: 102
Joined: Sat Apr 19, 2014 10:48 am
Location: Frankfurt/Germany

Re: array assignment?

Postby 94k » Thu Jul 31, 2014 10:49 am

Bit arrays exist, but as far as I know each bit is padded to a byte (I might be wrong on this one), so you probably want to use the whole byte.
I'd store the maze in PROGMEM (i.e. corners, straights) and the dots/pills in a bytarray with 4 tiles per byte (on a tile you can either have nothing, a pill, a dot (or both), which comes down to 2 bit/tile or 4 tiles per byte). That way you'd need 224 bytes of memory.

let's say you apply the following masks:
0b00: the tile has no item
0b01: there's a dot on the tile
0b10: there's a pill on the tile
0b11: there's a dot and a pill on the tile (this most likely won't happen)
a byte that looks like 0b01010110 (01 01 01 10) would then imply that it's corresponding tiles contain a dot, a dot, a dot and a pill. You'll probably want to use bitwise operators (most likely a combination of "and", "or" and shifts) to read and set your item array.

rodots method would require at least 2 byte/item, which comes down to 126*2 = 252 bytes total and be considerably slower (as you'd have to traverse the entire list to check if a given tile has a item).

Edit:
To be more specific, a code that gives you the item(s) for a specific tile could look like this:
Code: Select all
# returns 0 for no item, 1 for a dot, 2 for a pill and 3 for both
byte getItem(byte* items, int pos) {
    return (items[pos >> 2]>>((pos & 0b11) << 1)) & 0b11;
    #[pos >> 2] divides pos by 4 as you have 4 positions per byte (so to get the nth position you have to check the n/4th byte)
    #>>((pos & 0b11) << 1) gives you the pos mod 4th entry in the byte
    #&0b11 removes all the remaining other entries from your return value
}

to set the item on a position you'd use
Code: Select all
void setItem(byte* items, int pos, byte item) {
    # set the entry to 0
    items[pos >> 2] &= ~(0b11 << ((pos & 0b11) << 1));
    #assign new value (item has to be < 4)
    items[pos >> 2] |= item << ((pos & 0b11) << 1);
}
User avatar
94k
 
Posts: 44
Joined: Sun Jul 27, 2014 9:41 pm
Location: Germany

Re: array assignment?

Postby rodot » Thu Jul 31, 2014 11:09 am

I wrote a example to explain how to make physics yesterday night, tonight I'll make on to show how to make tiled word (with scrolling camera). I'll commit all that soon. Please be patient :)
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Re: array assignment?

Postby yodasvideoarcade » Thu Jul 31, 2014 7:34 pm

Actually it will be easier: The dots-array can have single bits for each dot. I will check the powerpill-positions seperately.

So I need the following things:

- How to draw only a part of a bitmap?

- How to access (check / change) a single bit of the byte-array?
User avatar
yodasvideoarcade
 
Posts: 102
Joined: Sat Apr 19, 2014 10:48 am
Location: Frankfurt/Germany

Re: array assignment?

Postby 94k » Thu Jul 31, 2014 8:12 pm

- How to draw only a part of a bitmap?

I'm pretty sure rodot will include this in his example, but I'm also pretty sure you can just draw outside the screen and only the parts on the screen will be visible.

- How to access (check / change) a single bit of the byte-array?

You'd have to use bitmagic, storing 8 bit in one byte. then you shift and filter the single bit. For example getting the 3rd bit you'd shift the byte until the 3rd bit is the last one (i.e. by 4 bits) and then cut the rest away like so:
Code: Select all
(value >> 4) & 1;

"& 1" gives you the last bit of a value. For example, if our value is 0b01010011, 0b01010011 >> 4 would result in 0b00000101 (every bit is shifted to the right by 4 positions, the beginning is filled with 0s), 0b00000101 & 1 results in 0b00000001 (everything but the last bit is set to 0).
To initialize your field you'll probably iterate over groups of 8 bits and set them like so:
Code: Select all
for (int i; i < 896 / 8; i++) {
    items[i] = 0;  # init to zero
    items[i] |= progmemItems[i*8]; # first item is written to last position
    items[i] <<= 1 # last position becomes second to last
    items[i] |= progmemItems[i*8 + 1]; # 2nd item is written to last position
    items[i] <<= 1 # last item becomes second to last, second to last becomes third to last
    items[i] |= progmemItems[i*8 + 2]; # 3rd item is written to last position
    ...
    items[i] |= progmemItems[i*8 + 7]; # 8th item is written to last position
}

say progmemItems starts like this:
Code: Select all
{0, 1, 1, 0, 1, 1, 0, 1 ...}

first you'd set items[i] to 0b00000000, then you set the last bit to 0, resulting in 0b00000000, then shift it to the left by one, resulting in 0b00000000, then set the last bit to the second value (1) yielding 0b00000001, then shift left again 0b00000010, set the last value to 1, shift again,
0b00000110 and so on, building your value from right to left. Eventually it will be 0b01101101, representing the first 8 bits of your progmem array.
Note that I don't actually know how to access the array in progmem, you'll probably have to replace progmemItems[i*8] with some function. You should also read up on bitwise operators since the above examples are by no means complete.
User avatar
94k
 
Posts: 44
Joined: Sun Jul 27, 2014 9:41 pm
Location: Germany

Re: array assignment?

Postby rodot » Thu Jul 31, 2014 8:59 pm

Thanks for the explanations 94k, I'm not good at explaining as English is not my mother tongue :P

I'm not a pixel artist neither a skilled programmer, but here is my example:

The world is stored in bi-dimensional array of bytes. Each tile of the world is stored in a byte. A byte is made of 8 bits.
The bits B000000XX define the sprite's ID (so there is 4 different sprites max)
The bits B0000XX00 define the sprite rotation (4 values of rotation)
You can notice that 4 bits are unused for each byte (these one: BXXXX0000).
This means that we could save even more memory by storing 2 tiles per byte, but that would make accessing the the tiles' coordinates more complicated. It will be the subject of another example.

dynamic tile system.jpg
dynamic tile system.jpg (33.38 KiB) Viewed 5315 times


Code: Select all
#include <SPI.h>
#include <Gamebuino.h>
Gamebuino gb = Gamebuino();

#define wrap(i, imax) ((imax+i)%(imax))

//store the different sprites in PROGMEM to save RAM
const byte grass[] PROGMEM = {
  16,16,
  B00010000,B00000000,
  B00101000,B00000010,
  B00010000,B00000000,
  B00000000,B00000000,
  B00000000,B00000000,
  B00010000,B01000000,
  B00000000,B00000000,
  B00000000,B00000000,
  B00000000,B01000000,
  B00000000,B00000000,
  B00000000,B00000000,
  B01000000,B00000000,
  B00000000,B00000000,
  B00000000,B00001000,
  B00000100,B00000000,
  B00000000,B00000000,
};
const byte rocks[] PROGMEM = {
  16,16,
  B00100000,B00000000,
  B01010000,B00000000,
  B00100001,B11100001,
  B00000110,B00011000,
  B00001000,B00001100,
  B00001000,B00000100,
  B00111100,B00000110,
  B01000010,B00000111,
  B01000000,B00110111,
  B01000000,B00011111,
  B00100011,B10011110,
  B00011100,B11111110,
  B00001000,B00111100,
  B00001000,B01111000,
  B00000111,B11100000,
  B00000000,B00000000,
};
const byte road_straight[] PROGMEM = {
  16,16,
  B00011111,B11111000,
  B00011110,B01111000,
  B01011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111001,
  B00011111,B11111000,
  B00011111,B11111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B10011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011111,B11111000,
};
const byte road_turn[] PROGMEM = {
  16,16,
  B00011111,B11111000,
  B00011111,B11111000,
  B00011111,B11111100,
  B00011111,B11111111,
  B00011111,B11111111,
  B00001111,B11111111,
  B00001111,B11111111,
  B00000111,B11111111,
  B10000111,B11111111,
  B00000011,B11111111,
  B00000001,B11111111,
  B00000000,B01111111,
  B00000010,B00011111,
  B00000000,B00000000,
  B00000000,B00000000,
  B01000000,B00000000,
};

// array containing the different sprites
#define NUM_SPRITES 4
const byte* sprites[NUM_SPRITES] = {
  grass, rocks, road_straight, road_turn};

// world array
// Each tile of the world is stored in a byte. A byte is made of 8 bits.
// The bits B000000XX define the sprite's ID
// The bits B0000XX00 define the sprite rotation
// You can notice that 4 bits are unused for each byte.
// This mean that we could save even more memory by storing 2 tiles per byte.
#define WORLD_W 5
#define WORLD_H 3
byte world[WORLD_W][WORLD_H];

byte getSpriteID(byte x, byte y){
  return world[x][y] & B00000011;
}
byte getRotation(byte x, byte y){
  return (world[x][y] >> 2)  & B00000011;
}
void setTile(byte x, byte y, byte spriteID, byte rotation){
  world[x][y] = (rotation << 2) + spriteID;
}

// cursor
char cursor_x, cursor_y;

void setup()
{
  gb.begin();
  initGame();
}

void loop(){
  if(gb.update()){
    //pause the game if C is pressed
    if(gb.buttons.pressed(BTN_C)){
      initGame();
    }
   
    updateCursor();
   
    drawWorld();
    drawCursor();

  }
}

void initGame(){
  gb.titleScreen(F("DYNAMIC TILE MAP DEMO"));
  gb.pickRandomSeed(); //pick a different random seed each time for games to be different
  initWorld();
  gb.popup(F("\25:change \26:rotate"),60);
}

void initWorld(){
  for(byte y = 0; y < WORLD_H; y++){
    for(byte x = 0; x < WORLD_W; x++){
      setTile(x, y, 0, random(0,4)); //fill with grass with random rotation
    }
  }
}

void drawWorld(){
  for(byte y = 0; y < WORLD_H; y++){
    for(byte x = 0; x < WORLD_W; x++){
      byte spriteID = getSpriteID(x,y);
      byte rotation = getRotation(x,y);
      gb.display.drawBitmap(x*16, y*16, sprites[spriteID], rotation, 0);
    }
  }
}

void updateCursor(){
  byte spriteID = getSpriteID(cursor_x,cursor_y);
  byte rotation = getRotation(cursor_x,cursor_y);
  if(gb.buttons.repeat(BTN_A, 4)){
    spriteID = (spriteID+1) % NUM_SPRITES;
  }
  if(gb.buttons.repeat(BTN_B, 4)){
    rotation = (rotation+1) % 4;
  }
  setTile(cursor_x, cursor_y, spriteID, rotation);
 
  if(gb.buttons.repeat(BTN_RIGHT, 4)){
    cursor_x = wrap(cursor_x+1, WORLD_W);
  }
  if(gb.buttons.repeat(BTN_LEFT, 4)){
    cursor_x = wrap(cursor_x-1, WORLD_W);
  }
  if(gb.buttons.repeat(BTN_DOWN, 4)){
    cursor_y = wrap(cursor_y+1, WORLD_H);
  }
  if(gb.buttons.repeat(BTN_UP, 4)){
    cursor_y = wrap(cursor_y-1, WORLD_H);
  }
 
}

void drawCursor(){
  gb.display.drawRect(cursor_x*16,cursor_y*16,16,16);
 
  byte spriteID = getSpriteID(cursor_x, cursor_y);
  gb.display.cursorX = cursor_x*16 + 17;
  gb.display.cursorY = cursor_y*16 + 2;
  gb.display.println(spriteID);
 
  byte rotation = getRotation(cursor_x, cursor_y);
  gb.display.cursorX = cursor_x*16 + 17;
  gb.display.cursorY = cursor_y*16 + 9;
  gb.display.println(rotation);
}


Edit: Here is a new version with a moving camera and a larger world. This way you can see how not to draw the bitmaps which are not on screen.

Code: Select all
#include <SPI.h>
#include <Gamebuino.h>
Gamebuino gb;

#define wrap(i, imax) ((imax+i)%(imax))

//store the different sprites in PROGMEM to save RAM
const byte grass[] PROGMEM = {
  16,16,
  B00010000,B00000000,
  B00101000,B00000010,
  B00010000,B00000000,
  B00000000,B00000000,
  B00000000,B00000000,
  B00010000,B01000000,
  B00000000,B00000000,
  B00000000,B00000000,
  B00000000,B01000000,
  B00000000,B00000000,
  B00000000,B00000000,
  B01000000,B00000000,
  B00000000,B00000000,
  B00000000,B00001000,
  B00000100,B00000000,
  B00000000,B00000000,
};
const byte rocks[] PROGMEM = {
  16,16,
  B00100000,B00000000,
  B01010000,B00000000,
  B00100001,B11100001,
  B00000110,B00011000,
  B00001000,B00001100,
  B00001000,B00000100,
  B00111100,B00000110,
  B01000010,B00000111,
  B01000000,B00110111,
  B01000000,B00011111,
  B00100011,B10011110,
  B00011100,B11111110,
  B00001000,B00111100,
  B00001000,B01111000,
  B00000111,B11100000,
  B00000000,B00000000,
};
const byte road_straight[] PROGMEM = {
  16,16,
  B00011111,B11111000,
  B00011110,B01111000,
  B01011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111001,
  B00011111,B11111000,
  B00011111,B11111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B10011110,B01111000,
  B00011110,B01111000,
  B00011110,B01111000,
  B00011111,B11111000,
};
const byte road_turn[] PROGMEM = {
  16,16,
  B00011111,B11111000,
  B00011111,B11111000,
  B00011111,B11111100,
  B00011111,B11111111,
  B00011111,B11111111,
  B00001111,B11111111,
  B00001111,B11111111,
  B00000111,B11111111,
  B10000111,B11111111,
  B00000011,B11111111,
  B00000001,B11111111,
  B00000000,B01111111,
  B00000010,B00011111,
  B00000000,B00000000,
  B00000000,B00000000,
  B01000000,B00000000,
};

// array containing the different sprites
#define NUM_SPRITES 4
const byte* sprites[NUM_SPRITES] = {
  grass, rocks, road_straight, road_turn};

/*
The world is stored in bi-dimensional array of bytes.
Each tile of the world is stored in a byte. A byte is made of 8 bits.
The bits B000000XX define the sprite's ID (so there is 4 different sprites max)
The bits B0000XX00 define the sprite rotation (4 values of rotation)
You can notice that 4 bits are unused for each byte (these one: BXXXX0000).
This means that we could save even more memory by storing 2 tiles per byte,
but that would make accessing the the tiles coordinates more complicated.
It will be the subject of another example.
*/
#define WORLD_W 16
#define WORLD_H 8
byte world[WORLD_W][WORLD_H];

byte getSpriteID(byte x, byte y){
  return world[x][y] & B00000011;
}
byte getRotation(byte x, byte y){
  return (world[x][y] >> 2)  & B00000011;
}
void setTile(byte x, byte y, byte spriteID, byte rotation){
  world[x][y] = (rotation << 2) + spriteID;
}

// cursor
int cursor_x, cursor_y;
int camera_x, camera_y;

void setup()
{
  gb.begin();
  initGame();
}

void loop(){
  if(gb.update()){
    //pause the game if C is pressed
    if(gb.buttons.pressed(BTN_C)){
      initGame();
    }
   
    updateCursor();
   
    drawWorld();
    drawCursor();

  }
}

void initGame(){
  gb.titleScreen(F("DYNAMIC TILE MAP DEMO"));
  gb.pickRandomSeed(); //pick a different random seed each time for games to be different
  initWorld();
  gb.popup(F("\25:change \26:rotate"),60);
}

void initWorld(){
  for(byte y = 0; y < WORLD_H; y++){
    for(byte x = 0; x < WORLD_W; x++){
      setTile(x, y, 0, random(0,4)); //fill with grass with random rotation
    }
  }
}

void drawWorld(){
  for(byte y = 0; y < WORLD_H; y++){
    for(byte x = 0; x < WORLD_W; x++){
      byte spriteID = getSpriteID(x,y);
      byte rotation = getRotation(x,y);
      //coordinates on the screen depending on the camera position
      int x_screen = x*16 - camera_x;
      int y_screen = y*16 - camera_y;
      if(x_screen < -16 || x_screen > LCDWIDTH || y_screen < -16 || y_screen > LCDHEIGHT){
        continue; // don't draw sprites which are out of the screen
      }
      gb.display.drawBitmap(x_screen, y_screen, sprites[spriteID], rotation, 0);
    }
  }
}

void updateCursor(){
  byte spriteID = getSpriteID(cursor_x,cursor_y);
  byte rotation = getRotation(cursor_x,cursor_y);
  if(gb.buttons.repeat(BTN_A, 4)){
    spriteID = (spriteID+1) % NUM_SPRITES;
    gb.sound.playOK();
  }
  if(gb.buttons.repeat(BTN_B, 4)){
    rotation = (rotation+1) % 4;
    gb.sound.playOK();
  }
  setTile(cursor_x, cursor_y, spriteID, rotation);
 
  if(gb.buttons.repeat(BTN_RIGHT, 4)){
    cursor_x = wrap(cursor_x+1, WORLD_W);
    gb.sound.playTick();
  }
  if(gb.buttons.repeat(BTN_LEFT, 4)){
    cursor_x = wrap(cursor_x-1, WORLD_W);
    gb.sound.playTick();
  }
  if(gb.buttons.repeat(BTN_DOWN, 4)){
    cursor_y = wrap(cursor_y+1, WORLD_H);
    gb.sound.playTick();
  }
  if(gb.buttons.repeat(BTN_UP, 4)){
    cursor_y = wrap(cursor_y-1, WORLD_H);
    gb.sound.playTick();
  }
 
  //target position of the camera for the cursor to be centered
  int camera_x_target = cursor_x*16 - LCDWIDTH/2 + 8;
  int camera_y_target = cursor_y*16 - LCDHEIGHT/2 + 8;
  //apply the target coordinate to the current coordinates with some smoothing
  camera_x = (camera_x*3 + camera_x_target)/4;
  camera_y = (camera_y*3 + camera_y_target)/4;
 
}

void drawCursor(){
  int x_screen = cursor_x*16 - camera_x;
  int y_screen = cursor_y*16 - camera_y;
  if(!(x_screen < -16 || x_screen > LCDWIDTH || y_screen < -16 || y_screen > LCDHEIGHT)){
    gb.display.drawRect(x_screen, y_screen, 16, 16);
  }
 
  gb.display.print(F("X"));
  gb.display.print(cursor_x);
  gb.display.print(F(" Y"));
  gb.display.print(cursor_y);
 
  byte spriteID = getSpriteID(cursor_x, cursor_y);
  gb.display.print(F(" I"));
  gb.display.print(spriteID);
  byte rotation = getRotation(cursor_x, cursor_y);
  gb.display.print(F(" R"));
  gb.display.print(rotation);
}


PS: you might want to rename this topic to something like "dynamic tile map" ?
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Re: array assignment?

Postby yodasvideoarcade » Fri Aug 01, 2014 11:57 am

I solved it this way:

One image in PROGMEM for the visible screen-maze.
One array of bytes for the dots and one array of bytes for the walls.
In the arrays, each bit represents one tile, since it's only dot/no dot/rodot (joke!) and wall/no wall in the other array.
There I need only 132 bytes for the dot-array and 132 bytes for the wall-array.
User avatar
yodasvideoarcade
 
Posts: 102
Joined: Sat Apr 19, 2014 10:48 am
Location: Frankfurt/Germany

Previous

Return to Programming Questions

Who is online

Users browsing this forum: No registered users and 3 guests

cron