Создание игры «Жизнь» на C++

Место действия игры — «вселенная» — размеченная на клетки ограниченная плоскость. Каждая клетка на этой плоскости может быть «живой» или «мертвой» (пустой). У клетки есть 8 соседей — окружающие ее клетки.

Правила игры

Первое поколение — это положение игровых клеток в начале игры. Будем заполнять его случайным образом. Каждое новое поколение рассчитывается на основе предыдущего по таким правилам:

• В пустой клетке, рядом с которой ровно три живые клетки, зарождается жизнь.
• Если у живой клетки есть две или три живые соседки, то эта клетки продолжает жить. Иначе, клетка умирает (от «одиночества» или «перенаселенности»).

Игра прекращается, если на поле не останется ни одной живой клетки или при очередном шаге ни одна клетка не меняет своего состояния (складывается стабильная конфигурация).

Описание игры жизнь в Википедии.

Игровое поле

Игровое поле будет храниться в двумерном массиве побитовых структур. Количество строк которого — высота поля, а столбцов — его ширина.

// Побитовая структура для хранения состояние клетки
struct point {
    unsigned is_live:1;
};

/* Ширина игрового поля */
#define __WORLD_HEIGHT__ 10

/* Высота игрового поля */
#define __WORLD_WIDTH__ 10

// Игровое поле размером 10x10 клеток
point world[__WORLD_WIDTH__][__WORLD_HEIGHT__];

Первое поколение игры будет генерироваться случайным образом. Для этого воспользуемся библиотекой <random> из C++ 11.

/*
 * Инициализация первого поколения игры псевдослучайными значениями
 */
void init_world(point world[][__WORLD_HEIGHT__])
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 10000);

    unsigned int i, j;

    for (i = 0; i < __WORLD_WIDTH__; i++) {
        for (j = 0; j < __WORLD_HEIGHT__; j++) {
            unsigned int num = dis(gen);
            if (num % 2 == 0) {
                world[i][j].is_live = 1;
            } else {
                world[i][j].is_live = 0;
            }
        }
    }
}

После формирования первого поколения начнется игровой цикл, который завершится, когда все клетки умрут, либо будет найдена оптимальная конфигурация (одинаковое состояние клеток на текущем и предыдущем шаге).

Клетки-соседи

Подсчетом количества живых клеток будет заниматься функция get_live_count.

/*
 * Количество живых клеток на игровом поле
*/
unsigned int get_live_count(point world[][__WORLD_HEIGHT__])
{
    unsigned int count = 0;
    unsigned i, j;
    for (i = 0; i < __WORLD_WIDTH__; i++) {
        for (j = 0; j < __WORLD_HEIGHT__; j++) {
            if (world[i][j].is_live == 1) {
                count++;
            }
        }
    }
    return count;
}

Для каждого шага цикла нужно сгенерировать новое поколение, в соответствии с правилами игры. Напишем функцию, которая будет определять координаты соседей клетки.

/*
 * Получение координат соседей точки (окрестность мура 1 порядка)
*/
void read_point_neighbors(signed int nb[][2], unsigned int x, unsigned int y)
{
    unsigned int i, j;
    unsigned int k = 0;

    for (i = x - 1; i <= x + 1; i++) {
        for (j = y - 1; j <= y + 1; j++) {
            if (i == x && j == y) {
                continue;
            }
            nb[k][0] = i;
            nb[k][1] = j;
            k++;
        }
    }
}

Функция read_point_neighbors принимает указатель на двумерный массив (для записи результата) и координаты x, y точки, для которой ищем соседей.

Необходимо знать количество живых соседей клетки. Для этого напишем функцию get_live_neighbors.

/*
 * Количество живых соседей у клетки с координатами x, y
 */
unsigned int count_live_neighbors(point world[][__WORLD_HEIGHT__], unsigned int x, unsigned int y)
{
    unsigned int count = 0;
    unsigned int i;
    signed int nb[8][2];
    signed int _x, _y;

    read_point_neighbors(nb, x, y);

    for (i = 0; i < 8; i++) {
        _x = nb[i][0];
        _y = nb[i][1];

        if (_x < 0 || _y < 0) {
            continue;
        }
        if (_x >= __WORLD_WIDTH__ || _y >= __WORLD_HEIGHT__) {
            continue;
        }

        if (world[_x][_y].is_live == 1) {
            count++;
        }
    }

    return count;
}

Функция принимает ссылку на массив игрового поля и координаты x, y клетки.

Смена поколения

Теперь мы можем быстро получить все данные, нужные для того, чтобы построить следующее поколение клеток. Напишем функцию next_generation для формирование нового поколения:

/*
 * Сгенерировать следующее поколение игрового мира
 */
void next_generation(point world[][__WORLD_HEIGHT__], point prev_world[][__WORLD_HEIGHT__])
{
    unsigned int i, j;
    unsigned int live_nb;
    point p;

    for (i = 0; i < __WORLD_WIDTH__; i++) {
        for (j = 0; j < __WORLD_HEIGHT__; j++) {
            p = prev_world[i][j];
            live_nb = count_live_neighbors(prev_world, i, j);

            if (p.is_live == 0) {
                if (live_nb == 3) {
                    world[i][j].is_live = 1;
                }
            } else {
                if (live_nb < 2 || live_nb > 3) {
                    world[i][j].is_live = 0;
                }
            }
        }
    }
}

Еще одно условие для завершения игры — когда у двух поколений, идущих друг за другом, идентичное состояние клеток. Для сравнения двух поколений создадим две функции — copy_world и cmp_world. Первая будет копировать состояние игрового поля во временный массив перед генерацией следующего поколения. Вторая будет сравнивать расположение клеток на двух игровых полях.

/*
 * Копирование игрового мира. Используется для сохранения предыдущего поколения
*/
void copy_world(point src[][__WORLD_HEIGHT__], point dest[][__WORLD_HEIGHT__])
{
    unsigned int i, j;
    for (i = 0; i < __WORLD_WIDTH__; i++) {
        for (j = 0; j < __WORLD_HEIGHT__; j++) {
            dest[i][j] = src[i][j];
        }
    }
}


/*
 * Сравнение игровых миров текущего и предыдущего поколения
 */
int cmp_world(point w1[][__WORLD_HEIGHT__], point w2[][__WORLD_HEIGHT__])
{
    unsigned int i, j;
    for (i = 0; i < __WORLD_WIDTH__; i++) {
        for (j = 0; j < __WORLD_HEIGHT__; j++) {
            if (w1[i][j].is_live != w2[i][j].is_live) {
                return -1;
            }
        }
    }
    return 0;
}

Функция print_world будет выводить на экран состояние игрового поля для каждого нового поколения.

/*
 * Вывести на экран игровое поле
*/
void print_world(point world[][__WORLD_HEIGHT__])
{
    unsigned int i, j;
    for (i = 0; i < __WORLD_WIDTH__; i++) {
        for (j = 0; j < __WORLD_HEIGHT__; j++) {
            if (world[i][j].is_live == 1) {
                cout << '*';
            } else {
                cout << ' ';
            }
            cout << ' ';
        }
        cout << endl;
    }
}

Игровой цикл

Определим функцию main, которая будет запускать игровой процесс.

int main()
{
    point world[__WORLD_WIDTH__][__WORLD_HEIGHT__];
    point prev_world[__WORLD_WIDTH__][__WORLD_HEIGHT__];

    init_world(world);
    unsigned int live_points = -1;
    bool is_optimal = false;

    do {
        print_world(world);
        copy_world(world, prev_world);
        next_generation(world, prev_world);

        is_optimal = cmp_world(world, prev_world) == 0;
        live_points = get_live_count(world);

        if (is_optimal) {
            cout << "Optimal configuration detected" << endl;
        }

        if (live_points == 0) {
            cout << "All points died" << endl;
        }
        msleep(1000);
    } while (live_points != 0 && !is_optimal);

    return 0;
}

Весь исходный код игры.

Компиляция

Для компиляции проекта нужна поддержка C++ 11. В GCC 4.7 такая поддержка включается так:

c++ -std=c++11 -o life life.cpp

Для включения поддержки C++ 11 в Dev C++, зайдите в меню «Tools → Compiler Options → (выберите ваш компилятор) → Settings → Code Generation». Установите значение опции «Language standard» на C++11.

В Visual Studio 2010 есть частичная поддержка C++ 11. По крайней мере, <random> должен быть.

Пример работы игры размером 20 × 20 клеток:

Внимательный читатель мог заметить, что в правилах игры присутствует «периодическая конфигурация» — когда текущее состояние игры повторяет любое предыдущее состояние на всех шагах.

В этом примере мы не стали писать такой функционал, потому что при большом количестве итераций может понадобиться много места для хранения истории. Но при желании, вы можете реализовать эту фишку и поделиться ей с другими читателями в комментариях.