Go Down

Topic: Not enough RAM? (Read 4388 times) previous topic - next topic

Chicken325

I want to make a Snake game on my Arduino.  However I have a little problem.  My Nokia screen already consumes half my RAM, so I only have 1/2 a KB left.  I store each square on the field as a number.  if it's 0, it's empty.  If it's -1, it's food.  If it's greater than 0, then the number is how many game ticks before that square becomes empty again.  Since the space for the game itself on the screen is 82x46, and each int is 2KB, that means that not even including the bytes of the array itself, just its contents, the size of the information to store the state of the game field is more than 7KB.  My Arduino can't do that! :P

Is there a better way of storing the game field?

nickgammon


and each int is 2KB


2000 bytes per int? You mean 2 bytes.

You could make them char rather than int. That gives you one byte each, and goes from -128 to +127. That's still 3772 bytes. Which Arduino is it? Some have 2 Kb of RAM, not 1 Kb.

I don't see how you are going to fit 3772 squares into 512 bytes of RAM, unless you make the game field a bit smaller. Like, use 4 pixels for each square rather than one, then you only need 943 bytes. It's getting closer to what you have available.

One option could be to get an I2C or SPI external SRAM chip to your processor.

I describe a way of doing that here:

http://www.gammon.com.au/forum/?id=10979

The chip costs around $1.70 and gives you 32 Kb of RAM, which should be enough for your game.
Please post technical questions on the forum, not by personal message. Thanks!

More info: http://www.gammon.com.au/electronics

wildbill

How much of the field is empty? If the data is sparse, you can do something like storing only the cells that have something in them by storing <row><col><content> as three bytes. Means that the algorithms for using the data are more complex and slower though. It's possible to be more devious still and use an indicator byte to tell you when row changes & drop that for most cells, accepting more complexity.

PaulS

You could also use 2 arrays - one for food and one for time. The food array can be very small, since it will only contain 0 or 1, so you can pack 8 squares of data into a single byte. This requires some effort to look up a value, but that gets put in a function, so you can simply call food(row, col) and get back true or false. If it's not food, it might be empty or it might be snake, depending on the value in the other array (0 or non-zero.
The art of getting good answers lies in asking good questions.

Magician

Why spend 1 or 2 bytes, just to store "0" or "1"?
Use bit wise operation, gives 8 times improvement, as each byte will keep info for 8 game fields.

S1 = 82 x 46 = 3772

Vertical size V = 46 / 8 = 6 bytes,  

S2 = 82 x 6 = 492   and S1 / S2 = 7.66, that is not exactly 8, due vertical size not exactly multiplier of 8.
I create a project base on this approach, have a look:
http://arduino.cc/forum/index.php/topic,63186.msg458799.html#msg458799
There is no comments in code,   :smiley-red: , but look for
unsigned int karta[INBUF] in function print_chart - is two dimensional array, an image map,
size [16] x [INBUF].





Chicken325

I'm not storing just 0 or one.  Here's how my program would parse the array: (Revised from OP)

-2:  It's the head.
-1: It's food.
0:  It's nothing.
> 0:  It's part of the snake, whatever number it is is how many game ticks it has left before it's 0 again.  The exact tail square of the snake would have the number 1, then the square before that 2, then 3, etc. until you get to the head.  This type of square is decremented every game tick.

Magician

O'k, I didn't play this game for a while...  And I find it an good brain exercise for weekend   ;)
Yeh, not much could be optimized w/o changing the logic, I just have an idea:

- in the beginning create "image-map" of the food, 1 - food, 0 - nothing.(492 bytes).

- as snake couldn't be too long, put it on a "running track" - small array
  size = maximum length of snake (what is it 8 or 16). Each elements of it holds XY coordinate of
the snake body pixel. One byte is enough for it, two make programming easier.
So it will require 16 integers, high byte X, low byte Y. ( 32 bytes ).

- transfer foods image map to output buffer image the same size, add to output
  image of the snake. (492 bytes).

Now on "click", move a "running track" like a conveyor belt / logical shift operation.

- copy each element to left/right, if elements last in the chain it will be lost.

- you know where snake moving on next step, look in food map check is there is "1",
   add up XY coordinate on top of the snake body, clear food map to "0".

- refresh image.

For more size reduction, I'd consider foods image-map create in the same way as a
snake's image, and it even doesn't have to move.

CrossRoads

Sorry, jumping in late here

-2:  It's the head.
-1: It's food.
0:  It's nothing.
> 0:
Seems like this approach wastes lot - if its a byte, you are wasting all the data from -127 to -3, using only -2, -1, 0 to 127.

Worse if its an int; -32767 to -3, then using -2, -1, 0 to 32768 (or whatever the split is between 2^16-1, you get the idea)

I'd go with unsigned bytes, use the full 0 to 255 range.
Designing & building electrical circuits for over 25 years.  Screw Shield for Mega/Due/Uno,  Bobuino with ATMega1284P, & other '328P & '1284P creations & offerings at  my website.

Chicken325

#8
Jun 12, 2011, 07:53 pm Last Edit: Jun 12, 2011, 08:15 pm by Chicken325 Reason: 1
Problem is, that would only allow my snake to be up to 253 squares long, including the head.  I suppose I could just ignore that and just make you go faster after that to keep making it harder.

However...  :P

Even if I use a byte instead of an int, instead of being 7.5KB of RAM needed, it's 3.75KB.  Still too much!  What I need is a better system...  I can't think of anything.

EDIT: Being a genius, I missed a post.

O'k, I didn't play this game for a while...  And I find it an good brain exercise for weekend   ;)
Yeh, not much could be optimized w/o changing the logic, I just have an idea:

- in the beginning create "image-map" of the food, 1 - food, 0 - nothing.(492 bytes).

- as snake couldn't be too long, put it on a "running track" - small array
  size = maximum length of snake (what is it 8 or 16). Each elements of it holds XY coordinate of
the snake body pixel. One byte is enough for it, two make programming easier.
So it will require 16 integers, high byte X, low byte Y. ( 32 bytes ).

- transfer foods image map to output buffer image the same size, add to output
  image of the snake. (492 bytes).

Now on "click", move a "running track" like a conveyor belt / logical shift operation.

- copy each element to left/right, if elements last in the chain it will be lost.

- you know where snake moving on next step, look in food map check is there is "1",
   add up XY coordinate on top of the snake body, clear food map to "0".

- refresh image.

For more size reduction, I'd consider foods image-map create in the same way as a
snake's image, and it even doesn't have to move.



That's smart!  But I just realized that since there's always just one piece of food on the map, instead of making an "image map" which I don't know how to do, I can just store the coordinates in 2 bytes.

But you were saying you could store both coordinates in one byte, it's just harder.  How do I do that?  The game field is 84x48.

BTW, why do booleans always suck up an entire byte?  It makes no sense...  Why does everything have to be in blocks of 8?  Couldn't the ATMEGA store 8 booleans per byte rather than using 8 bytes for 8 booleans?

Magician

Agree. And there is a leak I discovered in my own idea:
Quote
- you know where snake moving on next step, look in food map check is there is "1",
   add up XY coordinate on top of the snake body, clear food map to "0".

Snake isn't moving, it just dying of starvation  :~
Here each cell in the array has to be updated on +1 or -1 for X (left-right) OR Y(up-down)
movement, may be more than +-1 (increase speed).
But what bugging me, that this beach isn't linear, it has a "corners" on its body, every turn
snake made in the past create one of them, and corners have to be unmovable.
So we cann't just update every elements on running track with new coordinate, but only
elements of the same piece lining on straight line. 
It become too complicated, w/o step by step real coding in IDE I'm loosing a traction...

Chicken325

Well I'll try to do it using the coordinate method of storing the snake.

nickgammon


BTW, why do booleans always suck up an entire byte?  It makes no sense...  Why does everything have to be in blocks of 8? 


They don't have to - with programming you can store one per bit (8 per byte). However the hardware *addresses* in blocks of 8. So if you are storing ints it takes 2 addresses to hold one of them, and longs takes 4 addresses.

Quote
But you were saying you could store both coordinates in one byte, it's just harder.  How do I do that?  The game field is 84x48.


I don't think he is correct. 84x48 is 4032 positions. You won't store that in a byte.

However to try to squeeze it in we need more info. How long can the snake get? How much food can a segment eat?

Let's say you reduced the playing field to 64x32. That's 6 bits for the X coordinate (2^6 = 64)  and 5 bits for the Y coordinate  (2^5 = 32). Out of 2 bytes (16 bits) that gives 11 bits, leaving 5 over. So we could record up to 32 for food. Now with 2 bytes per segment you could fit 256 segments into 512 bytes, giving a 256-segment long snake.
Please post technical questions on the forum, not by personal message. Thanks!

More info: http://www.gammon.com.au/electronics

bubulindo


That's smart!  But I just realized that since there's always just one piece of food on the map, instead of making an "image map" which I don't know how to do, I can just store the coordinates in 2 bytes.

But you were saying you could store both coordinates in one byte, it's just harder.  How do I do that?  The game field is 84x48.

BTW, why do booleans always suck up an entire byte?  It makes no sense...  Why does everything have to be in blocks of 8?  Couldn't the ATMEGA store 8 booleans per byte rather than using 8 bytes for 8 booleans?


Why not randomize where the next food will show up instead of having it predetermined? I thought that's how it normally works. :\



This... is a hobby.

Magician

Code: [Select]
But you were saying you could store both coordinates in one byte,
My mistake, the best "packing" would need 13 bit anyway, doesn't worth it.

Chicken325



That's smart!  But I just realized that since there's always just one piece of food on the map, instead of making an "image map" which I don't know how to do, I can just store the coordinates in 2 bytes.

But you were saying you could store both coordinates in one byte, it's just harder.  How do I do that?  The game field is 84x48.

BTW, why do booleans always suck up an entire byte?  It makes no sense...  Why does everything have to be in blocks of 8?  Couldn't the ATMEGA store 8 booleans per byte rather than using 8 bytes for 8 booleans?


Why not randomize where the next food will show up instead of having it predetermined? I thought that's how it normally works. :\

I am.  To remember where the food currently is, it stores the coordinates of the food.  When the food is eaten, it randomizes those coordinates to a new location.

Go Up