The SQL of the Game – Conway’s Game of Life

Joe Celko recently published a challenge to implement Conway’s Game of Life in SQL. At the start of this game, each cell of a 10×10 grid is either occupied or unoccupied by an imaginary creature that Celko calls a Merkle. Each turn, Merkles that have fewer than two neighbors die of loneliness while Merkles that have more than three neighbors die of overcrowding. Unoccupied cells that have Merkles in exactly three neighboring cells grow a Merkle. This game is a form of cellular automaton.

One of the main obstacles to implementing a model like this in SQL is that the new state of each cell depends on the state of the adjoining cells. One common method of solving this problem is to join the table representing the cells to itself eight times, as seen in the first comment to the Celko article. However, eight self-joins can get very costly. The solution I outline below solves the  problem with a single join.

My solution depends on three premises: (1) we know the size of the grid; (2) we can represent each square in the grid by a single address (instead of an (x,y) coordinate pair), and (3) given the first two premises, we can derive the addresses of all neighboring squares for any given grid square by mathematical operations on its address.

Of course, we know the grid size for this Game of Life exercise: 10X10. We can represent the squares in the grids by numbering them sequentially starting in the lower left corner (it really doesn’t matter which corner is number 1 – I do it this way because it reflects the standard Cartesian coordinate system with the origin (0,0) at lower left):

Grid

With a little study of this grid, the mathematical relationships between a cell address and the addresses of its neighbors become clear. For most cells, the addresses of the eight neighboring cells can be established by the following formulae (where c = cell address), based on the known y dimension of the grid (10):

c + 1 (the cell to the "north")
c + 10 + 1 (the cell to the "northeast")
c + 10 (the cell to the "east")
c + 10 - 1 (the cell to the "southeast")
c - 1 (the cell to the "south")
c - 10 - 1 (the cell to the "southwest")
c - 10 (the cell to the "west")
c - 10 + 1 (the cell to the "northwest")

Some special conditions have to be applied for cells along the “north” and “south” edges of the grid, though, because cells on the north edge won’t have neighbors to the north (for example, cell 10 does not have cell 11 as a neighbor) and, likewise, cells on the south edge won’t have neighbors to the south. Cells on the north edge of the grid share a distinct characteristic – dividing their addresses by 10 leaves a remainder of 0. Cells that meet this condition will have no northern neighbors. Likewise, cells on the south edge of the grid share a distinct characteristic – dividing their addresses by 10 leaves a remainder of 1. Cells that meet this condition will have no southern neighbors. Similar conditions could be applied to the cells on the “east” and “west” edges of the grid (using whole number portion of the quotient of the cell address divided by 10, instead of the remainder, to identify the affected cells), but since the grid numbers for their eastern and western neighbors don’t actually exist,  this isn’t necessary (the fact that the formula yields the nonexistent cell -6 as the western neighbor of cell 6 will not affect the outcome). The code below shows how to implement these conditions.

Now that we can identify the addresses of neighboring cells, we can join each cell to its neighbors in one self-join, and, if we represent the status of each cell as a 1 for occupied and a 0 for unoccupied, determine the number of neighbors for each cell with the SUM aggregate function. From this result set, we can then determine how to update each cell to represent the outcome of a turn. The following code shows how to do this. As a little bonus, the stored procedure includes a bit of code that displays the starting state and the result of each turn in a grid with (x,y) coordinates – it uses the same principles to identify which row and column a cell belongs to based on its address as the code that identifies the cells on the northern and southern edges of the grid.

NOTES ABOUT THIS CODE: This code uses a tally table, which is simply a table of integers, and a function to generate random numbers within defined bounds developed by Jeff Moden to create and populate the table representing the 10×10 grid. This code also uses T-SQL syntax for declaring the temporary table since I have easiest access to a Microsoft SQL Server instance for testing the code; I tried to use ANSI standard SQL for all other purposes.


CREATE PROCEDURE dbo.GameOfLife @nRounds int

AS

BEGIN

--Create and populate 10x10 grid table:
CREATE TABLE #Merkles (GridNbr smallint, Merkle smallint)

INSERT INTO #Merkles

SELECT t.N, r.randomNumber

FROM DNA.dbo.tally t

OUTER APPLY dbo.RandomNumberSeries(0, 1, 1) r

WHERE t.N BETWEEN 1 AND 100

-- Display starting state:
SELECT m.y
,SUM(CASE WHEN m.x = 0 THEN m.Merkle ELSE 0 END) AS [1]
,SUM(CASE WHEN m.x = 1 THEN m.Merkle ELSE 0 END) AS [2]
,SUM(CASE WHEN m.x = 2 THEN m.Merkle ELSE 0 END) AS [3]
,SUM(CASE WHEN m.x = 3 THEN m.Merkle ELSE 0 END) AS [4]
,SUM(CASE WHEN m.x = 4 THEN m.Merkle ELSE 0 END) AS [5]
,SUM(CASE WHEN m.x = 5 THEN m.Merkle ELSE 0 END) AS [6]
,SUM(CASE WHEN m.x = 6 THEN m.Merkle ELSE 0 END) AS [7]
,SUM(CASE WHEN m.x = 7 THEN m.Merkle ELSE 0 END) AS [8]
,SUM(CASE WHEN m.x = 8 THEN m.Merkle ELSE 0 END) AS [9]
,SUM(CASE WHEN m.x = 9 THEN m.Merkle ELSE 0 END) AS [10]

FROM (SELECT *, ((GridNbr - 1) % 10) + 1 as y, (GridNbr - 1) / 10 AS x FROM #Merkles) m

GROUP BY m.y

ORDER BY m.y DESC

--Loop through @nRounds:
DECLARE @Counter smallint = 1

WHILE @Counter <= @nRounds

BEGIN

UPDATE z

SET z.Merkle = CASE WHEN z.Merkle = 1 AND (zx.nNeighbors 3) THEN 0
WHEN z.Merkle = 0 AND zx.nNeighbors = 3 THEN 1
ELSE z.Merkle
END

FROM #Merkles z

LEFT OUTER JOIN (

SELECT a.GridNbr, a.Merkle, ((a.GridNbr - 1) % 10) + 1 as y, ((a.GridNbr - 1) / 10) + 1 AS x, SUM(a.AdjoiningMerkle) AS nNeighbors

FROM (

SELECT m.*, mx.GridNbr AS AdjoiningGridNbr, mx.Merkle AS AdjoiningMerkle

FROM #Merkles m

LEFT OUTER JOIN #Merkles mx
ON mx.GridNbr IN (CASE WHEN m.GridNbr % 10 > 0 THEN m.GridNbr + 1 ELSE NULL END -- N
,CASE WHEN m.GridNbr % 10 > 0 THEN m.GridNbr + 11 ELSE NULL END -- NE
,m.GridNbr + 10 -- E
,CASE WHEN m.GridNbr % 10 1 THEN m.GridNbr + 9 ELSE NULL END -- SE
,CASE WHEN m.GridNbr % 10 1 THEN m.GridNbr - 1 ELSE NULL END -- S
,CASE WHEN m.GridNbr % 10 1 THEN m.GridNbr - 11 ELSE NULL END -- SW
,m.GridNbr - 10 -- W
,CASE WHEN m.GridNbr % 10 > 0 THEN m.GridNbr - 9 ELSE NULL END -- NW
)

) a

GROUP BY a.GridNbr, a.Merkle, ((a.GridNbr - 1) % 10) + 1, ((a.GridNbr - 1) / 10 ) + 1

) zx

ON z.GridNbr = zx.GridNbr

-- Display resulting state:
SELECT m.y
,SUM(CASE WHEN m.x = 0 THEN m.Merkle ELSE 0 END) AS [1]
,SUM(CASE WHEN m.x = 1 THEN m.Merkle ELSE 0 END) AS [2]
,SUM(CASE WHEN m.x = 2 THEN m.Merkle ELSE 0 END) AS [3]
,SUM(CASE WHEN m.x = 3 THEN m.Merkle ELSE 0 END) AS [4]
,SUM(CASE WHEN m.x = 4 THEN m.Merkle ELSE 0 END) AS [5]
,SUM(CASE WHEN m.x = 5 THEN m.Merkle ELSE 0 END) AS [6]
,SUM(CASE WHEN m.x = 6 THEN m.Merkle ELSE 0 END) AS [7]
,SUM(CASE WHEN m.x = 7 THEN m.Merkle ELSE 0 END) AS [8]
,SUM(CASE WHEN m.x = 8 THEN m.Merkle ELSE 0 END) AS [9]
,SUM(CASE WHEN m.x = 9 THEN m.Merkle ELSE 0 END) AS [10]

FROM (SELECT *, ((GridNbr - 1) % 10) + 1 as y, (GridNbr - 1) / 10 AS x FROM #Merkles) m

GROUP BY m.y

ORDER BY m.y DESC

SET @Counter = @Counter + 1

END

DROP TABLE #Merkles

END

Advertisements

One comment

  1. Did you lose characters in your code? m.NGridNbr % 10 1 ?? S/b % 10+1 etc.? I appreciate your effort and enjoy reading your comments on SSC.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: