Conway's Game of Life

Full Recipe

Recipe v2

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: 2
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 with Upload History (right-click the download button in the Exploration UI toolbar) to see the grid.
  You can create a new layout by running the generate-conways-layout.py 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:
  - name: gol-config-ingest
    source:
      type: File
      path: $config_file
      format:
        type: Json
    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
  - name: compute-wave
    pattern:
      type: Cypher
      mode: MULTIPLE_VALUES
      query: >-
        MATCH (ready)-[:ACTIVATES]->(cell)
        WHERE ready.computingCells = ready.totalCells AND ready.state = "computing"
        RETURN id(cell) AS cellId
    outputs:
      - name: compute-next-state
        resultEnrichment:
          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
          parameter: that
        destinations:
          - type: StandardOut

  # Wave 2: Apply computed state changes
  - name: apply-wave
    pattern:
      type: Cypher
      mode: MULTIPLE_VALUES
      query: >-
        MATCH (ready)-[:ACTIVATES]->(cell)
        WHERE ready.applyingCells = ready.totalCells AND ready.state = "applying"
        RETURN id(cell) AS cellId
    outputs:
      - name: apply-state-change
        resultEnrichment:
          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
          parameter: that
        destinations:
          - type: StandardOut

  # Wave coordination: Wave 1 complete -> Start Wave 2 (two-phase lock)
  - name: wave-1-to-2
    pattern:
      type: Cypher
      mode: MULTIPLE_VALUES
      query: >-
        MATCH (ready)
        WHERE ready.computingCells = 0 AND ready.applyingCells = 0 AND ready.state = "computing"
        RETURN id(ready) AS readyId
    outputs:
      - name: start-wave-2
        resultEnrichment:
          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
          parameter: that
        destinations:
          - type: StandardOut

  # Wave coordination: Wave 2 complete -> Start next generation Wave 1 (two-phase lock)
  - name: wave-2-to-next-gen
    pattern:
      type: Cypher
      mode: MULTIPLE_VALUES
      query: >-
        MATCH (ready)
        WHERE ready.applyingCells = 0 AND ready.computingCells = 0 AND ready.state = "applying"
        RETURN id(ready) AS readyId
    outputs:
      - name: start-next-generation
        resultEnrichment:
          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
          parameter: that
        destinations:
          - type: StandardOut

# 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: "● ("
  - predicate:
      propertyKeys: ["alive", "x", "y"]
      knownValues:
        alive: false
      dbLabel: Cell
    icon: ion-record
    color: "#CCCCCC"
    size: 15.0
    label:
      type: Property
      key: "x"
      prefix: "○ ("

quickQueries:
  - predicate:
      propertyKeys: []
      knownValues: {}
    quickQuery:
      name: Refresh
      querySuffix: RETURN n
      sort: NODE
  - predicate:
      propertyKeys: []
      knownValues: {}
    quickQuery:
      name: Local Properties
      querySuffix: RETURN id(n), properties(n)
      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
      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
      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. Each has a matching layout file, which loads the pattern's cells into the Exploration UI as a grid (see Step 2).

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

Download blinker-layout.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

Download glider-gun-layout.json

Explosion Pattern

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

Download explosion.json

Download explosion-layout.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 and its layout file (this walkthrough uses blinker.json and blinker-layout.json), then 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-2.2.1.jar -r conways-gol.yaml --recipe-value config_file=blinker.json
Graph is ready
Using 2 node appearances
Using 4 quick queries
Using 2 sample queries
Running Standing Query compute-wave
Running Standing Query apply-wave
Running Standing Query wave-1-to-2
Running Standing Query wave-2-to-next-gen
Running Ingest Stream gol-config-ingest
Status query URL is http://127.0.0.1:8080#MATCH%20(c:Cell)%0ARETURN%20c
gol-config-ingest status is terminated and ingested 1
Quine web server available at http://127.0.0.1:8080
Default API version: v2

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 Grid

To visualize the Game of Life properly, each cell must sit at its x,y coordinates in a grid. Each configuration comes with a matching layout file that holds every cell node and its position in the grid, and loading it puts all the cells on the canvas in grid formation.

1. Open the Exploration UI at http://localhost:8080/explorer.
2. Right-click the download button in the toolbar (its tooltip reads "Download history log") and choose Upload History.
3. Choose the layout file that matches your configuration (e.g., blinker-layout.json for the blinker configuration).
4. Click OK when the browser asks you to confirm "Uploading this history will erase your existing one."

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

Step 3: 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 4: 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 5: Stop the Game

To pause the evolution, right-click any cell and select the ⏸️ STOP Game quick query. If the cells keep changing, run ⏸️ STOP Game again.

View Configuration Details

You can check the current game configuration and statistics at any time with the 📊 Show Game Configuration sample query. After choosing it, press Ctrl+Shift+Enter (or hold Shift while clicking 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: POST /api/v2/system:shutdown:

   curl -X "POST" "http://127.0.0.1:8080/api/v2/system:shutdown"
   

3. Restart Quine with a different configuration file:

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

4. Load the cells with Upload History and the corresponding layout file (glider-gun-layout.json), as in Step 2. The 40x15 grid is larger than the default view, so zoom out to see the whole grid.

5. Activate the bookmarklet again
6. 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 loads every cell node onto the canvas and positions it properly in a grid formation.

Download generate-conways-layout.py

To use the layout generator:

1. Start Quine with your custom configuration
2. Run the Python script with your configuration file: python3 generate-conways-layout.py my-pattern.json (add --host if Quine is not at localhost:8080)
3. The script writes my-pattern-layout.json, which holds every cell node and its grid coordinates
4. Load this layout file in the Exploration UI with Upload History, as in Step 2

Run the script before starting the game, because the layout file records each cell's state at the moment it runs, and the bookmarklet only refreshes the cells that change.

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.