gol-ls.ls

# Conway's Game of Life, in LiveScript
# ====================================
# 
# Conway's Game of Life is a cellular automaton, published by John H Conway
# in 1970, fulfilling the design principles but greatly simplifying the
# research of von Neumann, into a hypothetical machine that could build
# copies of itself. It is a zero-player game, meaning there is no input, and
# the game will progress on its own with a 'seed', or configuration, to
# begin with.
#
# As a computer simulation, Life (as it will be herein abbreviated) has had
# phenomenal cultural interest across all different fields; in my usage here,
# I am implementing a familiar objective pattern for Life in different
# languages, and in as idiomatic a structure and style as I can, in that
# language.

# Each cell will have a CellState, defining whether it is alive or dead. The
# default states are added as static attributes of the class.
class CellState
  (@_state) ->

  @LIVE = new CellState true
  @DEAD = new CellState false

# Cells are the general focus of our cellular automata, representing here a
# location where one of the automatons could be living or not (the _state).
# The state is determined each tick by the GameOfLife object itself, based
# on the rules laid out by Conway.
class Cell
  ->
    @_state = CellState.DEAD

  get-state: ~> @_state
  set-state: (s) ~> @_state := s

# In order to abstractly identify locations in two-dimensional space while
# storing the Cells in a one-dimensional array, we use a FlatVector. FlatVectors
# have a method, to-id, which will find the iterative position of the cell.
class FlatVector
  (@x, @y) ->

  # A convenience method for adding two vectors, since we can't overload
  # operators in JS/LS.
  plus: (v) ~> new FlatVector @x + v.x, @y + v.y

  # The key convenience method that makes the FlatVector a FlatVector; by
  # finding the area of the rectangle from (0, 0) to (width, y) and then
  # adding x, we can determine its position if each row were run together,
  # end-to-end.
  to-id: (w) ~>
    | y < 1     => x
    | otherwise => w * (y - 1) + x

  # The opposite of to-id; from-id takes an id, width and height and returns
  # a new FlatVector that unwinds the formula that assembled our id.
  @from-id = (i, w, h) -> 
    | i > (w - 1) * (h - 1) => false
    | otherwise             => new FlatVector (i % iw), (floor i / iw) + 1

# Our World is a simple representation of a two-dimensional space, stored
# in a one-dimensional array. The cells are handled here, and we use FlatVectors
# to convert virtual X and Y coordinates into array ids for calls to the cells.
class World
  (@width, @height) ->
    @_cells = []
    @each (v) ->
      @_cells[v.to-id] = new Cell
  
  # A convenience operator for our World, which will iterate over the world in
  # a virtual two dimensions.
  each: -> (callback, endline-callback) ~>
    for y from 0 til @width
      for x from 0 til @height
        callback new Vector x, y
      endline-callback?!

  get-cell-state: (v) ~> @_cells[v.to-id].get-state!
  set-cell-state: (v, s) ~> @_cells[v.to-id].set-state s

  # Returns an array of FlatVectors, each pointing to one of the eight neighboring
  # cells to the one provided. This is used for quickly filtering and counting
  # neighbors, for the Life rules (below).
  get-neighbors: (v) ~>
    # Each of these coordinates corresponds with a relative direction in two
    # dimensions, in the order:
    #   NW, N, NE, W, E, SW, S, SE
    n = []
    each [[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]] (k) ->
      n.push v.plus(new FlatVector k.0, k.1)
    return n

  # Returns the number of living neighbors surrounding a given cell at FlatVector
  # v, for the purpose of determining a cell's next state.
  get-num-living-neighbors: (v) ~>
    length filter (n) -> @_cells.get-cell-state n.to-id == CellState.LIVE, @get-neighbors

# This is where everything begins to come together. Once we have our component
# parts lined up and ready, we can assemble them together in our GameOfLife object.
# GameOfLife holds the World, which holds the Cells, and provides a tick() method,
# which will step the simulation forward one run.
#
# The rules which Life follows are very simple:
#
# 1. Any cell with fewer than two neighbors dies, as if caused by underpopulation.
# 2. Any cell with more than three neighbors dies, as if caused by overpopulation.
# 3. Any cell with two or three neighbors lives on to the next generation.
# 4. Any dead cell with exactly 3 living neighbors comes to live in the next generation.
class GameOfLife
  (@world) ->

  tick: ->
    nw = new World @world.width!, @world.height!
    @world.each (v) ->
      nw.set-cell-state v, switch @world.get-num-living-neighbors v
        | 3 => CellState.LIVE
        | 2 => @world.get-cell-state v
        | _ => CellState.DEAD
    @world := nw