Skip to content

Category: javascript

Conway’s Game of Life (JavaScript)

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.

.

Video recording of simulation, live demo can be found here.

Conway’s Game of Life is awesome for being the simplest example of artifical life. It implements a rule-based system for determining whether elements in a grid should be alive or dead, with a very simple rule system. But like with DNA or Ant Colonies (read about it!) a simple set of rules can result in an amazing array of diverse behaviour.

Conway’s Game of Life isn’t hard to implement, and seems like a great target for optimisation. The logic is pretty simple, we need a grid of cells. A lot of people
use two-dimensional arrays for this, but I opted for a 1D array where the rows/columns are calculated through a translation function. Each cell contains a value of 0 or 1 for dead or alive.

The Code

class Grid {
  constructor() {
    this.grid = new Uint8Array(GRID_SIZE);
    this.next = new Uint8Array(GRID_SIZE);
    this.init();
  }

  dump() {
    return this.next;
  }
  swap() {
    this.grid = this.next;
    this.next = new Uint8Array(GRID_SIZE);
  }
  at(x, y) {
    return y * GRID_WIDTH + x;
  }
  init() {
    this.grid = fast_random(GRID_SIZE);
  }

The first part of the Grid class, the main meat of the code, is pretty simple. The Grid stores a current grid and a next grid, which is updated and then swapped with the current one during animation cycles. When the Grid is initialized it grabs GRID_SIZE bits using the fast_random function (more on this later).

Survival Function

For each cell within the “grid”, we need to calculate the number of neighbours to figure out its fate in the next generation. The rules for the game are as follows:

Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overpopulation.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

 

  update() {
    for (let x = 0; x < GRID_WIDTH; x++) {
      for (let y = 0; y < GRID_WIDTH; y++) {
        let score = 0;
        const CURRENT_LOCATION = this.at(x, y);
        for (let i = -1; i < 2; i++) {
          for (let j = -1; j < 2; j++) {
            if (i == 0 && j == 0) {
              // skip self
            } else {
              score += this.grid[this.at(x + i, y + j) % GRID_SIZE];
            }
          }
        }

Here we’re just looping over every cell of the grid, and for each of the cells adding up the 1s in the surrounding 8 cells. From this we can figure out whether it’s going to be alive or dead based on its current state and its neighbour count:

        switch (this.grid[CURRENT_LOCATION]) {
          case 0:
            if (score == 3) {
              this.next[CURRENT_LOCATION] = 1;
            } else {
              this.next[CURRENT_LOCATION] = 0;
            }
            break;
          case 1:
            if (score > 3 || score < 2) {
              this.next[CURRENT_LOCATION] = 0;
            } else {
              this.next[CURRENT_LOCATION] = 1;
            }
            break;
        }
      }

Pretty simple!

Rendering the Output

I wanted to write several potential renderers to test what gave the best performance. Each simply takes a grid as an array and draws it.

const renderer = RectangleRenderer;
render = new renderer();
let grid = new Grid();

function iterate() {
  grid.update();
  render.render(grid.dump());
  grid.swap();
  requestAnimationFrame(iterate);
}

var ctx;
$(document).ready(function() {
ctx = $("#game-view")[0].getContext("2d");
iterate();
});

Initial Optimisations

Ok so, one problem. With a 256×256 grid the initial start-up takes up to 9 seconds. Some quick JS Profiling in chrome seemed to indicate that the culprit was the init() function.

The init() function was seeding the grid by iterating over the entire grid’s X/Y coordinates and filling each cell with a random 0 or 1. But in order to do this, the Math.random() function was being called for each cell (meaning it needs to be called 65535 times) as the following:

  cell = Math.floor(Math.random()*2)

As it turns out this is extremely wasteful. In theory, each call to Math.random() could be used to supply up to 32 unique bits per call, which would reduce the number of calls significantly. After implementation, the init() function began to run almost instantaneously:

function random_byte() {
  let el = Math.round(Math.random() * (Number.MAX_SAFE_INTEGER/2) + Number.MAX_SAFE_INTEGER/2);
  let bits = [];
  static_counter += 1;

  while (el > 1) {
    let bit = Math.floor(el % 2);
    bits.push(bit);
    el = el / 2;
  }

  return bits;
}

function fast_random(size) {
  let array = [];

  while (array.length < size) {
    let c = random_byte();
    array = array.concat(c);
  }

  return array.slice(0,size);
}

With this function added, the initial delay disappeared entirely for a 256x256 grid. In the next article I'm going to look at some of the algorithms used in speeding up the Game of Life as an implementation level.

Ruby’s Array#map_with_index and each_with_index in Javascript

#each_with_index and #map_with_index are commonly used Ruby features that can be easily achieved in JavaScript

Each with index

In Ruby we can do this:

x = ["a","b","c","d","e"]

x.each_with_index { |el,n| puts "#{n} is #{el}" }

Output:

0 is a
1 is b
2 is c
3 is d
4 is e

In Javascript it’s possible to do something very similar. The documentation for JavaScript’s Array.forEach function states that the three arguments passed to the callback function are:

callback is invoked with three arguments:

the element value
the element index
the array being traversed

Therefore we can do this:

let array = ["a","b","c","d","e","f"];

array.forEach((x,n) => (console.log(x + " is " + n)));
a is 0
b is 1
c is 2
d is 3
e is 4
f is 5

Map with index

In Ruby it’s possible to do this:

x = ["a","b","c","d","e","f"]

z = x.map.with_index { |el,n| (el.ord + n).chr }

puts z

Output:

a
c
e
g
i
k

Similar to with forEach, Map has the following arguments passed to its function argument:

currentValue

The current element being processed in the array.

indexOptional

The index of the current element being processed in the array.

arrayOptional

The array map was called upon.

Which makes it possible to do this:

let array = ["a","b","c","d","e","f"];

let new_array = array.map((x,n) => String.fromCharCode(x.charCodeAt(0)+n));

console.log(new_array);

Output

[ 'a', 'c', 'e', 'g', 'i', 'k' ]

Genetic Algorithms: Evolving “Hello World” in Javascript

I’ve always been extremely interested in evolution as an optimisation algorithm, this post is part of a series of write-ups on experiments using genetic techniques.

If you’re just interested in seeing the end result, check the demo here

Evolution is often described as being a “random” process. Some lay understandings of evolution imply that its process is not feasible given the number of “random” mutations required in order to produce a particular change or result in an organism. The key point neglected in these evaluations is that while mutations are a random component of evolution, the main power is its ability to accumulate “useful” mutations over time. The algorithm presented here is a simple illustration of the power of these kinds of algorithms, future articles with examine more advanced usage of the capabilities.

The problem

Generating the string “Hello, World!” (or any other) from random selections of letters. We start with an initial population of randomly generated strings and allow survivors whose string distance score is the smallest.

The problem space

Given the length of the string N, we will have to search through 26^n possibilities, leading to very rapid combinatorial explosion. For the “Hello, World!” string we will need to search through 2.4811529e+18 (that is, 2.48*10^18) different strings to find the one we’re looking for.

Strings are generated as candidates using the following function, resulting in each initial generation consisting of a series of randomly generated sequences of letters. Note that the alphabet doesn’t contain punctuation, even though it is used in the target string. This is because mutations will result in ASCII characters outside the specified range.

function random_string(len) {

  return new Array(len)
             .fill(0)
             .map((_) => ALPHABET.charAt(get_random_int(0,ALPHABET.length)))
             .join("")
  }

Elements of Genetic Algorithms

Since this example is very simple, it becomes easy to create a set of tunable parameters to investigate the effects on the resulting evolutionary process. These parameters are specified at the top of the JS file:

// string we're targetting
const TARGET_STR = "this string was produced by evolution";
// maximum length of initially created strings
const RANDOM_STR_MAX_LEN = 50;
// mutation rate. 40 means that on average each gene in 40 will be mutated 
const MUTATION_RATE = 40; 
// the tokens to draw from when creating initial strings
const ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 
// the amount to increase or decrease each ASCII amount by during mutation
const MUTATION_STEPS = 2 
// penalty for being a different length from target string
const PENALTY_FACTOR = 100 
// initial generation size
const INITIAL_GENERATION_SIZE = 100;  
// number of candidates allowed to breed
const ALLOWED_TO_BREED = 40; 
// number of candidates allowed to survive
const ALLOWED_SURVIVORS = 40; 

Iteration

Each new generation is produced partially from the prior ones. Some of the best candidates will survive to the next round, and will also “breed” with other candidates to produce new candidates.

Fitness

After each round “fitness” should be evaluated. This is the digital equivalent of the survival/replication aspect of real evolution. A candidate’s fitness score is used in order to judge whether or not it will survive to the next generation. The algorithm described here uses a numerical distance factor created by summing the integer distance of the character codes of the candidate vs. the target string.

function fitness(str) {

  let smallest = Math.min.apply(null,[str.length, TARGET_STR.length]);
  let score = 0;
  score += Math.abs(str.length - TARGET_STR.length) * 100;

  for(let x=0;x<smallest;x++) {
    score += Math.abs(str.charCodeAt(x) - TARGET_STR.charCodeAt(x));
  }

  return score;

}

Mutation

Mutation introduces the ability to inroduce new genetic material in each round. Interesting results occur if the mutation function is removed or altered, and can result in a single dominant solution very early on with little or no new genetic material. For each child of the candidates in each generation, for every codon there is an 1 in MUTATION_RATE chance of a mutation occuring, which shifts a single letter’s character code by a random amount. If MUTATION_STEPS is 2, the random amount to shift will be between -1 and 1. If it’s 10, the random amount will be between -5 and 5.

function mutate(str) {

  return str
         .split("")
         .map((letter) => 
           (Math.round(Math.random()*MUTATION_RATE) == 2) 
           ? 
             String.fromCharCode(letter.charCodeAt(0)+Math.round(((Math.random()*MUTATION_STEPS)-(MUTATION_STEPS/2)))) 
             : 
             letter)
         .join("");

}

Breeding/Recombination

In order to retain the benefits of the optimal candidates, we cross-breed the best solutions. There are numerous ways to do this. One might be to simply take the odd numbered characters from one string, the even numbered characters from another string, and splice them together. Another could be to just use the first half of one string and the second half of the other. A solution often used in genetic algorithm research is creating “cut points” in the genomes of the two candidates. For instance, imagine two strings:

AAAAAAA
BBBBB
We select cut points 3 and 4 in string1, and 2 and 4 in string2, the resulting child ends up being:
  str1 0-3 AAA
  str2 2-4 BB
  str1 4-5 A
  = AAABBA

These functions are implemented as follows:

function breed(str1, str2) {

  let cp_1 = get_random_int(0, str1.length-1); 
  let cp_2 = get_random_int(cp_1, str1.length-1);
 
  // cp_1 is in the first string, defined as the first cut-point
  // this means we will take genetic material from str1 from 0 -> cp1
  // this will then be combined with the genetic material between cp_3 and cp_4 in str2
  // so we have str1[0,cp_1] + str2[cp_3,cp_4] + str1[cp_2,str1.size]

  let cp_3 = get_random_int(0, str2.length-1);
  let cp_4 = get_random_int(cp_3, str2.length-1);

  return (str1.slice(0, cp_1) + str2.slice(cp_3, cp_4) + str1.slice(cp_2, str2.length)).toString();

}

Put it all together and run it in the console and you end up with a generational history something like this:

 [lWTogtaMKlaXTHFozonCcqkpIrpESsEIqSSl, 916]
 [hduqCqurauqCqtrEsvrhprahDawErvrpvrpen, 349]
 [ieprBstrhtrDrtrEsvqbtaagDbwEavrputagn, 295]
 [hepsDrurirqCrdsCprrctaafBbxDavpptughn, 256]
 [iegsCquritgCrctBprpct#beBbxDcuonuthgn, 232]
 [uggtAqtrithBvbtBprpbtcbdBbxDcuonuthgn, 210]
 [uggs#rtrjnhAwasBprqctcid#ayCcvolurihn, 193]
 [ughs#rtrinh#xatAprpducdd#ayBdvnlutign, 180]
 [thhs#strinh#wat#prpcucdd#bxBdvnlutiin, 169]
 [this#strinh#wat#qroduced#byBdvnlutiin, 160]
 [uhis#strinh#wat#pqoduced#by#cvolutiin, 152]
 [this#string#xas8pqpduced#by#evoluthjn, 142]
 [this#string9was6qqoduced9by#evoluuijn, 134]
 [thhs9string7was8produced6by#evolutikn, 125]
 [this7strhng7was8prodtced5by#evolutiln, 122]
 [this7rtrgng5was2produced3bz#evolutimn, 113]
 [thhs6strgng3was2producfd2by8evolution, 105]
 [this6strgng1was2produced2by5evolution, 98]
 [thjs4string0was1producee0by3euolution, 91]
 [thjs3string0was1produced0by1fvolution, 87]
 [this1ssring#was#prodtced#cy#evplutjon, 80]
 [thit0string#was#prodtced#bz#evolution, 75]
 [this0string#was#prodtced#by#euolutjon, 69]
 [this#string#was#produced#by#evoluuion, 63]
 [this#ssring#was#produced#by#evolution, 59]
 [this#string#was#qroduced#by#fvolution, 55]
 [this#string#was#prodvced#by#evolution, 51]
 [this#string#was#psoduced#by#evolution, 46]
 [this#string#was#producdd#by#evolutipn, 38]
 [this#string#was#procuced#by#evplutioo, 26]
 [uhis#string#was#produced#by#evolutioo, 22]
 [this#stoing#was#produced#by evolution, 20]
 [shis#stting#was#produced#by evolution, 17]
 [tiis stting#was#produced bx evnlutiom, 11]
 [this#stting was#procuced bx evnlution, 9]
 [this#stsing was producee by evomution, 4]
 [this string wat producee by evolution, 2]

Feel free to try the live version here or check the code out from github to play with.