Sierpinski triangle (JavaScript)

From LiteratePrograms

Other implementations: C | Erlang | Forth | Haskell | JavaScript | OCaml | Perl | Python | Scheme | Sed

This program will display a crude Sierpinski triangle by calculating a simple one-dimensional cellular automaton and displaying its changing state over time.

We will use an array to represent the current state of the one-dimensional universe. We allocate an extra byte at the end (width+1) to avoid overflow during the later generational calculation. init_state() clears the array and sets one cell to Full. print_state() writes the current state to the document, showing a space for Empty cells and '@' for full cells.

<<state>>=
var width = 80
var state
function init_state() {
  state = new Array(width+1)
  state[width/2] = 1
}
function print_state() {
  for (var i=0; i<width; i++)
    document.write(state[i] ? '@' : ' ')
  document.write("<br/>\n")
}

The particular cellular automaton for generating a Sierpinski triangle looks at the current cell and the two neighboring cells. There are eight possible permutations of the states of these three cells (which will henceforth be called the neighborhood), and we will represent the automaton as a table mapping the state of the neighborhood (represented as a number from 0..7) to the next state of the current cell. The rule stated succinctly is to clear the cell if the neighborhood cells are the same (all Empty or all Full) and set the cell if the three cells differ.

<<automaton rules>>=
// the index has three bits: b0,b1,b2 = next neighbor, current cell, previous neighbor
var transition = [0,1,1,1,1,1,1,0]

The function gen() will keep the neighborhood of the current cell on the stack. It is easy to obtain the neighborhood of the current cell from the neighborhood of the previous cell. You just shift the window: shift right (2*n), putting the state of the next neighbor into the LSB (| state[i+1]) and taking away the old neighbor from the MSB by restricting the result to three bits (& 7).

<<current neighborhood>>=
((2*n) | state[i+1]) & 7

gen() invokes the automaton to obtain the next generation of the state from the previous state.

<<gen>>=
function gen() {
  var n = state[0];
  for (var i=0; i<width; i++) {
    n = current neighborhood
    state[i] = transition[n]
  }
}

sierpinski() will calculate and show height generations of the automaton (including the initial one), displaying a Sierpinski triangle height characters tall and 2*height+1 characters wide. Powers of two for height generate complete triangles. The entire construct is wrapped in a pre block for proper formatting within a web page.

<<sierpinski.js>>=
state
automaton rules
gen
function sierpinski(height) {
  document.write("<"+"pre>\n")     // split tag for proper wiki formatting
  init_state()
  print_state()
  for (var i=1; i<height; i++) {
    gen()
    print_state()
  }
  document.write("<"+"/pre>\n")
}
sierpinski(32)

Download code