Thread: A snake game - Memory problem

I wrote another snake game [this time an efficient one (I think)] and I was wandering how much RAM my game use so I checked at the task manager and it starts at something like 1,200 and don't stop to increase (no matter if I allocate memory for the array) [and every time I played the game it stopped at the same size of the snake (64)].
I don't know much about memory so don't use complicated terms please (;

Guess you'll need to see the code, so:

Code:

#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#include <User/Console.h>

#define UP 72
#define LEFT 75
#define RIGHT 77
#define DOWN 80
#define ESC 27

typedef struct
{
        int x;
        int y;
        int exist;
}INFO;

typedef struct
{
        int x;
        int y;
}LOC;

void Clear(LOC* snake)
{
     free(snake);
}

void Initialize(LOC snake[], int* size, INFO* food, int* direction)
{
     int i;
     srand((unsigned)time(NULL));
     ResizeConsoleWindow(50,30);
     ChangeConsoleTitle("Snake");
     HideConsoleCursor();
     *size = 3;
     *direction = LEFT;
     for (i=0;i<*size;i++)
     {
         snake[i].x = 40 + i;
         snake[i].y = 10;
     }
     food->exist = 0;
}

void Input(int *input, LOC* snake)
{
     int temp = *input;
     if (kbhit())
        *input = getch();
     if (*input == 224)
     {
        *input = getch();
        switch(*input)
        {
                      case UP: if (temp == DOWN) *input = temp;
                           break;
                      case DOWN: if (temp == UP) *input = temp;
                           break;
                      case LEFT: if (temp == RIGHT) *input = temp;
                           break;
                      case RIGHT: if (temp == LEFT) *input = temp;
                           break;
        }
     }
     else if (*input == ESC)
          {
             Clear(snake);
             exit(0);
          }
     else *input = temp;
}

void Allocate(LOC* snake, int size)
{
     snake = malloc(sizeof(LOC)*size);
     if(snake == NULL)
     {
              printf("Allocating Error");
              getch();
              exit(1);
     }
}

void Move(LOC snake[], int *size, int direction, INFO* food)
{
     int i;
     if ( (snake[0].x == food->x && snake[0].y == food->y) )
     {
         Allocate(snake,++(*size));
         snake[*size-1].x = snake[*size-2].x;
         snake[*size-1].y = snake[*size-2].y;
         FilledCircle(food->x*8,food->y*12.33,4,BLACKRGB);
         food->exist = 0;
     }
     if(food->exist)
        FilledCircle(food->x*8,food->y*12.33,4,REDRGB);
     Circle(snake[*size-1].x*8,snake[*size-1].y*12.33,5,BLACKRGB);
     for (i=*size-1;i>0;i--)
     {
         snake[i].x = snake[i-1].x;
         snake[i].y = snake[i-1].y;
     }
     Circle(snake[0].x*8,snake[0].y*12.33,5,YELLOWRGB);
     switch (direction)
     {
            case UP: snake[0].y--;
                 break;
            case DOWN: snake[0].y++;
                 break;
            case LEFT: snake[0].x--;
                 break;
            case RIGHT: snake[0].x++;
                 break;
     }
     Circle(snake[0].x*8,snake[0].y*12.33,5,GREENRGB);
}

void CreateFood(LOC snake[], int size, INFO* food)
{
     int x, y, i;
     RANDOM:
     x = rand()%49+1; y = rand()%29+1;
     for (i=0;i<size;i++)
         if (snake[i].x == x && snake[i].y == y)
            goto RANDOM;
     food->x = x;
     food->y = y;
     food->exist = 1;
     FilledCircle(food->x*8,food->y*12.33,4,REDRGB);
}

int Crash(LOC snake[], int size)
{
    int i;
    for (i=1;i<size;i++)
        if (snake[0].x == snake[i].x && snake[0].y == snake[i].y)
           return 1;
    if (snake[0].x == 0 || snake[0].y == 0 || snake[0].x == 51 || snake[0].y == 31)
       return 1;
    return 0;
}

void End(LOC* snake, int size)
{
     Clear(snake);
     ClearConsole();
     gotoxy(10,10);
     SetAttColor(LIGHTBLUE);
     printf("Final Lenght: %d", size);
     getch();
}

int main()
{
    int size, direction;
    LOC *snake = malloc(sizeof(LOC)*3);
    INFO food;
    Initialize(snake, &size, &food, &direction);
    while(!Crash(snake, size))
    {
           Input (&direction, snake);
           if (!food.exist)
              CreateFood(snake, size, &food);
           Move(snake, &size, direction, &food);
           Sleep(((70-(size/3))>0)*(70-(size/3)));
    }
    End(snake, size);
    return 0;
}

If you want to see it (Win only):
http://www.2shared.com/file/4313871/40b3182d/Project1.html

Thanks (:

A good improvement on the old one - only one goto (but you don't need that one either - a regular while-loop will be perfectly fine (and shorter to write, as goto random is longer than a while). You may need a continue or use of an extra variable to track if the choice is OK, but there's absolutely no need to use goto here.

Your function called Allocate doesn't work right - it allocates a new bit of memory, but since it assigns it to the parameter without actually modifying the variable on the outside of the function, it will just crash eventually when you go over the end of the buffer. Either return the new value, or pass pointer to pointer.

And of course, whenever you extend the snake, you need to:
1. copy the old snake contents.
2. free the old snake memory.

You only free the snake when the game ends (from looking at it briefly).

--
Mats

Thanks and leave that goto behind for now (I am an addict.. \=).
Which choice are you talking about?

I don't understand my mistake, can you fix it for me? (please? (: )

It's like in C# that when you allocates memory you need to copy the old values? \:
Why should I free the snake memory? @_@

Yes.. that's what I thought I should do..

Thanks again.. (=

There's a much more efficient way to code a snake game.
You have a grid of structs that look somewhat like this:

Code:

struct {
    enum CellContents {
        EMPTY,
        SNAKE,
        FOOD,
        WALL, // etc
    } contents;
    enum NextSnakePiece {
        NONE, // I.e. this is the head
        UP,
        LEFT,
        DOWN,
        RIGHT,
    } nextPiece;
};

You also need to track just the snake's head and tail...

Code:

int headX, headY, tailX, tailY;

When you want to move the snake along then you go straight to the tail spot on the grid and the nextPiece enum of that cell tells you where the next piece of the snake is. You adjust your tail location accordingly and erase the old tail piece.
For moving the head you first test the cell in the direction you are moving, and then set the nextPiece value of cell the that currently holds the head to point towards the new head piece, and then add the head piece into the grid and adjust the head location.
Essentially the board itself has linked-list information embedded within it, making it possible to travel form the tail to the head if you needed to, though you're really only interested in updating things at the head and the tail. It all makes it really easy to only update the bits of screen that need updating.
When you're extending the snake, you simply skip adjusting the tail for a few iterations.
You'll barely have any loops at all doing it this way. Perhaps just one loop for trying spots to place food that aren't on the snake, other than your main loop of course.
You don't need any dynamic memory allocation at all and you can easily create multiple food spots if you want too. The easiest way to not leak is to not allocate.

Also, get rid of those magic numbers. To change the width of your game you should only have to change one constant.

And how does everything you said is connected with my problem? XD
I didn't understand your way for creating this game but if when you said: "There's a much more efficient way to code a snake game" you realated for run time then I think my last snake game was very efficient at this point (cuz when I said "efficient" I refered to the memory) or maybe you meant both run time and memory? .
Thanks anyway dude (=

Mats where are you? \=

Originally Posted by gavra

And how does everything you said is connected with my problem? XD

Uh, your problem is a memory leak. I described one way to write the program that doesn't just not leak, it completely avoids the possibility of leaking because it does no dynamic allocations.

I didn't understand your way for creating this game but if when you said: "There's a much more efficient way to code a snake game" you realated for run time then I think my last snake game was very efficient at this point (cuz when I said "efficient" I refered to the memory) or maybe you meant both run time and memory?

Fair enough, if you don't understand then I can try explaining it in a different way, or perhaps explain it with a diagram.
Yes I meant more efficient in terms or run-time, and also in terms of memory usage once you take into account a snake that has gotten rather long, and the possible memory fragmentation caused in the process, and dynamic memory allocation overhead.
I've simplified it furthur by replacing the two enums with only one. Memory usage is therefore board_height * board_width bytes, as each cell is can be one bytes.
Here's a sample board. Key:
<space> = Empty, F = Food, W = Wall, H = Head, U = UP, L = Left, D = Down, R = Right

Code:

WWWWWWWWWWWWWWWW
W              W
W  RRRH    F   W
W  U           W
W  U  DLLL     W
W  ULLL  U     W
W        U     W
W      RRU     W
W              W
WWWWWWWWWWWWWWWW

The H is the head of the snake at (6, 2) from the top-left corner. The R at (7, 7) is the tail. To move the head down say, you replace the H with a D, and place an H below that D, changing the head coordinates to the position of the new H which is (6, 3). To move the tail you remove the R at (7, 7) and change the tail coordinates to (8, 7). The letter you erase tells you which direction to follow the tail in.
Does this at least make sense now?
You're totally free to implement it how you've chosen of course and I'll do what I can to help.
The following changes to the function prototypes may hint at what you need to do:

Code:

LOC *Allocate(LOC* snake, int size)
LOC *Move(LOC *snake, int *size, int direction, INFO* food)

Now, think about what you will return, and what this return value will be assigned to.

If you use a board of the game then it's the same idea as my last snake game (I leave behind "footprints" [UP\DOWN\LEFT\RIGHT] so I'll be able to follow the body and moving the snake won't be depend in the lenght of the snake).

I thought malloc is being converted for the right type but I think it depends in which compiler you are using.

I still don't understand what is wrong so the using of RAM is increasing \=

Thanks (:

Originally Posted by gavra

I was wandering how much RAM my game use so I checked at the task manager and it starts at something like 1,200 and don't stop to increase

Well, since void Allocate (b/t/w why don't you use realloc instead of malloc there?) dynamically allocates more memory for the snake depending on events, of course memory use increases.

Originally Posted by gavra

I still don't understand what is wrong so the using of RAM is increasing

Okay I'll be explicit here and tell you exactly what the problem is:
One problem is here:

Code:

void Allocate(LOC* snake, int size)
{
     snake = malloc(sizeof(LOC)*size);
     if(snake == NULL)
     {
              printf("Allocating Error");
              getch();
              exit(1);
     }
}

The allocated memory here is leaked because once the function exits there are no pointers holding the memory address that was returned by malloc. The variable that you passed into this function is passed by value. Think about what happens here:

Code:

void demo(int foo)
{
    foo = 2;
}

int main()
{
    int bar = 1;
    demo(bar);
    // What is the value of bar here?
}

The answer of course is that bar is still 1. Why? Well what would you expect to happen if you did this?:

Code:

demo(3);

Does 3 suddenly become 2? No of course not! You can't modify what you pass in. The same deal goes for pointers and everything else in C.
If you want to modify what you pass in, then you either have to pass in a pointer to it, or you have to pass out the new value. E.g.

Code:

int demo(int foo)
{
    foo = 2;
    return foo;
}

int main()
{
    int bar = 1;
    bar = demo(bar);
    // What is the value of bar here?
}

Now bar = 2!
That means if you want to modify your pointer you have to also either return it, OR you need to pass in a POINTER TO A POINTER! That's LOC **snake for you. That isn't as nice a way though when coding in pure C, so it's best to return the new pointer value.

Next, think about how many times you call malloc vs how many times you call free. You call malloc through Allocate through Move every time in the loop. However you only call free through Clear at the end of when you press escape. You do know that you have to call free for EVERY address you get back form malloc right? (excluding memory allocation failure)

If this is all sounding too hard, then try the easy way I suggested where you use a board.

First of all thanks.

citizen
But I allocates memory only if I need to grow up (means ate some food)..

iMalc
I know what simple pointers means V_V
Anyway, I am starting to have an understanding with the malloc function.
If I use realloc I won't be asked to free and copy right?
As I said I have already make this game with a board:
http://cboard.cprogramming.com/showt...ighlight=snake

I used realloc instead:

Code:

void Allocate(LOC* snake, int size)
{
     realloc(snake,sizeof(LOC)*size);
     if(snake == NULL)
     {
              printf("Allocating Error");
              Clear(snake);
              getch();
              exit(1);
     }
}

but still the same problem..
Do I still need to pass "snake" as pointer to pointer?

Originally Posted by gavra

First of all thanks.

citizen
But I allocates memory only if I need to grow up (means ate some food)..

iMalc
I know what simple pointers means V_V
Anyway, I am starting to have an understanding with the malloc function.
If I use realoc I won't be asked to free and copy right?
As I said I have already make this game with a board:
http://cboard.cprogramming.com/showt...ighlight=snake

Yes, but like iMalc explains, you are not ACTUALLY using the new memory you allocated for the growing snake, but rather you are allocating a new block of memory, and immediately as you leave that function, loose the address that it points to, and you are still using your old memory that you allocated originally.

You also do not free the old memory after you have allocated new memory (which is the real reason your memory is growing - every time your snake eats something, you allocates more memory, but you don't free the OLD memory).

realloc basically does this (although it is a bit smarter than this code):

Code:

void *realloc(void *ptr, size_t newsize)
{
    // get_size is an internal function that knows how malloc/free works internally and
    // can find the size of the memory block as it was allocated. 
    size_t oldsize = get_size(ptr);   
    if (newsize == 0)
    {
        free(ptr);
        return 0;
    }
    // In the real realloc, it also checks if the old size is bigger than new size,
    // or if the block can just expand without a new allocation being created
    // (that is, there is space behind the current one that is not taken)
    if (newsize != oldsize)
    {
        void *tmp = malloc(newsize);
        if (!tmp)
            return NULL;
        // Copy data to the new pointer. 
        memcpy(tmp, ptr, oldsize);
        return tmp;
    }
    // Nothing needed, as we are not growing. 
    return ptr;
}

--
Mats

You don't know how long I have been waiting for your post (:
Well, so why is it still increasing? (I am using realloc..) /=

Originally Posted by gavra

You don't know how long I have been waiting for your post (:
Well, so why is it still increasing? (I am using realloc..) /=

If you post the current version of Allocate and it's call, I could tell. My mindreading isn't working well today - have a bit of a headache and cold, maybe that's why...

--
Mats

I have already post it.

Code:

void Allocate(LOC* snake, int size)
{
     realloc(snake,sizeof(LOC)*size);
     if(snake == NULL)
     {
              printf("Allocating Error");
              Clear(snake);
              getch();
              exit(1);
     }
}

Code:

void MoveAndDraw(LOC snake[], int *size, int direction, INFO* food)
Allocate(snake,++(*size));

Ohh are you sick? \=