Conway's Game of Life

Full Recipe

Shared by: Matthew Cullum

A complete implementation of Conway's Game of Life using Quine's standing queries to create a real-time cellular automaton. This recipe demonstrates that Quine is Turing complete by leveraging standing query recursion to evolve cell states across generations according to Conway's famous rules.

Conway's Game of Life Recipe

version: 1
title: Conway's Game of Life
contributor: Matthew Cullum https://github.com/brackishman
summary: Conway's Game of Life in Quine
description: |-
  This recipe implements a generic Conway's Game of Life using standing queries for 
  real-time cellular automaton evolution. The grid size, initial patterns, and 
  configuration are loaded from a JSON file specified at runtime.

  Each cell evaluates its neighbors and changes state only when Conway's rules dictate 
  a change, triggering cascading updates throughout the grid.

  Conway's Rules:
  1. Live cell with 2-3 live neighbors survives
  2. Dead cell with exactly 3 live neighbors becomes alive  
  3. All other cells die or stay dead

  Usage: Specify JSON config file with --recipe-value config_file=path/to/config.json
  The config file schema is as follows:
  {
    "name": "My Game of Life",
    "description": "A description of this setup",
    "gridWidth": 10,
    "gridHeight": 10,
    "initialPattern": [
      {"x": 1, "y": 0, "alive": true},
      {"x": 2, "y": 1, "alive": true},
      {"x": 0, "y": 2, "alive": true},
      {"x": 1, "y": 2, "alive": true},
      {"x": 2, "y": 2, "alive": true}
    ]
  }

  In Quine you can view all cell nodes with the following query: MATCH (c:Cell) RETURN c

  Once Quine is running with this recipe, load the layout json from the UI to see the grid.
  You can create a new layout by running the generate-conways-layout.js script while Quine is running.

  Once the cell nodes are layed out, make sure to enable the bookmarklet. The javascript for the bookmarklet is in conways-gol-bookmarklet.js

  Start the game with the "▶️ START Game" quick query on any cell node, and pause it with the "⏸️ STOP Game" quick query.

# Set up grid dynamically from JSON configuration file
ingestStreams:
  - type: FileIngest
    path: $config_file
    format:
      type: CypherJson
      query: |-
        // Extract configuration from JSON and calculate totalCells
        WITH $that.gridWidth AS gridWidth,
             $that.gridHeight AS gridHeight,
             $that.gridWidth * $that.gridHeight AS totalCells,
             $that.name AS name,
             $that.description AS description,
             $that.initialPattern AS initialPattern

        // Create all grid cells (totalCells = gridWidth * gridHeight)
        UNWIND range(0, totalCells - 1) AS cellIndex
        WITH gridWidth, gridHeight, totalCells, name, description, initialPattern,
             cellIndex % gridWidth AS x,
             cellIndex / gridWidth AS y

        // Determine if this cell should be alive based on initialPattern
        WITH x, y, gridWidth, gridHeight, totalCells, name, description,
             CASE 
               WHEN any(pattern IN initialPattern WHERE pattern.x = x AND pattern.y = y AND pattern.alive = true) THEN true
               ELSE false 
             END AS alive

        // Create/update the specific cell
        MATCH (cell)
        WHERE id(cell) = idFrom("cell", x, y)
        SET cell.x = x,
            cell.y = y,
            cell.alive = alive,
            cell.generation = 0,
            cell.state = "applied",
            cell: Cell

        // Create neighbor relationships within grid bounds
        WITH cell, x, y, gridWidth, gridHeight, totalCells, name, description
        UNWIND [
          [x-1, y-1], [x, y-1], [x+1, y-1],
          [x-1, y],             [x+1, y],
          [x-1, y+1], [x, y+1], [x+1, y+1]
        ] AS neighbor
        WITH cell, neighbor[0] AS nx, neighbor[1] AS ny, gridWidth, gridHeight, totalCells, name, description
        WHERE nx >= 0 AND nx < gridWidth AND ny >= 0 AND ny < gridHeight
        MATCH (neighborCell)
        WHERE id(neighborCell) = idFrom("cell", nx, ny)
        CREATE (cell)-[:NEIGHBOR]->(neighborCell)

        // Create/update ready node with configuration and connect to this cell
        WITH cell, gridWidth, gridHeight, totalCells, name, description
        MATCH (ready)
        WHERE id(ready) = idFrom("ready")
        SET ready.computingCells = 0,
            ready.applyingCells = 0,
            ready.generation = 0,
            ready.state = "stopped",
            ready.totalCells = totalCells,
            ready.gridWidth = gridWidth,
            ready.gridHeight = gridHeight,
            ready.name = name,
            ready.description = description
        CREATE (ready)-[:ACTIVATES]->(cell)

# Standing queries for two-wave Conway's Game of Life evolution (fully dynamic)
standingQueries:
  # Wave 1: Compute next state for all cells
  - pattern:
      type: Cypher
      mode: MultipleValues
      query: >-
        MATCH (ready)-[:ACTIVATES]->(cell)
        WHERE ready.computingCells = ready.totalCells AND ready.state = "computing"
        RETURN id(cell) AS cellId
    outputs:
      compute-next-state:
        type: CypherQuery
        query: |-
          MATCH (cell)-[:NEIGHBOR]->(neighbor)
          WHERE id(cell) = $that.data.cellId
          WITH cell, count(CASE WHEN neighbor.alive = true THEN 1 END) AS liveNeighbors
          WITH cell, liveNeighbors, CASE
            WHEN cell.alive = false AND liveNeighbors = 3 THEN true
            WHEN cell.alive = true AND (liveNeighbors = 2 OR liveNeighbors = 3) THEN true
            ELSE false
          END AS nextAlive
          SET cell.nextAlive = nextAlive,
              cell.state = "calculated"
          WITH cell
          MATCH (ready)-[:ACTIVATES]->(cell)
          WHERE id(cell) = $that.data.cellId
          CALL int.add(ready, "computingCells", -1) YIELD result
          RETURN cell.x AS x, cell.y AS y, cell.nextAlive AS nextAlive, "calculated" AS cellState, result AS remainingCells
        andThen:
          type: PrintToStandardOut

  # Wave 2: Apply computed state changes
  - pattern:
      type: Cypher
      mode: MultipleValues
      query: >-
        MATCH (ready)-[:ACTIVATES]->(cell)
        WHERE ready.applyingCells = ready.totalCells AND ready.state = "applying"
        RETURN id(cell) AS cellId
    outputs:
      apply-state-change:
        type: CypherQuery
        query: |-
          MATCH (cell)
          WHERE id(cell) = $that.data.cellId
          WITH cell, cell.alive AS oldAlive, cell.nextAlive AS newAlive
          SET cell.alive = newAlive,
              cell.updated = (oldAlive <> newAlive),
              cell.state = "applied"
          WITH cell
          MATCH (ready)-[:ACTIVATES]->(cell)
          WHERE id(cell) = $that.data.cellId
          CALL int.add(ready, "applyingCells", -1) YIELD result
          RETURN cell.x AS x, cell.y AS y, cell.alive AS alive, "applied" AS cellState, result AS remainingCells
        andThen:
          type: PrintToStandardOut

  # Wave coordination: Wave 1 complete -> Start Wave 2 (two-phase lock)
  - pattern:
      type: Cypher
      mode: MultipleValues
      query: >-
        MATCH (ready)
        WHERE ready.computingCells = 0 AND ready.applyingCells = 0 AND ready.state = "computing"
        RETURN id(ready) AS readyId
    outputs:
      start-wave-2:
        type: CypherQuery
        query: |-
          MATCH (ready)-[:ACTIVATES]->(cell)
          WHERE id(ready) = $that.data.readyId
          WITH ready, ready.totalCells AS TOTAL_CELLS, count(CASE WHEN cell.state = "calculated" THEN 1 END) AS calculatedCells
          WHERE calculatedCells = TOTAL_CELLS
          SET ready.applyingCells = TOTAL_CELLS,
              ready.state = "applying"
          RETURN "Starting Wave 2" AS message, TOTAL_CELLS AS cellCount, calculatedCells AS verifiedCells
        andThen:
          type: PrintToStandardOut

  # Wave coordination: Wave 2 complete -> Start next generation Wave 1 (two-phase lock)
  - pattern:
      type: Cypher
      mode: MultipleValues
      query: >-
        MATCH (ready)
        WHERE ready.applyingCells = 0 AND ready.computingCells = 0 AND ready.state = "applying"
        RETURN id(ready) AS readyId
    outputs:
      start-next-generation:
        type: CypherQuery
        query: |-
          MATCH (ready)-[:ACTIVATES]->(cell)
          WHERE id(ready) = $that.data.readyId
          WITH ready, ready.totalCells AS TOTAL_CELLS, count(CASE WHEN cell.state = "applied" THEN 1 END) AS appliedCells
          WHERE appliedCells = TOTAL_CELLS
          CALL int.add(ready, "generation", 1) YIELD result
          SET ready.computingCells = TOTAL_CELLS,
              ready.state = "computing"
          RETURN "Starting Generation" AS message, result AS generation, TOTAL_CELLS AS cellCount, appliedCells AS verifiedCells
        andThen:
          type: PrintToStandardOut

# UI Configuration - works with any grid size
nodeAppearances:
  - predicate:
      propertyKeys: ["alive", "x", "y"]
      knownValues: 
        alive: true
      dbLabel: Cell
    icon: ion-record
    color: "#FF4500"
    size: 50.0
    label:
      type: Property
      key: "x"
      prefix: "● ("
      suffix: ",{y})"
  - predicate:
      propertyKeys: ["alive", "x", "y"] 
      knownValues:
        alive: false
      dbLabel: Cell
    icon: ion-record
    color: "#CCCCCC"
    size: 15.0
    label:
      type: Property
      key: "x"
      prefix: "○ ("
      suffix: ",{y})"

quickQueries:
  - predicate:
      propertyKeys: []
      knownValues: {}
    quickQuery:
      name: Refresh
      querySuffix: RETURN n
      queryLanguage: Cypher
      sort: Node
  - predicate:
      propertyKeys: []
      knownValues: {}
    quickQuery:
      name: Local Properties
      querySuffix: RETURN id(n), properties(n)
      queryLanguage: Cypher
      sort: Text
  - predicate:
      propertyKeys: ["x", "y"]
      knownValues: {}
      dbLabel: Cell
    quickQuery:
      name: "▶️ START Game"
      querySuffix: |-
        MATCH (ready) WHERE id(ready) = idFrom("ready")
        SET ready.computingCells = ready.totalCells, ready.state = "computing"
        RETURN n
      queryLanguage: Cypher
      sort: Node
  - predicate:
      propertyKeys: ["x", "y"]
      knownValues: {}
      dbLabel: Cell
    quickQuery:
      name: "⏸️ STOP Game"
      querySuffix: |-
        MATCH (ready) WHERE id(ready) = idFrom("ready")
        SET ready.computingCells = 0, ready.applyingCells = 0, ready.state = "stopped"
        RETURN n
      queryLanguage: Cypher
      sort: Node

sampleQueries:
  - name: "● Show All Cells"
    query: |-
      MATCH (c:Cell) RETURN c
  - name: "📊 Show Game Configuration"
    query: |-
      MATCH (ready) WHERE id(ready) = idFrom("ready")
      MATCH (c:Cell)
      RETURN
        ready.name AS setup,
        ready.description AS description,
        ready.gridWidth AS width,
        ready.gridHeight AS height,
        ready.totalCells AS totalCells,
        count(CASE WHEN c.alive = true THEN 1 END) AS liveCells,
        ready.generation AS currentGeneration

statusQuery:
  cypherQuery: |-
    MATCH (c:Cell)
    RETURN c

Download Recipe

Scenario

Conway's Game of Life is a classic cellular automaton invented by mathematician John Conway in 1970. Despite its simple rules, it can produce remarkably complex patterns and behaviors. This recipe implements the complete Game of Life in Quine, where each cell is a node in the graph that evaluates its neighbors and updates its state according to Conway's rules:

1. A live cell with 2-3 live neighbors survives
2. A dead cell with exactly 3 live neighbors becomes alive
3. All other cells die or stay dead

The implementation uses a two-wave standing query pattern to compute and apply state changes across all cells simultaneously, demonstrating Quine's capability for recursive, real-time graph computation.

Sample Configurations

This recipe requires a configuration file that defines the grid size and initial pattern of alive cells. Each configuration is a JSON file specifying the grid dimensions and which cells start alive:

{
  "name": "Small Conway's Game - Blinker Pattern",
  "description": "7x7 grid with a simple blinker pattern in the center",
  "gridWidth": 7,
  "gridHeight": 7,
  "initialPattern": [
    {"x": 3, "y": 2, "alive": true},
    {"x": 3, "y": 3, "alive": true},
    {"x": 3, "y": 4, "alive": true}
  ]
}

Three pre-configured patterns are included with the recipe:

Blinker Pattern (Recommended for first run)

A simple 7x7 grid featuring a "blinker", a pattern that oscillates between horizontal and vertical orientations every generation. This is perfect for understanding the basic mechanics.

Download blinker.json

Gosper Glider Gun

The famous 40x15 grid containing the original Gosper Glider Gun discovered in 1970. This pattern produces new gliders every 30 generations, demonstrating emergent complexity from simple rules.

Download glider-gun.json

Explosion Pattern

A more chaotic initial configuration that creates dynamic, unpredictable evolution across the grid.

Download explosion.json

How it Works

This recipe demonstrates Quine's Turing completeness through recursive standing queries that continuously evaluate and evolve the cellular automaton.

Graph Structure

The recipe creates a graph where:

• Each cell is represented as a node with properties: x, y, alive, generation, and state
• Cells are connected via [:NEIGHBOR] relationships to their 8 adjacent cells
• A central ready node coordinates the computation waves and tracks the current generation

Two-Wave Standing Query Pattern

The recipe uses a sophisticated two-phase approach to ensure all cells update simultaneously:

Wave 1: Compute Next State

Standing queries detect when all cells are ready to compute their next state. Each cell:

1. Counts its live neighbors
2. Applies Conway's rules to determine if it should be alive in the next generation
3. Stores the result in nextAlive without changing its current state

Wave 2: Apply State Changes

Once all cells have computed their next state, a second wave of standing queries:

1. Updates each cell's alive property to the computed nextAlive value
2. Marks cells that changed as updated
3. Increments the generation counter

Wave Coordination

Standing queries monitor the ready node to coordinate the waves:

• When Wave 1 completes → Start Wave 2
• When Wave 2 completes → Start next generation's Wave 1

This recursive pattern continues indefinitely, evolving the grid through successive generations. The standing queries act as the "rules engine" that recursively applies Conway's rules, demonstrating that Quine's standing query mechanism is Turing complete.

Visual Configuration

The recipe includes node appearances that automatically style cells:

• Live cells: Large orange circles (●)
• Dead cells: Small gray circles (○)

Prerequisites: Install the Bookmarklet

Before running the recipe, you need to install a browser bookmarklet that enables visualization of the Game of Life animation. The bookmarklet performs two critical functions:

1. Enables unlimited node rendering by automatically bypassing the browser's node limit prompts
2. Monitors generation updates by connecting to Quine's standing query WebSocket and automatically refreshing the view to show updated cells

Without the bookmarklet, you would need to manually approve rendering hundreds of nodes and manually refresh the query after each generation, making the animation impossible to watch in real-time.

Installation Steps

1. Download the bookmarklet JavaScript file:

   Download conways-gol-bookmarklet.js

2. Open the downloaded file in a text editor and copy the entire JavaScript code

3. Create a new bookmark in your browser (usually Ctrl+D or Cmd+D)
4. Edit the bookmark and paste the JavaScript code as the bookmark URL
5. Name the bookmark "Quine GoL Monitor" (or any name you prefer)

Once Quine is running and you have loaded the cell nodes in the Exploration UI, click the bookmarklet in your browser's bookmark bar. You should see an alert confirming "Now monitoring Conway's Game of Life generations with unlimited node rendering..."

Bookmarklet Required

The bookmarklet must be activated before starting the game, or you will not see the animation. If you forget to activate it, simply click the bookmarklet and restart the game.

Running the Recipe

Step 1: Start Quine with the Recipe

Download one of the sample configurations (we'll use blinker.json for this walkthrough) and start Quine. Make sure the configuration file is in the same directory as your Quine JAR file, or provide the correct relative path:

❯ java -jar quine-1.9.3.jar -r conways-gol.yaml --recipe-value config_file=blinker.json
Graph is ready
Running Recipe: Conway's Game of Life
Using 2 node appearances
Using 2 quick queries
Using 1 sample query
Running Standing Query STANDING-1
Running Standing Query STANDING-2
Running Standing Query STANDING-3
Running Standing Query STANDING-4
Quine web server available at http://localhost:8080

Note

The configuration file path is relative to where you run the java command. If you organize your files in subdirectories, adjust the path accordingly (e.g., config_file=configs/blinker.json).

Step 2: Load the Cell Nodes

Open your browser to http://localhost:8080 and click the sample query ● Show All Cells to load all cell nodes into the Exploration UI.

You should see all cells in the grid displayed as small gray circles (all dead initially) or a mix of orange (alive) and gray (dead) circles depending on your initial pattern.

Step 3: Load the Grid Layout

The cell nodes are currently displayed in a random arrangement. To visualize the Game of Life properly, you need to load a layout file that positions each cell at its correct x,y coordinates in a grid formation. Each configuration comes with a matching layout file that contains the precise coordinates for every cell node.

1. In the Exploration UI, click the layout dropdown menu (top right of the graph view)
2. Select "Load Layout from File"
3. Choose the corresponding layout file that matches your configuration (e.g., blinker-layout.json for the blinker configuration)

The cells will now be arranged in a proper grid formation, with each cell positioned at its x,y coordinate. Live cells will appear as large orange circles and dead cells as small gray circles.

Step 4: Activate the Bookmarklet

Click the bookmarklet you installed earlier in your browser's bookmark bar. You should see an alert confirming "Now monitoring Conway's Game of Life generations with unlimited node rendering..."

The bookmarklet is now connected to Quine and ready to automatically refresh the view as cells change.

Step 5: Start the Game

Right-click on any cell node and select the ▶️ START Game quick query.

The game will immediately begin evolving! You'll see:

• Cells changing color as they become alive or dead
• The generation counter incrementing rapidly
• Patterns evolving according to Conway's rules

For the blinker pattern, you'll observe the three cells oscillating between horizontal and vertical orientations.

Step 6: Stop the Game

To pause the evolution, right-click any cell and select the ⏸️ STOP Game quick query.

View Configuration Details

You can check the current game configuration and statistics at any time with the 📊 Show Game Configuration sample query. Hold Shift while clicking the sample query to view the results as tabular data rather than updating the exploration canvas.

MATCH (ready) WHERE id(ready) = idFrom("ready")
MATCH (c:Cell)
RETURN
  ready.name AS setup,
  ready.description AS description,
  ready.gridWidth AS width,
  ready.gridHeight AS height,
  ready.totalCells AS totalCells,
  count(CASE WHEN c.alive = true THEN 1 END) AS liveCells,
  ready.generation AS currentGeneration

This displays the grid size, total cells, live cell count, and current generation as a table.

Trying Other Patterns

To run different Game of Life patterns:

1. Stop the current game with the ⏸️ STOP Game quick query

2. Shut down Quine by either typing Ctrl+C in the terminal window or issuing a graceful shutdown:

   curl -X "POST" "http://127.0.0.1:8080/api/v1/admin/shutdown"
   

3. Restart Quine with a different configuration file:

❯ java -jar quine-1.9.3.jar -r conways-gol.yaml --recipe-value config_file=glider-gun.json

1. Load the cells using the ● Show All Cells sample query
2. Apply the corresponding layout file (glider-gun-layout.json)
3. Activate the bookmarklet again
4. Start the game with the ▶️ START Game quick query

The Gosper Glider Gun is particularly fascinating to watch as it continuously creates gliders that move across the grid.

Performance Considerations

For larger grids (50x50 or more), you may notice the visualization slowing down. This is not a limitation of Quine's computation - the standing queries continue to process generations at high speed. The performance bottleneck is primarily the browser UI continuously querying and rendering hundreds of nodes in real-time.

The Quine graph continues to evolve rapidly even when the UI struggles to keep up with the visualization. You can verify this by checking the generation count, which will continue incrementing quickly regardless of grid size.

Performance Tip

For very large grids, consider periodically stopping the game to examine the current state rather than trying to watch continuous animation.

Creating Custom Patterns

Advanced users can create their own Game of Life configurations and layouts:

Custom Configuration

Create a JSON file following this schema:

{
  "name": "My Custom Pattern",
  "description": "Description of your pattern",
  "gridWidth": 20,
  "gridHeight": 20,
  "initialPattern": [
    {"x": 10, "y": 10, "alive": true},
    {"x": 11, "y": 10, "alive": true}
  ]
}

Generating Layout Files

The included Python script can generate layout JSON files for your custom configurations. This tool queries a running Quine instance to discover all cell nodes and their x,y coordinates, then generates a layout file that positions each node properly in a grid formation.

Download generate-conways-layout.py

To use the layout generator:

1. Start Quine with your custom configuration
2. Load all cells into the Exploration UI using the ● Show All Cells sample query
3. Run the Python script: python generate-conways-layout.py
4. The script generates a layout JSON file mapping each cell to its grid coordinates
5. Load this layout file in the Exploration UI

This tool is useful when creating new patterns, as it automatically calculates proper spacing and positioning for any grid size.

Summary

This recipe demonstrates a fundamental computer science concept - Turing completeness - through an elegant implementation of Conway's Game of Life. By using standing queries that recursively evaluate and update cell states, we prove that Quine can perform arbitrary computation. The two-wave pattern ensures synchronized updates across the entire grid, while the recursive nature of the standing queries drives the continuous evolution of the cellular automaton.

The Game of Life is a perfect demonstration of emergent complexity from simple rules, and implementing it in Quine showcases the power of recursive graph computation.

Turing Completeness

The ability to implement Conway's Game of Life demonstrates that Quine's standing query system is Turing complete. Since Game of Life itself is Turing complete, and we've implemented it entirely through standing queries, this proves that standing queries can perform any computable function.