GameOfLife

Github

Overview

Challenge:

To create a Unity project exploring the Conway's Game Of Life in 72 hours in 2D and 3D.

My Approach:

Spend the first day or so, trying to understand the algorithm, using coins and sketches to grasp the context of the exercise. I watched John Conway interviewed on Youtube. Interesting! I was trying to avoid processing every pixel and its neighbors for every frame. This is brute force. Good enough for a proof of concept, though. The underlying algorithm involving the pattern over time of each cell, is where the action is. Understanding the historical patterns of each cell state can possibly lead to an algorithm that predicts where the next new cells will appear, which will expire, and which will continue. This algorithm will be fast, calculating only the live cells and their immediate neighbors, or predicting which cells to calculate. One huge issue is where the seed data comes from. It is a snapshot in a sequence that we are trying to identify and use to generate the next cycle. Speed can be increased by only regenerating bounding boxes of touching active cells. This would work well for low density situations. I spent a day in Unity, and a day documenting and sharing. I took photos and screen grabs along the way, documenting as I went alone,

What I would try next:

Since there are 256 possible neighbor layouts in 2D for each cell, we can create a byte array as a lookup table. We can pre-calculate all 256 possible outcomes and create a lookup table of the next cycle. The would result in a nice speed increase. In 3D, there would be 2^26 possibilities to consider for each cell, since it has 26 neighbors.

Understanding 2D in 3D:

A good next step in understanding the underlying algorithm is to view 2d grids in 3D as slices, to see each cell evolving over time, starting with Glider.

Fun Fact:

There are only 512 possible neighborhoods! I need another week!

2D Rules:

If a cell is alive, and neighbor count is greater than 3, the cell is crowded, and is removed in the next cycle.

If a cell is alive, and neighbor count is less than 2, the cell is alone and is removed in the next cycle.

If a cell is not alive, and the neighbor count is equal to 3, the cell will be alive in the next cycle.

Features

Wrap Around:

Edge conditions are a consideration here. Wrap-around updates off-grid cell positions on one side, to the opposite side. The end result is a virtual grid. Cells appear to wrap-around the grid in any direction.

Neighbor Count:

Neighbors are counted for every cell. Each cell in 2D has 8 neighbors (3 x 3 - 1). Each cell in 3D has 26 neighbors (3 x 3 x 3 - 1). Diagonal neighbors (catty corner) count equally as neighbors (even though they are further away).

ynShowNeighbors:

In 2D, cell heights can reflect neighbor counts. This feedback is informative.

ynShowNew

Show cells that are now alive but where not in the previous cycle.

ynShowAlone

Show live cells with fewer than two neighbors.

ynShowCrowded

show live cells with more than three neighbors.

ynStep

step thru cycles with a 1 second delay.

Further Studies

Neighbor Count Per Cell

Studying Glide, I notice that I add 2 and remove 2 cells each cycle. That's 4 out of 9 cells. If neighbors are touched only when adding or removing cells, we save 5 neighbor operations. The grid needs to be regenerated at the beginning, meaning that each cell counts its neighbors and populates its neighborCount. Then for each cycle after, each grid cell's neighbor count is checked. If on, if n < 2 or > 3, then its off, and its neighbors' nCount is reduced by 1 (8 operations). If off, if n == 3, then it on, and its neighbors' count is increased by one. So each cycle, we affect neighbor counts only when they change. This might be twice as fast.