17 января 2011

Игра в "Жизнь"

Привет. А знаете ли вы, кто такой Джон Хортон Конвей? А знаете ли вы про игру "Жизнь"? Ответы на эти вопросы мне не интересны. Я вам в любом случае буду об этом рассказывать. Джон Хортон, если верить википедии, обладатель равного единице числа Эрдёша, а так же автор игры "Жизнь". Нас конечно же интересует последнее.

Игра "Жизнь", если опять таки верить википедии, клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. Я не буду вдаваться в историю возникновения этой игры или философствовать на тему ее гениальности, я попробую ее сделать на Си с использованием библиотеки ncurses.

В игре очень простые правила. Игровое поле представляет собой разбитое на клетки пространство. Каждая клетка может быть живой или мертвой. Если вокруг мертвой клетки три живые, то она оживает. Что бы клетка не умерла, вокруг нее должны находиться две или три других живых клеток. Вот и все правила.

Теперь непосредственно к реализации:

#if 0
gcc -o life $0 -lncurses -W -Wall -Wextra
exit
#endif
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ncurses.h>
#include <locale.h>

#define SIZE_R 20 /* Строки. */
#define SIZE_C 70 /* Колонки. */

/*
 * Это клетка.
 */
struct cell
{
  int state; /* Это состояние клетки. 1 - живая. 0 - мертвая. */
  int next;  /* Это состояние которое клетка готовиться принять. */
};

/*
 * Создает сетку клеток.
 */
struct cell**
grid_malloc();

/*
 * Высвобождает память выделенную для сетки.
 */
void
grid_free(struct cell** grid);

/*
 * Что бы сетка была замкнута, мы нормализуем координату n таким
 * образом что бы она попадала в отрезок от 0 до mod.
 */
int
normalize(int n, int mod);

/*
 * Эта полный шаг симуляции жизни сетки.
 */
void
grid_step(struct cell** grid);

/*
 * Эта функция которая позволяет получить текущее состояние клетки не
 * нормализуя координаты заранее.
 */
int
grid_get_state(struct cell** grid, int x, int y);

/*
 * Эта функция вернет true если на сетке есть жизнь, в противном
 * случае false.
 */
bool
grid_is_life(struct cell** grid);

/*
 * Эта функция нарисует сетку.
 */
void
grid_print(struct cell** grid);

/*
 * Эта функция отчистит сетку.
 */
void
grid_clear(struct cell** grid);

int
main()
{
  int i;
  int j;
  int x;
  int y;
  char ch = 0;
  bool set = true;
  bool done = false;

  struct cell** grid;

  /*
   * Что бы в ncurses можно было выводить русские буквы нужно
   * установить локаль.
   */
  setlocale(LC_ALL, "");

  /*
   * Инициализируем ncurses.
   */
  initscr();

  /*
   * Получаем размеры терминала.
   */
  getmaxyx(stdscr, y, x);

  /*
   * Если терминал меньше чем наша сетка, то мы закроем программу с
   * ошибкой.
   */
  if (x <= SIZE_C || y <= SIZE_R)
    {
      printf("Error: small window.\n");
      /*
       * Важно не забывать освободить ресурсы занятые ncurses. Можно
       * так же проверить значение которое вернет endwin, но для
       * данного примера это не критично. Но только для данного
       * примера.
       */
      endwin();
      exit(1);
    }

  /*
   * Переводим терминал в режим, в котором нажатые кнопки передаются
   * без нажатия Enter.
   */
  cbreak();
  /*
   * Отменяем вывод вводимых символов.
   */
  noecho();
  /*
   * Ждем ввода от пользователя. C true в качестве второго аргумента,
   * мы бы не ждали ввода пользователя.
   */
  nodelay(stdscr, false);

  grid = grid_malloc();
  grid_clear(grid);
  grid_print(grid);

  i = 0;
  j = 0;
  move(i, j);
  while(!done)
    {
      if (set)
        {
          /* Это ожидание ввода символа. */
          ch = getch();
          switch (ch)
            {
            case 113: /* q */
              done = true;
              break;
            case 10: /* enter */
              set = !set;
              nodelay(stdscr, !set);
              break;
            case 32: /* пробел */
              if(grid[i][j].state == 1)
                grid[i][j].state = 0;
              else
                grid[i][j].state = 1;
              break;
            case 65: /* вверх */
              i = normalize(i - 1, SIZE_R);
              break;
            case 66: /* вниз */
              i = normalize(i + 1, SIZE_R);
              break;
            case 68: /* влево */
              j = normalize(j - 1, SIZE_C);
              break;
            case 67: /* вправо */
              j = normalize(j + 1, SIZE_C);
              break;
            case 127: /* backspace */
              grid_clear(grid);
              i = 0;
              j = 0;
              break;
            }
        }
      else
        {
          i = SIZE_R;
          j = SIZE_C;
          grid_step(grid);
          napms(150); /* Это задержка в миллисекундах. */
          ch = getch();
          switch (ch)
            {
            case 113:
              done = true;
              break;
            case 10:
              set = !set;
              nodelay(stdscr, !set);
              i = 0;
              j = 0;
              break;
            }
          if (!grid_is_life(grid))
            {
              set = !set;
              nodelay(stdscr, !set);
              i = 0;
              j = 0;
            }
        }
      grid_print(grid);
      /*
       * Эта функция передвинет курсор для вывода символов.
       */
      move(i, j);
      /*
       * Эта функция обновит экран.
       */
      refresh();
    }

  grid_free(grid);
  endwin();

  return 0;
}

int
normalize(int n, int mod)
{
  n = n % mod;

  if (n == -1)
    n = mod - 1;

  return n;
}

int
grid_get_state(struct cell** grid, int x, int y)
{
  return (grid[normalize(x, SIZE_R)][normalize(y, SIZE_C)]).state;
}

void
grid_step(struct cell** grid)
{
  int i;
  int j;
  int count_life_cells;

  /*
   * Здесь мы узнаем какое следующие состояние у всех клеток сетки. Это
   * не самый оптимальный алгоритм, он самый простой.
   */
  for (i = 0; i < SIZE_R; ++i)
    {
      for (j = 0; j < SIZE_C; ++j)
        {
          count_life_cells
            = grid_get_state(grid, i+1, j+1)
            + grid_get_state(grid, i+1, j)
            + grid_get_state(grid, i,   j+1)
            + grid_get_state(grid, i-1, j-1)
            + grid_get_state(grid, i-1, j)
            + grid_get_state(grid, i,   j-1)
            + grid_get_state(grid, i-1, j+1)
            + grid_get_state(grid, i+1, j-1);

          if (grid_get_state(grid, i, j) == 1)
            {
              if (count_life_cells == 2 || count_life_cells == 3)
                grid[i][j].next = 1;
              else
                grid[i][j].next = 0;
            }
          else
            {
              if (count_life_cells == 3)
                grid[i][j].next = 1;
            }
        }
    }

  /*
   * Выставляем новое состояние клетки в текущее.
   */
  for (i = 0; i < SIZE_R; ++i)
    {
      for (j = 0; j < SIZE_C; ++j)
        {
          grid[i][j].state = grid[i][j].next;
        }
    }
}

bool
grid_is_life(struct cell** grid)
{
  int i;
  int j;

  /*
   * Если хоть одна из клеток жива, поле считается живым.
   */
  for (i = 0; i < SIZE_R; ++i)
    {
      for (j = 0; j < SIZE_C; ++j)
        {
          if (grid[i][j].state == 1)
            return true;
        }
    }
  return false;
}

void
grid_print(struct cell** grid)
{
  int i;
  int j;
  char ch;

  for (i = 0; i < SIZE_R; ++i)
    {
      for (j = 0; j < SIZE_C; ++j)
        {
          if (grid[i][j].state == 1)
            ch = 'O';
          else
            ch = '.';
          /*
           * Выводим либо 'O' если клетка жива, либо '.' если клетка
           * мертва. A_BOLD это флаг жирности. Надеюсь вы заметили что
           * сначала указывается строка, а потом колонка, в которой
           * нужно вывести символ.
           */
          mvaddch(i, j, ch | A_BOLD);
        }
    }
}

void
grid_clear(struct cell** grid)
{
  int i;
  int j;

  for (i = 0; i < SIZE_R; ++i)
    {
      for (j = 0; j < SIZE_C; ++j)
        {
          grid[i][j].state = 0;
          grid[i][j].next  = 0;
        }
    }
}

struct cell**
grid_malloc()
{
  int i;
  struct cell** grid;

  grid = malloc(sizeof(struct cell*) * SIZE_R);

  for (i = 0; i < SIZE_R; ++i)
    {
      grid[i] = malloc(sizeof(struct cell) * SIZE_C);
    }

  return grid;
}

void
grid_free(struct cell** grid)
{
  int i;

  for (i = 0; i < SIZE_R; ++i)
    {
      free(grid[i]);
    }

  free(grid);
}

Для каждой неизвестной вам функции вы можете почитать man, для ncurses он очень хорош.

Это не самая лучшая реализации игры "Жизнь". Зато ее было очень весело делать.