Игра Жизнь на SQL

Определения

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

Колония изменяется по следующим правилам:

• Если у клетки заняты соседями две или три смежных ячейки, то клетка “выживает” и переходит в следующее поколение, в противном случае она “умирает” от перенаселения или недостатка соседей.
• Если рядом с пустой ячейкой находятся ровно три клетки, то на месте этой ячейки появляется новая клетка.
• В процессе смены поколения “умирающие” клетки считаются принадлежащими колонии до определения всех новых клеток и клеток, переходящих в следующее поколение. Также и рождающиеся считаются принадлежащими следующему поколению и не оказывают влияние на количество соседей клеток текущего поколения.

Таблицы и представления

Колония описывается множеством пар координат клеток. Таблица cells хранит координаты клеток колонии и номер поколения, которому они принадлежат:

CREATE TABLE cells (
    x BIGINT,
    y BIGINT,
    gen BIGINT,
CONSTRAINT UQ_xy UNIQUE (x, y, gen)
);

Представление (VIEW), которое возвращает координаты клеток последнего поколения из таблицы cells:

CREATE VIEW LastGen AS 
    SELECT x,y,gen 
    FROM 
        cells 
    WHERE 
        gen = (SELECT max(gen) from cells);

Вспомогательная неизменяемая таблица относительных координат смежных ячеек:

CREATE TABLE dxdy (
    x BIGINT,
    y BIGINT,
    CONSTRAINT UQ_xy UNIQUE (x, y)
);

В таблице dxdy восемь записей: у каждой ячейки восемь смежных ей ячеек, которые отличаются на единицу по любой координате:

INSERT INTO dxdy (x,y) VALUES 
 ( 1, 1),
 ( 0, 1),
 (-1, 1),
 (-1, 0),
 (-1,-1),
 ( 0,-1),
 ( 1,-1),
 ( 1, 0);

Процедура

Процедура, вычисляющая следующее поколение и добавляющая координаты клеток нового поколения в таблицу cells.

На первом шаге определяется номер текущего поколения, который записывается в локальную переменную current_gen:

DECLARE current_gen BIGINT DEFAULT 0;
SELECT max(gen) from cells into current_gen;

Далее используется синтаксис INSERT INTO … SELECT для формирования множества координат клеток нового поколения при помощи двух запросов SELECT, результаты которых объединяются оператором UNION.

Первый SELECT выбирает из таблицы cells координаты клеток текущего поколения

C1.gen=current_gen and C2.gen=current_gen

и у которых смежные ячейки (C1.x+dxdy.x, C1.y+dxdy.y) заняты

C2.x = C1.x+dxdy.x and C2.y = C1.y+dxdy.y

двумя или тремя клетками из текущего поколения:

HAVING COUNT(*)=3 OR COUNT(*)=2

Второй SELECT выбирает координаты смежных ячеек колонии, у которых ровно три соседа. Смежные ячейки колонии – это множество незанятых смежных ячеек всех её клеток. Незанятые ячейки определяются при помощи левого соединения множества координат смежных ячеек (cells C1) с координатами клеток колонии (cells C2) при условии

(C2.x IS NULL OR C2.y IS NULL) 

Объявление процедуры:

DELIMITER $$;

CREATE PROCEDURE NextGen()  
BEGIN
DECLARE current_gen BIGINT DEFAULT 0;
SELECT max(gen) from cells into current_gen;
INSERT INTO cells (x,y,gen)
	SELECT 
		C1.x,C1.y,current_gen+1	as gn
	FROM 
		LastGen C1
	JOIN dxdy
	JOIN LastGen C2 ON C2.x = C1.x+dxdy.x and C2.y = C1.y+dxdy.y 
	GROUP BY 
		x,y,gn
	HAVING COUNT(*)=3 OR COUNT(*)=2
UNION
	SELECT 
		C1.x+dxdy.x as nearx,  
		C1.y+dxdy.y as neary,
		current_gen+1 as gn
	FROM 
		LastGen C1
	JOIN dxdy
	LEFT JOIN LastGen C2 ON C2.x = C1.x+dxdy.x and C2.y = C1.y+dxdy.y AND (C2.x IS NULL OR C2.y IS NULL)
	GROUP BY 
		nearx,neary,gn
	HAVING COUNT(*) = 3;
END $$

DELIMITER ;

Пример

Колония “Глайдер”, которая через 4 поколения смещает вниз и вправо на одну клетку:

INSERT INTO cells (x,y,gen) VALUES 
	( 1, 1, 1),
	( 2, 1, 1),
	( 3, 1, 1),
	( 3, 2, 1),
    ( 2, 3, 1),

Первое поколение:

select * from LastGen;

x|y|gen|
-|-|---|
1|1|  1|
2|1|  1|
2|3|  1|
3|1|  1|
3|2|  1|

Состояние колонии через четыре поколения:

CALL NextGen();
CALL NextGen();
CALL NextGen();
CALL NextGen();

select * from LastGen;

select * from LastGen;

x|y|gen|
-|-|---|
2|0|  5|
3|0|  5|
3|2|  5|
4|0|  5|
4|1|  5|

• Игра “Жизнь” на языке Python
• Игра “Жизнь” на языке MATLAB