Клеточный автомат Конвея

Игра «Жизнь» (англ. Conway's Game of Life) — это клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.

Место действия этой игры — размеченная на клетки поверхность или плоскость.

Эта поверхность может быть безграничной, ограниченной, или замкнутой.
Каждая клетка на этой поверхности может находиться в двух состояниях: «живой» или «мёртвой».
Клетка имеет восемь соседних клеток, окружающих её.
Распределение живых клеток в начале игры называется первым поколением.
Каждое следующее поколение рассчитывается на основе предыдущего по правилам:
- в пустой клетке, рядом с которой ровно три живые клетки, зарождается жизнь;
- если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить;
- во всех остальных случаях клетка умирает.

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

Классические правила игры Жизнь Конвея, коротко, можно записать формулой B3/S23. Где B — рождение, S — сохранение. Цифрами обозначено количество соседей.

Рис. 1.

На анимированном рисунке показан пентадекатлон (p15). Найден в 1970 году Джоном Конвеем.

from tkinter import *               # Импортируем все функции из библиотеки tkinter

SIDE = 26; SIZE = 14                # Размер поля в клетках, клетки в пикселях
colores = ['#aa9', '#0f0', '#ccd']  # Цвет поля, жизни, сетки
cell  = []                          # Клетки

cnv = Canvas(width=SIDE*SIZE, height=SIDE*SIZE)             # Canvas с именем cnv
cnv.pack()
for y in range(SIDE):               # Создаём поле
    for x in range(SIDE):
        cell.append(cnv.create_rectangle(x*SIZE, y*SIZE, (x+1)*SIZE, (y+1)*SIZE,
                    fill=colores[0], outline=colores[2], width=1))

mainloop()                          # Главный цикл программы

Лист. 1. Программа

from tkinter import *               # Импортируем все функции из библиотеки tkinter

SIDE = 26; SIZE = 14                # Размер поля в клетках, клетки в пикселях
colores = ['#aa9', '#0f0', '#ccd']  # Цвет поля, жизни, сетки
cell  = []                          # Клетки
playGround = [0]*SIDE**2            # Игровое поле, int

def doDraw(event):                  # Hbcjdfybt yf gjkt
    global playGround
    n = event.x//SIZE + event.y//SIZE*SIDE                  # Номер клетки
    playGround[n] =  int(not(playGround[n]))                # Инверсия состояния
    cnv.itemconfig(cell[n], fill=colores[playGround[n]])    # Инверсия цвета

cnv = Canvas(width=SIDE*SIZE, height=SIDE*SIZE)             # Canvas с именем cnv
cnv.pack()
cnv.bind('<Button-1>', doDraw)      # Рисование по клику мыши
for y in range(SIDE):               # Создаём поле
    for x in range(SIDE):
        cell.append(cnv.create_rectangle(x*SIZE, y*SIZE, (x+1)*SIZE, (y+1)*SIZE,
                    fill=colores[0], outline=colores[2], width=1))

mainloop()                          # Главный цикл программы

Лист. 2. Программа

from tkinter import *               # Импортируем все функции из библиотеки tkinter

SIDE = 26; SIZE = 14                # Размер поля в клетках, клетки в пикселях
colores = ['#aa9', '#0f0', '#ccd']  # Цвет поля, жизни, сетки
cell  = []                          # Клетки
playGround = [0]*SIDE**2            # Игровое поле, int
Birth = [3]                         # Правило рождения
Life = [2]                          # Правило жизни
fps = 100                           # 1/частоту обновления мсек.

def play():
    global playGround
    pgTmp = list(playGround)
    for i in range(SIDE**2):
        roomie  = pgTmp[(i+1)%SIDE + SIDE*(i//SIDE)]        # Соседи (x+y*SIDE)
        roomie += pgTmp[(i-1+SIDE)%SIDE + SIDE*(i//SIDE)]
        roomie += pgTmp[((i//SIDE+1)%SIDE)*SIDE + i%SIDE]   # y+1=(i//SIDE+1)%SIDE ; x=i%SIDE ; n=y*SIDE+x
        roomie += pgTmp[((i//SIDE+SIDE-1)%SIDE)*SIDE + i%SIDE]
        roomie += pgTmp[((i//SIDE+1)%SIDE)*SIDE + (i+1)%SIDE]
        roomie += pgTmp[((i//SIDE+1)%SIDE)*SIDE + (i-1+SIDE)%SIDE]
        roomie += pgTmp[((i//SIDE+SIDE-1)%SIDE)*SIDE + (i+1)%SIDE]
        roomie += pgTmp[((i//SIDE+SIDE-1)%SIDE)*SIDE + (i-1+SIDE)%SIDE]
        if playGround[i] != 0:
            if roomie not in Life:
                playGround[i] = 0
                cnv.itemconfig(cell[i], fill=colores[0])
        if playGround[i] == 0:
            if roomie in Birth:
                playGround[i] = 1
                cnv.itemconfig(cell[i], fill=colores[1])
    if var.get() == True:
        cnv.after(fps, play)

def doDraw(event):                  # Hbcjdfybt yf gjkt
    global playGround
    n = event.x//SIZE + event.y//SIZE*SIDE                  # Номер клетки
    playGround[n] =  int(not(playGround[n]))                # Инверсия состояния
    cnv.itemconfig(cell[n], fill=colores[playGround[n]])    # Инверсия цвета

cnv = Canvas(width=SIDE*SIZE, height=SIDE*SIZE)             # Canvas с именем cnv
cnv.pack()
cnv.bind('<Button-1>', doDraw)      # Рисование по клику мыши
for y in range(SIDE):               # Создаём поле
    for x in range(SIDE):
        cell.append(cnv.create_rectangle(x*SIZE, y*SIZE, (x+1)*SIZE, (y+1)*SIZE,
                    fill=colores[0], outline=colores[2], width=1))
frm = Frame()                       # Кнопки крпавления
frm.pack()
var = BooleanVar()
Radiobutton(frm, text='RUN', variable = var, value=True, command=play).pack(side=LEFT)
Radiobutton(frm, text='STOP', variable = var, value=False, command=play).pack(side=LEFT)
var.set(False)

mainloop()                          # Главный цикл программы

Лист. 3. Программа

#!/usr/bin/env python3
# -*- Mode: Python; coding: utf-8; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- 
#
# LinuxORfreeBSD.py
# Copyright (C) 2021 Aleksandr Diorditsa, see <https://adior.ru>
# I want to thank all my students for the inspiration they give me.
#
# LinuxORfreeBSD.py is free software: you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
# Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# LinuxORfreeBSD.py is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
# See the GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License along
# with this program.  If not, see <http://www.gnu.org/licenses/>.

from tkinter import *

SIDE = 26; SIZE = 14                                        # Размер поля в клетках, клетки в пикселях
playGround = [0]*SIDE**2                                    # Игровое поле, boolean
colores = ['#aa9', '#0f0', '#ccd']                          # Цвета
cell  = []                                                  # Клетки
Birth = [3]
Life = [2]
fps = 100

class btn():
    def __init__(self, frm, number, BirthLife):
        self.bili = BirthLife
        self.number = number
        Button(frm, text=str(number), command = self.setBL).pack(side=LEFT)
    def setBL(self):
        if self.number in self.bili:
            self.bili.remove(self.number)
        else:
            self.bili.append(self.number)
        tk.title('VI.RUS ' + ''.join(map(str, Birth)) + '/' + ''.join(map(str, Life)))

def play():
    global playGround
    pgTmp = list(playGround)
    for i in range(SIDE**2):
        roomie  = pgTmp[(i+1)%SIDE + SIDE*(i//SIDE)]        # Соседи
        roomie += pgTmp[(i-1+SIDE)%SIDE + SIDE*(i//SIDE)]
        roomie += pgTmp[((i//SIDE+1)%SIDE)*SIDE + i%SIDE]   # y+1=(i//SIDE+1)%SIDE ; x=i%SIDE ; n=y*SIDE+x
        roomie += pgTmp[((i//SIDE+SIDE-1)%SIDE)*SIDE + i%SIDE]
        roomie += pgTmp[((i//SIDE+1)%SIDE)*SIDE + (i+1)%SIDE]
        roomie += pgTmp[((i//SIDE+1)%SIDE)*SIDE + (i-1+SIDE)%SIDE]
        roomie += pgTmp[((i//SIDE+SIDE-1)%SIDE)*SIDE + (i+1)%SIDE]
        roomie += pgTmp[((i//SIDE+SIDE-1)%SIDE)*SIDE + (i-1+SIDE)%SIDE]
        if playGround[i] != 0:
            if roomie not in Life:
                playGround[i] = 0
                cnv.itemconfig(cell[i], fill=colores[0])
        if playGround[i] == 0:
            if roomie in Birth:
                playGround[i] = 1
                cnv.itemconfig(cell[i], fill=colores[1])
    if var.get() == True:
        cnv.after(fps, play)

def doDraw(event):
    global playGround
    n = event.x//SIZE + event.y//SIZE*SIDE
    playGround[n] = 0 if playGround[n] else 1
    for i in range(SIDE**2):
        cnv.itemconfig(cell[i], fill=colores[playGround[i]])

tk = Tk()                                                   # Создаём главное окно программы
tk.title('VI.RUS ' + ''.join(map(str, Birth)) + '/' + ''.join(map(str, Life)))                                          # Заголовок главного окна программы
frmTop = Frame()
frmTop.pack()
Label(frmTop, text='Birth>').pack(side=LEFT)
for i in range(1, 9): btn(frmTop, i, Birth)
Label(frmTop, text='<Birth').pack(side=LEFT)
frmTop2 = Frame()
frmTop2.pack()
Label(frmTop2, text='Life>').pack(side=LEFT)
for i in range(1, 9): btn(frmTop2, i, Life)
Label(frmTop2, text='<Life').pack(side=LEFT)

cnv = Canvas(width=SIDE*SIZE, height=SIDE*SIZE)             # Создаём объект класса Canvas с именем cnv
cnv.pack()
cnv.bind('<Button-1>', doDraw)
for y in range(SIDE):
    for x in range(SIDE):
        cell.append(cnv.create_rectangle(x*SIZE, y*SIZE, (x+1)*SIZE, (y+1)*SIZE,
                    fill=colores[0], outline=colores[2], width=1))

frm = Frame()
frm.pack()
var = BooleanVar()
Radiobutton(frm, text='RUN', variable = var, value=True, command=play).pack(side=LEFT)
Radiobutton(frm, text='STOP', variable = var, value=False, command=play).pack(side=LEFT)
var.set(False)

mainloop()                                                  # Главный цикл программы

Лист. 4. Программа

Рис. 2. Осцилляторы найденные Саймоном Нортоном в 1970 г.

Рис. 3.

Рис. 4.

Рис. 5.

Рис. 6.

Рис. 7.

Рис. 8.

Рис. 9.

Рис. 10.

Рис. 11.

Рис. 12.

Формулы для клеточных автоматов:

B3/S23 (клетка рождается, если у неё три соседа, и выживает, если у неё три или два соседа).

B3/S35 (клетка рождается, если у неё три соседа, и выживает, если у неё три или пять соседей).

Игра «Жизнь» Конвея — это клеточный автомат, частный случай Клеточных автоматов.

Клеточный автомат — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых окрестностью. К примеру, окрестность может быть определена как все ячейки на расстоянии не более 2 от текущей (окрестность фон Неймана ранга 2). Для работы клеточного автомата требуется задание начального состояния всех ячеек и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.

Википедия.

Применение клеточных автоматов:

Криптография
Моделирование физических процессов
Цифровая физика
Компьютерные процессоры
Нейронные сети.

Python