Conway's Game of Life in 3D with Graphs

Posted on 2023-04-09
Tags: scala, open source, personal project, graphs, 3d

To follow on from my previous post, I’m going to try and run conway’s game of life in 3d, let’s see what happens.

I’ll just naievely scale the rules from 2d to 3d, we’re going from 8 neighbours to 26 neighbours, to scale relative to that:

Domain

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

On each time step, the following is performed:

  • Any live cell with two or three six to ten live neighbours survives
  • Any dead cell with three eight to ten 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, 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 5x5x5 grid:

import net.andimiller.hedgehogs._

// use a 3x3x3 cube
val initialPattern = (for {
  x <- 1 to 3
  y <- 1 to 3
  z <- 1 to 3
} yield (x, y, z)).toSet
val nodes = for {
  x <- 0 to 4
  y <- 0 to 4
  z <- 0 to 4
} yield Node((x, y, z), initialPattern.contains((x,y,z)))

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
  z <- 0 to 4
  tx <- x-1 to x+1
  ty <- y-1 to y+1
  tz <- z-1 to z+1
  if ((x,y,z) != (tx, ty, tz)) // don't connect to itself
  if (validRange(tx))          // stay in the grid
  if (validRange(ty))
  if (validRange(tz))
} yield Edge((x,y,z), (tx, ty, tz),  weight = 1)

We can combine these into our graph:

type LifeGraph = Graph[(Int, 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 3D grid, so let’s do some quick string creation:

import cats.implicits._
def render(nodes: Map[(Int, Int, Int), Boolean]): String = nodes.toList.mapFilter { 
  case ((x, y, z), true) => Some(s"""{x:$x, y:$y, z:$z}""")
  case (_, false)        => None
}.mkString_("[", ", ", "]")

render(graph.nodes)
// res0: String = "[{x:2, y:1, z:3}, {x:3, y:1, z:2}, {x:2, y:2, z:1}, {x:3, y:2, z:2}, {x:2, y:3, z:2}, {x:3, y:2, z:1}, {x:2, y:3, z:1}, {x:3, y:3, z:3}, {x:1, y:1, z:3}, {x:1, y:2, z:2}, {x:1, y:2, z:3}, {x:1, y:3, z:1}, {x:2, y:2, z:2}, {x:2, y:1, z:1}, {x:1, y:3, z:3}, {x:1, y:1, z:2}, {x:3, y:2, z:3}, {x:2, y:3, z:3}, {x:3, y:1, z:1}, {x:3, y:3, z:1}, {x:1, y:1, z:1}, {x:3, y:1, z:3}, {x:2, y:2, z:3}, {x:2, y:1, z:2}, {x:3, y:3, z:2}, {x:1, y:2, z:1}, {x:1, y:3, z:2}]"

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)): 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(6,7,8,9,10).contains(aliveNeighbours(g)(id)) => true
  case (id, false) if Set(8,9,10).contains(aliveNeighbours(g)(id))     => true
  case _                                                               => false
}

Results

render(graph.nodes)
// res2: String = "[{x:2, y:1, z:3}, {x:3, y:1, z:2}, {x:2, y:2, z:1}, {x:3, y:2, z:2}, {x:2, y:3, z:2}, {x:3, y:2, z:1}, {x:2, y:3, z:1}, {x:3, y:3, z:3}, {x:1, y:1, z:3}, {x:1, y:2, z:2}, {x:1, y:2, z:3}, {x:1, y:3, z:1}, {x:2, y:2, z:2}, {x:2, y:1, z:1}, {x:1, y:3, z:3}, {x:1, y:1, z:2}, {x:3, y:2, z:3}, {x:2, y:3, z:3}, {x:3, y:1, z:1}, {x:3, y:3, z:1}, {x:1, y:1, z:1}, {x:3, y:1, z:3}, {x:2, y:2, z:3}, {x:2, y:1, z:2}, {x:3, y:3, z:2}, {x:1, y:2, z:1}, {x:1, y:3, z:2}]"
render(step(graph).nodes)
// res4: String = "[{x:2, y:4, z:2}, {x:0, y:2, z:2}, {x:3, y:3, z:3}, {x:1, y:1, z:3}, {x:1, y:3, z:1}, {x:2, y:2, z:4}, {x:1, y:3, z:3}, {x:3, y:1, z:1}, {x:3, y:3, z:1}, {x:1, y:1, z:1}, {x:3, y:1, z:3}, {x:2, y:2, z:0}, {x:4, y:2, z:2}, {x:2, y:0, z:2}]"
render(step(step(graph)).nodes)
// res6: String = "[{x:2, y:2, z:2}]"
render(step(step(step(graph))).nodes)
// res8: String = "[]"

Well that exploded then fizzled out, maybe we can find a more stable pattern, or iterate on the rules…