Optimizing Conway’s Game of Life in JavaScript — Part I

This is another smaller pure JavaScript project. That being said, if I am able to efficiently optimize this code, I will attempt to apply some sort of interactive interface online. I’ve never really toyed with creating games but when I came across this Kata it immediately reminded me of the simple non-competitive games I used to play as a kid. You know those games where you mindlessly floated around, or collected crystals, with no real goal?

In this analysis I will briefly mention why I have made extraneous choices, and why I believe they will be applicable in the n + 1 iteration of the program. By making these forward thinking choices in my practice, I find that it helps educate me in making more advanced decisions earlier, in line with the fail-edit-learn approach. Fail faster and I get more out of it.

See the full code here

Photo by Joel Filipe on Unsplash

Process

1. Get the program to correctly generate new generations
2. Optimize the program so that it isn’t wastefully processing
3. Change the structure of the Life maps from a 2D config to a toroidal config
4. Wireframe / Plan Visuals
5. Deploy to a React app

Getting the program to work with a 2D config without recursion

I wanted to jump right into a recursive algorithm that would generate each new generation without a for loop, but I quickly realized I had a lot of decision making to do before I’d be able to handle that.

Initial model of the computed data

The first decision I had to come to was to decide how I wanted to store the data I was generating. It seems that typically these would be handled with an array of the previous generation and an array of the current generation. Having to only keep track of two arrays seems nice and easy, but I'm thinking forward a bit so I've abandoned the simple 2-part array. The reason for this is that I would like my user to be able to "rewind" my visual model at the later stage so I need to keep track of more than just the previous generation and current generation. My thought, though untested, is that this would save on computing because the data already knows what happened 15 generations ago.

Setting up the generations

The getGeneration() function takes to arguments. An array cells, that is the seed, and generations which is an int of how many generations we would like our seed to live.

For my initial variables I declare:

• a mutable copy of my data, which I always do and is unnecessary because I’m good about not using mutative methods. const initialGen = cells
• a cache for each of the generations that are computer let genCache = [].

The for loop that computes each generation is pretty simple. It starts with the previous generation, which depending on whether our cache has anything in it, will be the initial seed or the last item in the cache. On display is also my current obsession with ternary operators.

for (var i = 0; i < generations; i++){
  const previousGen = genCache.length > 0 
   ? generateNextState(generateGenState(
       genCache[genCache.length - 1]))
   : initialGen 
  genCache.push(previousGen); 
};

Generating the stateful cells

I refer to it as state now, even though it isn’t something that changes, but I’m anticipating it to later so I’m covering some of my bases now. For the initial state of the generation I define what each value of the arrays, or cell, is going to look like for our computations. I’m also using the default value of 0 for neighbors should something not get passed in. Probably unnecessary but I want to start using these more.

function Cell(x, y, cellState, neighbors = 0){ 
  this.x = x; 
  this.y = y;
  this.hash = (this.x * 15486047) + (this.y * 15487429); 
  this.isAlive = cellState; 
  this.neighbors = neighbors 
};

• A cell has an x and 'y' value, which I was using when testing against my hand written tests.
• A cell has a hash value, which I what I'm assuming I'm going to need for hash evaluation for memoization later. This is just a computation of the x and y values multiplied by a high prime number.
• The cell has an isAlive property which I do use in the initial iteration of this function. This lets me know if the cell is a 0, or 1.
• The cell also has a neighbors value which, egocentrically, let's me keep track of the number of 1 values for each cell adjacent top, bottom, and perpendicularly.

Now for the creating my map of the cells, with their more complicated state.

return rawCells.map((terrian, i, arr) => { 
  return terrian.map((cell, p, arr2) => {
    const cellState = Boolean(cell); 
    const above = arr[i - 1] !== undefined ? arr[i - 1][p] : 0;  
    const below = arr[i + 1] !== undefined ? arr[i + 1][p] : 0; 
    const right = arr2[p + 1] !== undefined ? arr2[p + 1] : 0; 
    const left = arr2[p - 1] !== undefined ? arr2[p - 1] : 0;
    const abovePerps = arr[i - 1] !== undefined 
      ? [arr[i - 1][p - 1], arr[i - 1][p + 1]] 
      : [0, 0]; 
    const belowPerps = arr[i + 1] !== undefined 
      ? [arr[i + 1][p - 1], arr[i + 1][p + 1]] 
      : [0, 0]; 
    const neighbors = checkNeighbors([
      right, left,
      above, below, 
      abovePerps[0], abovePerps[1], 
      belowPerps[0], belowPerps[1] 
    ]); 
    return new Cell(i + 1, p + 1, cellState, neighbors); 
  }); 
});

As I write this out I’m already seeing things I’d change.

• We map over each terrain, where each cell lives, and then return the stateful cell
• There are a lot of ternary operators here, which is why I think some people are adverse to using them. It does look a bit messy. You can really pile of them a lot of them in. Once again, I use them because it takes the conditional logic off the functions that need only values.
• These ternary operators are especially useful when mapping over 2 arrays, when needing to compare to arrays “above” or “below” the current array. If I simply tried to pass arr[i + 1][p] into my function that needs to count the total number of neights an error would throw. arr[i + 1] would return undefined at the last level of my map, but trying to access a specific index arr[i + 1][p] when p doesn't exist on undefined throws an error Cannot read property 0 of undefined.

Generating the life map for the next generation

As I’m spitting out basic life maps for each generation, not just the seed and the final generation, my generateNextState() function returns an array of arrays of the life, 0 or 1, based on the generation passed in. This is where I ran into a logical mess with ternary operators (yes, they are not as cut and dry as if statements so if you aren't thorough you can break everything). That being said when I reorganized how I was thinking about the logical deduction the path was clear and I was able to use these pretty little babies again.

Initially I screwed up because I wasn’t simplifying enough. As I don’t version control these mini-projects (I plan to start doing so soon because they are getting more complicated) here is a general breakdown of the mess I created:

return cells.map(terrain => {
  return terrain.map(cell => {
    return (cell.isAlive === true && cell.neighbors < 2) 
      ? 0 
      : (cell.isAlive === true && cell.neighbors) > 3 
        ? 0 
        : (cell.isAlive && cell.neighbors === 2) 
          || (cell.isAlive && cell.neighbors === 3)
         ETC ETC ...

See? What a mess. I’d forgotten my rule to simplify things first. First, every instance I need to check the isAlive value. This also doesn't fit AirBnb's style guides that ternary operators should be single line expressions.

return cells.map(terrain => {
  return terrain.map(cell => {
    return cell.isAlive 
      ? do something 
      : or do something else because its dead
  });
});

Alas the cleaner version.

return cells.map(terrain => {
  return terrain.map(cell => {
    const twoOrThree = (cell.neighbors === 2
                     || cell.neighbors === 3) ? 1 : 0; 
    const greaterThanThree = cell.neighbors > 3 ? 0 : twoOrThree;    
    const convertLive = cell.nieghbors < 2 ? 0 : greaterThanThree; 
    const convertDead = cell.neighbors === 3 ? 1 : 0;
    return cell.isAlive ? convertLive : convertDead 
  }); 
});

• The first thing I’ve done is created my single line ternary operators for each of the options based on the number of neighbors which was store in the cell’s state in the earlier function. I would prefer to chain these together, but I can see how that can cause problems editing later because if you mess up the chain of the ternary operator nothing works.
• The return for the map is cleaner too. Is the cell alive? Convert it to a 0 or 1 based on the number of neighbors it has then. If it's not alive do the same thing.

Expectations for the next step of the process

I have a few decisions that I will need to make when moving on to optimize/edit what I have started:

1. Is it actually import that there be a historical log? The point of this game isn’t really to see the past.
2. I will probably move away from the ego-centric neighbor calculation and do it based on areas, so that I can skip calculations if they aren’t needed.
3. I plan on skipping things I will need to rebuild the arrays based off an object. I doubt this will be complicated because there are plenty of object methods now, it might just change the form of the code completely.
4. I will probably want to decide if I’m handling this as a toroidal array before I get started on anything else.
5. I don’t want to provision a whole new app build just for this so I’m going to have to figure out what I can tack it on to. How do I not have a hodge-podge project where I can just throw anything?

Originally published at gist.github.com.