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

Пример реализации алгоритма игры “Жизнь” на языке 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|


© 2020. All rights reserved.

Powered by Hydejack v9.0.3