Реализация игры Жизнь на Python

Меня уже давно интересовала конвеевская игра "Жизнь", и вот наконец-то у меня дошли руки попробовать реализовать ее наиболее простым и элегантным способом. Если кто-не знает, что это за игра - на русской Википедии есть хорошее описание. Для тех, кто знает, но забыл, я постараюсь напомнить классические правила:

• Время дискретно.
• Игровое поле - плоскость, состоящая из клеток, у каждой клетки восемь соседей.
• Клетки могут находится в двух состояниях: живом или мертвом. Совокупность живых клеток называется поколением.
• В процессе игры каждая клетка может неограниченное количество раз переходить из одного состояния в другое.

Правила перехода тоже не отличаются сложностью:

• Каждое следующее поколение рассчитывается на основе предыдущего.
• Мертвая клетка оживает, если рядом с ней находится ровно 3 живые клетки.
• Живая клетка продолжает жить, если рядом с ней находится 2 или 3 живые клетки.

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

Наивная реализация

Начать лучше с самого прямолинейного способа. Он выглядит примерно так:

1. Создается двумерный массив из булевых значений, где True бы означал наличие живой клетки, а False - мертвой.
2. Генерируется новый массив.
3. Для каждой клетки определяется число живых соседей и на основании этого определяется, будет ли она жить в новом поколении.
4. Новый массив записывается на место старого.
5. Происходит возврат к пункту 2.

Обычное в этом месте появляется потребность определять соседей клетки для реализации пункта 3. Поскольку сейчас мы имеем игровое поле, представленное в виде массива - есть риск выйти за его пределы. Есть несколько способов этого избежать:

• Отбрасывать в функции все обращения к i, j < 0 и i >= n, j >= m (где m и n - размер строки и столбца соответственно).
• Замкнуть поле на само себя - все обращения к клеткам из предыдущего пункта считать обращением к клетке с другой стороны поля. Т.е i < 0 будет обращением к m - i, i > m будет обращением к клетке m - i. Для j формулы аналогичны.
• Оградить игровое поле со всех сторон элементами, обозначающими его границу. Такие элементы физически не являются ни мертвым, ни живыми, но при подсчете числа живых соседей считаются мертвыми.

Алгоритм хоть и прост для понимания, но имеет ряд недостатков:

• Имеет линейное от размеров поля время работы.
• Двойное потребление памяти (нужно хранить предыдущее поколение + новое).
• Требует много кода для реализации.

Все это хочется взять и оптимизировать.

Наивная оптимизация

Можно уменьшить время вычисления следующего поколения с помощью списка значений, которые могут измениться на следующем шаге. А измениться могут только две категории клеток: живые и их соседи. Введение еще одной структуры немного усложнит код, увеличит потребление памяти до тройного в худшем случае, но время работы станет линейным только в худшем случае (раньше оно было линейным всегда).

Кардинальная оптимизация с переосмыслением

Если продолжить развивать идею из предыдущего пункта (хранение списка координат живых клеток и их соседей), можно уйти и от моделирования "в лоб". В конце концов, состояние поля можно выразить просто списком живых клеток. Почему это возможно? Зная только координаты живых клеток мы можем воссоздать поле в изначальном состоянии. Хранить состояние соседних с живыми клеток нам тоже не требуется - поскольку состояний у клеток всего два (жива-мертва) - все, кто не живы, мертвы, а получить координаты соседей по координатам клетки тоже достаточно просто. Плюсы этого варианта достаточно заманчивы:

• Экономия памяти. Нам не нужно хранить все поле целиком.
• Время такое же, как и в предыдущем разделе.
• Динамичность игрового поля. Размеры поля можно менять на протяжении игры в зависимости от расположения живых клеток.
• Алгоритм очень легко параллелится. Можно создать несколько потоков, которые бы принимали список живых клеток и координаты рассматриваемой клетки. Результат работы потоков склеивается и получается новый список живых клеток.
• Он красивый:)

Я не люблю везде засовывать ООП, поэтому мой вариант основан целиком на функциях. Все начинается с функции, генерирующей новое поколение клеток на основе списка живых клеток предыдущего поколения:

def new_step(alive_cons):
    board = itertools.chain(*map(get_neighbors, alive_cons))
    new_board = set([con
                 for con in board
                 if is_alive_con(con, alive_cons)])
    return list(new_board)

Запутанная конструкция board = itertools.chain(*map(get_neighbors, alive_cons)) всего лишь сохраняет в переменной board список всех живых ячеек и их соседей. Теперь настала очередь функции is_alive_con.

def is_alive_con(con, alive_cons):
    alive_neighbors = calculate_alive_neighbors(con, alive_cons)
    if (alive_neighbors == 3 or
            (alive_neighbors == 2 and con in alive_cons)):
        return True
    return False

В следующей реализованы правила перехода клетки из одного состояния в другое.

def calculate_alive_neighbors(con, alive_cons):
    return len(filter(lambda x: x in alive_cons,
                      get_neighbors(con)))

Осталось рассмотреть самое важное - функцию, которая возвращает список всех соседей клетки на основе ее координат.

def get_neighbors(con):
x, y = con
neighbors = [(x + i, y + j)
             for i in xrange(-1, 2)
             for j in xrange(-1, 2)
             if not i == j == 0]
return neighbors

Здесь нет необходимости проверять корректность координат клеток соседей - некорректные координаты (приводящие к обращению за пределы поля) и так не должны будут встретиться в списке живых. Корректность имеет смысл проверять уже после создания нового поколения. У меня для этого реализованы две функции - одна проверяет корректность координат клетки, другая делает нечто с "неправильными" - в этой реализации просто отбрасывает все некорректные значения:

def is_correct_con(size, con):
x, y = con
return all(0 <= coord <= size - 1 for coord in [x, y])


def correct_cons(size, cons):
    return filter(lambda x: is_correct_con(size, x), cons)

Заключение

Подход, при котором сохраняются только координаты клеток с определенным состоянием может применяться не только для моделирования GoF, но и для других игр, реализуемых в терминах клеточных автоматов. Например, при реализации крестиков-ноликов можно сохранять только координаты клеток, в которых стоит крестик или нолик, а не моделировать все поле сразу. Это достаточно удобно, если нужно смоделировать игру по нестандартным правилам (доска не 3*3 и требуется поставить в ряд не 3 символа). Проверять, образовалась ли на доске выигрышная комбинация можно по аналогии с определением живости клетки GoF, но чуть сложнее:

• Получить список соседей по диагоналям, вертикалям и горизонталям.
• Последовательно подсчитать, сколько соседей имеет такое же состояние (крестик или нолик), как и исходная клетка.

Полную реализацию можно посмотреть на github

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