# Conway's Game of Life with Graphs

Posted on 2023-04-05
Tags: scala, open source, personal project, graphs

A friend of mine mentioned Conway’s Game of Life in a group chat today, so I ended up thinking, most people implement this with arrays, can we do it in a graph?

I just wrote the introduction post for Hedgehogs, so let’s give it a go:

## Domain

The game is played on a grid, each cell is either alive or dead.

On each time step, the following is performed:

• Any live cell with two or three live neighbours survives
• Any dead cell with three live neighbours becomes alive
• All other cells die

## Domain Modelling

We can just model the alive status as a `Boolean`, and our grid as `(Int, Int)` tuples.

We don’t need to care about weights here, so every edge can have weight 1 to keep things simple.

I’ll start off with a 5x5 grid:

``````import net.andimiller.hedgehogs._

// use a starting pattern, this is a blinker, a 2 phase animation from the game
val initialPattern = Set((2, 1), (2, 2), (2, 3))
val nodes = for {
x <- 0 to 4
y <- 0 to 4
} yield Node((x, y), initialPattern.contains((x,y)))``````

And we’d like them to connect to all adjacent cells, including diagonally, so we need some edges:

``````val validRange = (0 to 4).toSet
val edges = for {
x <- 0 to 4
y <- 0 to 4
tx <- x-1 to x+1
ty <- y-1 to y+1
if ((x,y) != (tx, ty)) // don't connect to itself
if (validRange(tx))    // stay in the grid
if (validRange(ty))
} yield Edge((x,y), (tx, ty),  weight = 1)``````

We can combine these into our graph:

``````type LifeGraph = Graph[(Int, Int), Boolean, Int]
val graph: LifeGraph = Graph.fromIterables(nodes, edges, bidirectional = true)
.getOrElse(throw new Exception("invalid graph"))``````

And we’d like some way to render out our grid, so let’s do some quick string creation:

``````def render(nodes: Map[(Int, Int), Boolean]): String = nodes.toList
.sortBy(_._1)
.groupBy(_._1._2)
.toList
.sortBy(_._1)
.map { case (_, cells) =>
cells.map(_._2).map(alive => if (alive) "#" else " ").mkString
}
.mkString("\n")

render(graph.nodes)
// res0: String = """
//   #
//   #
//   #
//      """``````

## The Algorithm

Okay, I listed the 3 steps we need to perform above, we’re going to want a helper function to map the data inside a graph, maybe I should add this into the base `Hedgehogs` library, but we’re adding it as an extension for now:

``````implicit class GraphOps[Idx, Data, Distance](g: Graph[Idx, Data, Distance]) {
def mapData[NewData](f: (Idx, Data) => NewData): Graph[Idx, NewData, Distance] =
g.copy(nodes = g.nodes.map { case (k, v) => k -> f(k, v) })
}``````

This just lets us map the data, taking in the index and data, returning the new data.

We’re going to want to ask how many alive neighbours a cell has in a graph:

``````def aliveNeighbours(g: LifeGraph)(id: (Int, Int)): Int =
g.neighbours(id).map(_._1).map(g.nodes).count(identity)``````

And now we can write our main step function:

``````def step(g: LifeGraph): LifeGraph = g.mapData {
case (id, true) if Set(2, 3).contains(aliveNeighbours(g)(id)) => true
case (id, false) if aliveNeighbours(g)(id) == 3               => true
case _                                                        => false
}``````

## Result

``````render(graph.nodes)
// res1: String = """
//   #
//   #
//   #
//      """

render(step(graph).nodes)
// res2: String = """
//
//  ###
//
//      """``````

Get rotated nerd.