12
\$\begingroup\$

My programming background is mostly C++/C#. Lately i got interested in writing some C. So i implemented Conway's Game of Life using SDL2 for visualization. This is actually my first program written in C. Since im quite comfortable in writing C++ it's probably not completely awful.

I would like to get some review/feedback/suggestions for improvements about my code.

Upon start you can set up the starting pattern (left-click = alive, right-click = dead) and pressing the Enter key starts the simulation. Here is the code:

#define SDL_MAIN_HANDLED
#include <SDL.h>

#include <time.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

enum State
{
    INIT,
    RUNNING,
    EXIT
};

struct Cell
{
    bool alive;
    bool next;
};

static const int32_t field_size = 200; // the amount of cells in both dimensions
static const int32_t pixels_per_cell = 6; // size of a displayed cell in pixels
static const Uint32 tickrate = 200; // update frequency in ms

static SDL_Window* window = NULL;
static SDL_Renderer* renderer = NULL;
static struct Cell** cells = NULL;
static enum State state = INIT;

static bool initialize(void)
{
    if(SDL_Init(SDL_INIT_VIDEO) != 0)
    {
        return false;
    }

    int32_t window_size = field_size * pixels_per_cell;

    window = SDL_CreateWindow("Conway's Game of Life", 50, 50, window_size, window_size, SDL_WINDOW_OPENGL);
    renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);

    SDL_ShowWindow(window);

    cells = calloc(field_size, sizeof(struct Cell*));

    for(int32_t i = 0; i < field_size; i++)
    {
        cells[i] = calloc(field_size, sizeof(struct Cell));
    }

    return true;
}

static void cleanup(void)
{
    for(int32_t i = 0; i < field_size; i++)
    {
        free(cells[i]);
    }

    free(cells);

    SDL_DestroyRenderer(renderer);
    SDL_DestroyWindow(window);

    SDL_Quit();
}

static void set_field_from_mousepos(const Sint32 mouse_x, const Sint32 mouse_y, const bool value)
{
    uint32_t x = mouse_x / pixels_per_cell;
    uint32_t y = mouse_y / pixels_per_cell;

    cells[x][y].alive = value;
}

static void on_mouse_down(const SDL_MouseButtonEvent* const event)
{
    if(state == INIT) 
    {
        switch(event->button)
        {
            case SDL_BUTTON_LEFT:
                set_field_from_mousepos(event->x, event->y, true);
                break;

            case SDL_BUTTON_RIGHT:
                set_field_from_mousepos(event->x, event->y, false);
                break;
        }
    }
}

static void on_key_down(const SDL_KeyCode key)
{
    switch(key)
    {
        case SDLK_RETURN:
            state = RUNNING;
            break;
    }
}

static void process_messages()
{
    SDL_Event event;

    while(SDL_PollEvent(&event))
    {
        switch(event.type)
        {
            case SDL_QUIT:
                state = EXIT;
                break;

            case SDL_MOUSEBUTTONDOWN:
                on_mouse_down(&event.button);
                break;

            case SDL_KEYDOWN:
                on_key_down(event.key.keysym.sym);
                break;
        }
    }
}

static int32_t count_neighbours(const int32_t cell_x, const int32_t cell_y)
{
    int32_t count = 0;

    for(int32_t x = max(cell_x - 1, 0); x <= min(cell_x + 1, field_size - 1); x++)
    {
        for(int32_t y = max(cell_y - 1, 0); y <= min(cell_y + 1, field_size - 1); y++)
        {
            if(!(x == cell_x && y == cell_y) && cells[x][y].alive) // don't count the cell itself
            {
                count++;
            }
        }
    }

    return count;
}

static void update_game(void)
{
    // calculate next state for the cells
    for(int32_t x = 0; x < field_size; x++)
    {
        for(int32_t y = 0; y < field_size; y++)
        {
            int32_t count = count_neighbours(x, y);

            if(!cells[x][y].alive && count == 3) // rule 1
            {
                cells[x][y].next = true;
            }

            if(cells[x][y].alive && (count < 2 || count > 3)) // rule 2 & 4
            {
                cells[x][y].next = false;
            }

            if(cells[x][y].alive && (count == 2 || count == 3)) // rule 3
            {
                cells[x][y].next = true;
            }
        }
    }

    // set alive states for drawing and reset next
    for(int32_t x = 0; x < field_size; x++)
    {
        for(int32_t y = 0; y < field_size; y++)
        {
            cells[x][y].alive = cells[x][y].next;
            cells[x][y].next = false;
        }
    }
}

static void render_frame()
{
    SDL_SetRenderDrawColor(renderer, 50, 50, 50, SDL_ALPHA_OPAQUE);
    SDL_RenderClear(renderer);

    SDL_SetRenderDrawColor(renderer, 255, 255, 255, SDL_ALPHA_OPAQUE);

    // draw a white rectangle for each living cell
    for(int32_t x = 0; x < field_size; x++)
    {
        for(int32_t y = 0; y < field_size; y++)
        {
            if (cells[x][y].alive)
            {
                SDL_Rect rect = {
                    .x = x * pixels_per_cell,
                    .y = y * pixels_per_cell,
                    .w = pixels_per_cell,
                    .h = pixels_per_cell
                };

                SDL_RenderFillRect(renderer, &rect);
            }
        }
    }

    SDL_RenderPresent(renderer);
}

int main(int argc, char** argv)
{
    if(!initialize()) return -1;

    Uint32 current_time = SDL_GetTicks(); // ellapsed ms since initialization

    while (state != EXIT)
    {
        process_messages();

        if(state == RUNNING)
        {
            Uint32 delta_time = SDL_GetTicks() - current_time;

            if(delta_time >= tickrate)
            {
                current_time += delta_time;

                update_game();
            }
        }
        
        render_frame();
    }

    cleanup();

    return 0;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I would go for a one [m|c]alloc for that cells, rather than a unique for each cell. Besides that, those two bools in struct Cell could be hosted with only one int8 type.(or even better, 4 cells could be hosted with only one int8) \$\endgroup\$
    – user230399
    Sep 12 '20 at 20:34
  • \$\begingroup\$ @911992: It's one alloc per row, not per Cell. (That would be totally insane; struct Cell is smaller than struct Cell*). This is just the common sub-optimal choice of using an array of row pointers instead of a single flat array with manual 2D indexing. Like in C++ when people use a vector of vectors. So yes, one single allocation would still be better, but it's not a total disaster like I thought upon seeing your comment. \$\endgroup\$ Sep 13 '20 at 13:34
8
\$\begingroup\$

General Observations

Initially I was very impressed because the file started with the declaration of 2 enums. All of the functions seem to follow the single responsibility principle and that is great! In main() I might have put the game loop into its own function. I like seeing the cleanup() function.

I'm really curious about how many classes you would use to implement this program in C++?

I would separate the game logic from the display logic. That way the game would work with different display mechanisms. It would also be more like some of the object oriented design patterns such as MVC or MVVM.

Missing Memory Allocation Check

In C++ if new fails it throws an exception that would halt the program unless the exception was handled, this is not true in the C programming language. When memory allocation fails in C the memory allocation function (calloc(), malloc() or realloc()) returns NULL (nullptr in C++). While memory allocation failure is rare these days with the large memories most processors have it can still occur. To prevent a Segmentation Violation or memory corruption the value of the pointer return by the memory allocation function should always be tested before use.

The example below uses sizeof(**cells) rather than sizeof(struct Cell) because this allows the programmer to make only one edit to the line containing calloc() rather than multiple edits if the type of cells is changed:

static bool initialize(void)
{
    if (SDL_Init(SDL_INIT_VIDEO) != 0)
    {
        return false;
    }

    int32_t window_size = field_size * pixels_per_cell;

    window = SDL_CreateWindow("Conway's Game of Life", 50, 50, window_size, window_size, SDL_WINDOW_OPENGL);
    renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);

    SDL_ShowWindow(window);

    cells = calloc(field_size, sizeof(*cells));
    if (!cells)
    {
        fprintf(stderr, "The calloc() function returned NULL for the initial allocation of cells\n");
        return false;
    }

    for (int32_t i = 0; i < field_size; i++)
    {
        cells[i] = calloc(field_size, sizeof(**cells));
        if (!cells[i])
        {
            fprintf(stderr, "The calloc() function returned NULL for the allocation of cells[%d]\n", i);
            return false;
        }
    }

    return true;
}

Prefer size_t Over int for Indexes into Arrays

All of the loops in the program seem to utilize int32_t rather than size_t. The type size_t is unsigned and this makes it safer to use as an index because it can't be negative.

The type Uint32 used in main() is not a standard type and doesn't compile on my system, perhaps you meant uint32_t which is part of the C standard.

Global Variables

I realize the variables aren't quite global because all the variables are static and this is the method for creating private variables in C, but I don't see a good reason why most of the variables aren't declared in main() or as they are needed and passed into the functions that require them.

\$\endgroup\$
3
  • \$\begingroup\$ using unsigned for never-negative numbers is not always the best case. For example, if a function len(list) returns the length of a list in size_t, then for(size_t i = 0; i < len(list); i++) {} will loop quite a few times on a 0-length list, where as if len returned a singed number, this would be work as expected, and iterate through all element except the last. \$\endgroup\$ Sep 13 '20 at 3:37
  • 1
    \$\begingroup\$ Uint32 comes from SDL and is the type that gets returned by SDL_GetTicks() \$\endgroup\$
    – Eric
    Sep 13 '20 at 13:11
  • 3
    \$\begingroup\$ @CarsonGraham: 0 < 0 is false in the first i < len(list) so execution never enters the loop. The danger is when you try to do something like i < len-1 with unsigned. Perhaps you meant to write that, since you talk about iterating all elements except the last. Yes, you have to be careful to do stuff like i+1 < len instead of i < len-1 if unsigned len can be zero. \$\endgroup\$ Sep 13 '20 at 13:38
8
\$\begingroup\$
  • Reduce number of tests.

    An if in the tight loop is a performance killer. Since you test for cells[x][y].alive in update_game anyway, there is no reason to test for cell equality in count_neighbours. Consider

      static int32_t count_neighbours(const int32_t cell_x, const int32_t cell_y)
      {
          int32_t count = 0;
    
          for(int32_t x = max(cell_x - 1, 0); x <= min(cell_x + 1, field_size - 1); x++) {
              for(int32_t y = max(cell_y - 1, 0); y <= min(cell_y + 1, field_size - 1); y++) {
                  if(cells[x][y].alive) {
                      count++;
                  }
              }
          }
    
          return count;
      }
    

    followed by

      for(int32_t x = 0; x < field_size; x++) {
          for(int32_t y = 0; y < field_size; y++) {
              int32_t count = count_neighbours(x, y);
    
              if(!cells[x][y].alive && count == 3) {
                  cells[x][y].next = true;
              }
    
              if(cells[x][y].alive && (count < 3 || count > 4)) {
                  cells[x][y].next = false;
              }
    
              if(cells[x][y].alive && (count == 3 || count == 4)) {
                  cells[x][y].next = true;
              }
          }
      }
    
  • Simplify logic.

Notice that two last ifs are the long way to say

            if (cells[x][y].alive) {
                cells[x][y].next = (count == 3 || count == 4);
            }

and the entire update_game collapses to

            if (cells[x][y].alive) {
                cells[x][y].next = (count == 3 || count == 4);
            } else {
                cells[x][y].next] = (count == 3);
            }

Now, because each branch just assigns a boolean value to the same variable, I would seriously consider a ternary:

            cells[x][y].next = cells[x][y].alive? (count == 3 || count == 4): (count == 3);

Finally, since count == 3 makes the cell alive regardless of its previous state,

            cells[x][y].next = (count == 3) || (cells[x][y].alive && count == 4);

seems even cleaner.

  • Any time you feel obliged to put comments like // calculate next state for the cells and // set alive states for drawing and reset next, consider to factor the commented code into a function. Especially if that piece of code is a loop.

    compute_next_state() and set_alive_states() seem like very good names.

    Another argument to factor out set_alive_states() into a function is that it does not depend on the game rules and can be reused.

  • I see no reason to declare cells as an array of pointers.

      static struct Cell * cells;
    

    initialized as

      cells = calloc(field_size, sizeof (struct Cell));
    

    would do as well, with no need to calloc individual cells. As a side note,

      cells = calloc(field_size, sizeof(cells[0]));
    

    is more idiomatic C.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I see no reason to declare cells as an array of pointers. - yes, but you do need to say something about how to do manual 2D indexing, or cast to a variable-dimension 2D array type. (C99 VLA support makes that legal in C, not C++). The rest of the code does stuff like cells[x][y] which will no longer Just Work with static struct Cell *cells. An array of pointers to arrays is generally worse for performance but does is easier to write code for when the dimensions are variable. (But the OP has static const dimensions so they should just static struct Call cells[field_size][field_size]) \$\endgroup\$ Sep 13 '20 at 13:43
2
\$\begingroup\$

Use a normal 2D array, not pointers to rows.

(Or actually you're doing pointers to columns, since you index as [x][y], with each vertical column allocated with a separate calloc. Video memory has contiguous rows so it's more normal to draw along each row. Idiomatic C/C++ would normally use [y][x] indexing, looping over y in outer loops and x in inner loops, so you're still looping over contiguous memory of a row-major 2D array. It's basically fine to have the array rows store columns of your image, it's just weird, and maybe makes drawing slower.)

An array of pointers to arrays is usually less efficient than a single contiguous 2D array; the extra indirection is less efficient for the CPU and harder for the compiler to optimize than scaling by the row width. Especially when the array dimension is a compile-time constant, but even with runtime-variable sizes manual 2D indexing is generally preferable. You could #define a macro like INDEX(x,y,stride) that lets you write cells[INDEX2D(x,y,field_size)]. Or an inline function that returns size_t would also be idiomatic in modern C.

Or in this case, your simple program has compile-time constant array dimensions.

In C++ you can use static const integers as array dimensions for global / static variables, like static struct Cell cells[field_size][field_size]. (Implicitly zero-initialized because it's in static storage). But in C, that doesn't work because a const variable isn't a "constant expression", unlike in C++ :(

One of the standard workarounds is to define C constants as preprocessor macros with #define, or as enum constants (examples in this SO answer). It's a good idea (and idiomatic for C) to give them all-caps names because they're not variables.

Instead of keeping just a pointer in static storage, might as well go all-in and use static storage for the whole array. With a zero initializer, it won't take up space in your executable (on normal C implementations that have a BSS).

enum { FIELD_SIZE = 200 };
static struct Cell cells[FIELD_SIZE][FIELD_SIZE];

If you want to make runtime-variable sizes possible in the future, one large calloc and manual 2D indexing with a macro or helper function is one way. Or you can cast to (struct Cell (*)[field_size]), a pointer to an array of struct Cell. A 2D array is an array of arrays, so a pointer to an actual array type is to a 2D array what a pointer to an element is to a 1D array.

    // given   void *p; size_t row; size_t col;

    struct Cell (*arr)[field_size] = p;
    struct Cell tmp = arr[row][col];

    // field_size can even be a variable; C99 VLA support works for casting pointers

You could initialize arr with a calloc() return value to use one calloc as a dynamically allocated 2D array.


Use two arrays instead of old/new fields within each element

    for(x) {
        for(y) {
            cells[x][y].alive = cells[x][y].next;
            cells[x][y].next = false;
        }
    }

That loop over every element would be unnecessary if you instead swapped pointers to whole 2D bool arrays, like prev and curr. You count neighbours in the previous generation then assign a value to the current generation.

As well as avoiding this work, it's also somewhat better for performance. Same total memory, but only half the cache lines get written in each generation. This is better if it doesn't all fit in L1d cache. Possibly also better cache locality when looking at neighbours in the previous row; it's fewer bytes away.

If performance and cache footprint were a big deal, you'd try to use less temporary storage, maybe just an extra row at a time. An "old" row is only needed while working on the row immediately below it. (And then maybe you would want an array of row pointers so you could swap out the storage for one row without copying.) And / or you'd use denser storage, like 1 or 2 bits per cell instead of a whole bool which is at least as large as a char. (In practice 1 byte on normal C implementations). Also, just for fun, SIMD implementations of Life are possible, giving massive speedups on modern x86.

Don't busy-wait, ideally sleep until an event or timeout

Your main loop just calls SDL_PollEvent (via your process_messages wrapper) and keeps checking the time until it's time to actually update the field.

Nowhere does it sleep, not even for like 10 or 20 milliseconds.

Ideally SDL would have a way to give SDL_WaitEvent a timeout so it can block until an event, or until you want to wake up and update, whichever comes first. Like the POSIX select() function. But unfortunately it seems SDL doesn't have a way to do that easily or maybe at all. So for this toy program, perhaps just put a 10 or 30 ms sleep into your main loop, saving some CPU but still waking it up unnecessarily between times you want to actually draw.

Actually sleeping for 200ms would delay response to mouse clicks too long.

Make sure to poll until you empty the message queue before sleeping, if you introduce a sleep. See https://stackoverflow.com/questions/56386995/sdl-2-how-use-the-event-system-and-draw-asynchronously. I also found https://stackoverflow.com/questions/18860243/sdl-pollevent-vs-sdl-waitevent.

\$\endgroup\$
1
\$\begingroup\$

Since this is a standalone program, there is no need to modify functions as static

regarding:

int main(int argc, char** argv)

Since the parameters argc and argv[] are not used, the compiler (when the warnings are enabled, as they should be) will output two warning messages about unused parameters. Suggest using the other valid signature for main().

int main( void )

Several of the functions take no parameters. strongly suggest such functions be declared with ( void ) as the parameter list. Otherwise the compiler will generate code that can take any number/type of parameters.

Using the Variable Length Array feature of C, you can avoid the calls to calloc() and free() by simply declaring the 2d array of struct cell types.

struct cell cells[ field_size ][ field_size ] = {0};
\$\endgroup\$
4
  • \$\begingroup\$ SDL requires main to always have argc and argv[] and while not having them could work on some platforms such as linux it will not on some including windows. \$\endgroup\$
    – nullptr
    Sep 13 '20 at 4:28
  • 1
    \$\begingroup\$ I would advice against declaring cells as a VLA, since this is a potentially large array, and you might not have enough stack space for it. While Linux, by default, assigns a very generous 8 MiB to the stack of the main thread, so you might get close to a field_size of 2048 for a 2-byte struct cell, this is not something you should rely on. \$\endgroup\$
    – G. Sliepen
    Sep 13 '20 at 8:45
  • 1
    \$\begingroup\$ @G.Sliepen: Right, you don't want that to be a local in main, you want that to be static struct Call cells[field_size][field_size] at global scope so it goes in the BSS. That's how you get it zero-initialized for free like calloc, which automatic storage (a VLA) wouldn't be. Remember that field_size is static const so we it doesn't have to be a VLA. \$\endgroup\$ Sep 13 '20 at 13:45
  • 1
    \$\begingroup\$ Array dimensions are in elements, not bytes, so multiplying by sizeof( struct cell ) is not appropriate inside the array declaration. \$\endgroup\$ Sep 13 '20 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.