A snake game - Memory problem

This is a discussion on A snake game - Memory problem within the C Programming forums, part of the General Programming Boards category; I wrote another snake game [this time an efficient one (I think)] and I was wandering how much RAM my ...

  1. #1
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    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 (:
    Last edited by gavra; 11-20-2008 at 12:07 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    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.. (=
    Last edited by gavra; 11-20-2008 at 12:09 AM.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    Last edited by iMalc; 11-20-2008 at 01:24 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    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? \=
    gavra.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by gavra View Post
    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.
    Last edited by iMalc; 11-21-2008 at 12:54 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    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 (:
    gavra.

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,751
    >> I thought malloc is being converted for the right type but I think it depends in which compiler you are using. <<

    It shouldn't depend on that unless you are using a compiler that predates when C was standardized. You are correct that malloc's return type (void *) is convertable to other pointer types. In particular you shouldn't need to cast for the result, if you've added the appropriate header, #include <stdlib.h>

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

    I think the idea is to just allocate the the whole board *once*. Try looking at his diagram again.

    In particular I notice:

    While still playing:
    1. User chooses direction
    2. Snake moves until:
    2a. He bites himself, game over.
    2b. runs into a wall, game over.
    3. If snake eats food, his tail grows by one column.

    So maneuvering the snake means moving the head in one direction and then gradually following with the rest of the body (depending on the acceleration at that level). If you have to allocate something to perform this logic, you need to start over, because the board has a finite number of states and is finite in size. Managing the state of the board should not involve memory allocation / deallocation in a significant way.

    But this is just my two cents. Even if you had a small grid of characters, managing the states simply means assigning new key values (like 'F', 'R', 'U', and 'D') over time.

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by gavra View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by gavra View Post
    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.
    Last edited by iMalc; 11-21-2008 at 03:00 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    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:
    Can you spot debug? [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?
    Last edited by gavra; 11-21-2008 at 05:08 AM.
    gavra.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by gavra View Post
    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:
    Can you spot debug? [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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    You don't know how long I have been waiting for your post (:
    Well, so why is it still increasing? (I am using realloc..) /=
    gavra.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by gavra View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    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? \=
    gavra.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with game code.
    By ajdspud in forum C++ Programming
    Replies: 5
    Last Post: 02-14-2006, 06:39 PM
  2. problem with my opegl game...
    By revelation437 in forum Game Programming
    Replies: 6
    Last Post: 11-25-2004, 11:32 AM
  3. Pointer's
    By xlordt in forum C Programming
    Replies: 13
    Last Post: 10-14-2003, 03:15 PM
  4. Manipulating the Windows Clipboard
    By Johno in forum Windows Programming
    Replies: 2
    Last Post: 10-01-2002, 10:37 AM
  5. allegro game problem
    By pode in forum Game Programming
    Replies: 12
    Last Post: 04-20-2002, 04:26 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21