My main interest is to use the canvas, to play around with it’s API, and to make things reusable for the next experiments. For example, I would like to reuse all the drag, zoom and painting logic when doing another celular automaton. I think the reusability can be seen in the setup above bellow.
It’s a composition of:
- an animation loop to provide the notion of animation, starting, stoping, and frame by frame iteration.
- a cellular automaton to integrate the visible aspect of an automaton (drawing, draging, zooming) with the invisible aspect (the algorithm).
- and game of life itself that takes an initial pattern and calculates each successive generation.
Those partes where implemented from scratch but a few external dependencies where used to complete the experiment.
Besides Prototype, to provide a consistent interface in this time of turbulence, I’ve also used Oleg’s Animation Frame. If the browser provides animation frames natively it is not needed and it does little (delegating to the browser unless a specific frame rate is asked).
The animation loop has the responsability of driving the game forward frame by frame or step by step. But, in the tradicional input-update-render game loop this object only handles the update part. This means the input processing and rendering is left for the game object that is passed to the loop.
Since the animation loop only deals with the timing of steps and the concept of animation it has no reference of a canvas. It simply supports:
- control buttons,
- animation hooks that are called before or after each step,
- and a game object to do the rest.
First the animation frames support is ensured by activating Oleg’s shim. This is done outside of the animation loop because the browser may already support it well enough and it quickly becomes and unecessary dependency.
Within the animation loop, the initialization prepares all the hooks. The game step and reset functions are also considered hooks which allows a page to decorate those game functions without modifying the game.
The animation loop provides four main functions
reset. For each of this a control button (or any clicable thing) is permited
as a option. Since each controls is optional the initialization is done in three
steps. First the control options are defined unitialized, in the configuration,
to enumerate the options.
Afterwards, for each control configuration, the corresponding control is initialized from the given options. If specified then the configuration is set with the corresponding element.
The final step is to bind each click in the control with one of the animation
loop’s public functions. The controls in the configuration and the public
functions match and it’s easy to keep it that way so the type checking, for the
public function, is more of an assert that confirms the value is a valid event
handler to the
Each public function has the same structure. It considers if the animation is
running or paused, calls the internal function and updates the control
visibility. For example, the
start function is show below.
The controls update is relatively simple. If the game is running then only the
stop button is enabled. If the game is stopped then the other buttons are
enabled. The internal function updates animation loop, calls the appropriate
hooks, and updates the internal state. In the case of the
shown bellow, a new animation is scheduled and the state is set to running
after calling the
We can see that the
animation function is the core of the animation loop. It
keeps the loop alive by continuously requesting another animation frame and
performs one step. As long as each step takes less than 16ms to complete (at
60 fps) then the animation loop is fluid. But if computing the next state and
drawing the canvas takes longer, it starts to slow down.
step function does not consider the animation. It simply calls any before
and after hooks, updates the frame count and delegates to the game object (or
any step hook that was provided). This allows the step function to be the same
function called when the user presses the configured step button, when the game
is not running.
The other public functions are similar to this case. The
reset function is
similar to the
step in the aspect that it does not consider the animation. And
cancelAnimationFrame, to cancel any pending request, and
resets the internal state.
The cellular automaton uses a canvas to provide a visualization, for the Game of Life algorithm, and to control the interactivity with the user. The colors for each pixel are actually calculated by the algorithm but the cellular automaton object controls scalling and other cell-to-pixel mappings and decorations.
First the cellular automaton initializes the canvas to provide the 2D drawing context.
The initial configuration is very simple and presently only captures the initial canvas, algorithm, and provides defaults for the initial scale and the zooming limits.
The initial state specifies the current scale, the cell position of the top left
corner of the canvas, and mouse related information which is starts
uninitialized. Initially we also assume a scale of 1 and that the top-left
position is in
(0.0, 0.0). The adjustements to scale and top-left position are
reset is called. That will be shown later.
The scale represents the number of pixels that correspond to a single cell. So a scale of 5.0 means one cell is represented by 5 pixels, and a scale of 0.5 means 1 pixel represents two cells. In this last case the algorithm is responsible for producing a combined color. The top left indicates the cell coordinate of the top left corner of the canvas. It can be a decimal value like 0.5, specially if the scale is bigger than 1.0 because we can still drag the canvas pixel by pixel.
The scale and top-left positions are changed by zooming (by using the mouse-wheel) and panning (by dragging), respectivly. This values impact on the drawing of the canvas. At the start of every redraw the vancas is cleared. The algorithm can provide a background. This allows the algorithm to provide colors for alive cells.
Cells are drawn as rectangles of the color provided by the algorithm. Due to scaling, the algorithm may be asked for the color of several cells at once (scale > 1). This means a pixel (1x1 rectangle) will have a combined color provided by the algorithm. When the scale is between 0 and 1 then the color of a single cell is used to fill more than 1 pixel.
These functions are used in the main draw function as shown bellow, in parts. First the canvas is cleared and all constants are defined.
Interesting constants are:
- ppc: The number of pixels per cell. The same as the scale.
- cpp: The number of cells per pixel. The inverse of the scale.
- cx0 and cy0: The position of the cell visible in the top left corner of the canvas. This position may be something like (1.5, 2.2), meaning the cell (1, 2) for the algorithm.
- px0 and py0: The position of the pixel corresponding to the top left corner of the cell in the top left corner of the canvas. This is a mouth full best represented by the following image.
In the image we have point
(px0, py0) = (-2.0, -2.0). The point
has two type of coordinates. The coordinates in the canvas, in pixels, are not
interesting because they are always
(0, 0) and we need to draw a rectangle
(px0, py0) with a side of
pcc length. That’s why the top-left
position in kept in cell coordinates and the
pcc is used to calculate the
With this starting values with iterate over the canvas in
ppc increments and
over the cells in
cpp increments. This values are obviously limited to a
minimum of 1, because we move at least 1 pixel and 1 cell. This iteration is
limited by the canvas width or height. This means we assume the cell coordinate
space is infinite and the algorithm must be prepared to accept requests for any
The intermediary values calculated in each iteration are the integers:
- pxi and pyi: The current position in pixels. A square will be drawn in the canvas starting at that position.
- cxi and cyi: The current cell position. The cell at that position will be considered.
- pxdelta and pydelta: The width and height of the square being drawn in the canvas.
- cxdelta and cydelta: The horizontal and vertical number of cells, starting at cxi and cyi, for which a color will be asked.
Iterating over the floating values and then taking the floor of the value allows
for a stable and smoother step, specially when we introduce dragging and decimal
(cx0, cy0). When we pass, for example, from the cell position
(0.9, 0.9) to
(1.0, 1.0) then
(px0, py0) jumps from a negative value to
(0.0, 0.0). In the same way, with a
ppc of 1.8, for example, we sometimes
jump in increments of 1 and other times have and increment of 2. That increment
size also defines the pixel and cell deltas used to retrive the color and paint
The main part of the drawing algorithm is conceptually very simple. Ask the algorithm for the color of a bunch of cells and, if there is a color for those cells paint a square of the appropriate size. If the scale is bigger than 1.0 then, for each cell, we draw a big square. If the scale is less than 1.0 then we get the color of several cells and draw a single pixel. Obvisouly, at 1.0 we have deltas of 1 and a match between pixels and cells.
draw function is used from the automaton public
functions. These provide the connection with the game loop: for each frame there
is a step in the algorithm and a redraw. In the
reset, the positions and
scaling are reset before reseting the algorithm and also redrawing.
applyScale function sets the current scale but also updates the top-left
corner. This allows for a centered scaling, that is, to keep a certain cell
under the same pixel of the canvas. When using an initial scale different than
one this moves the top-left corner further way or closer to the center indicated
by the algorithm.
The function shown above, updates the top-left corner by converting a pixel position, in the canvas, to a cell position and then comparing that position, before and after scalling, to determine an offset. Using a pixel position for the center of the scaling is particularly useful when performing zooming with the mouse wheel as will be shown later.
Having all the main functions ready, all we need now is a way to provide interactivity and scroll the position of the top-left corner and the scaling. That is done by monitoring mouse events in on the canvas. Dragging will translate the top-lef position. The mouse wheel, in turn, changes the scale.
The events that are simple to handle are the
mouseout. When the mouse is down we store the mouse position. Whenever the
mouse is up or leaves the canvas we disable the drag operation.
Whenever the drag is active, the
mousemove event is used to translate the
top-left position. Since the top-left position is a cell position we need to
convert the mouse position into a cell position by using the current
scale. Regardless of drag being inactive, we always store the mouse position
because that is helpful for zooming.
Whenever there is a
mousewheel event, the direction of the mouse wheel is used
to zoom in or out. Zooming corresponds mainly to a change in the used scale, so
if we zoom in we are increasing the scale, that is, the number of pixels used
for a single cell and making cells bigger in the canvas.
Zooming is limited to an interval, to keep cells perceptible and visible, and is
centered on the mouse position. The position saved, when the mouse moves over
the canvas, is used as the center point of the zoom, that is, if, for example,
you place the mouse cursor in the middle of a cell and zoom in then the cursor
remains in the middle of that cell. This is handled by the
function, shown before, after converting the mouse global coordinate into a
canvas coordinate, in pixels.
With this type of drawing and interactivity the algorithm for celular automatas can have very distinct behaviors. I could use the same automata logic and provide an algorithm for the color deamons celular automata. It’s all up to the algorithm which must know how to evolve the pattern in each step and generate a color for a bunch of cells.
The Game Of Life algorithm loads an initial pattern into a current generation and, in each step, calculates the next generation from the current. The current implementation is very simple and not very performance although it fulfills the initial goal of allowing several patterns and provide an infinite space for the cells.
The initial configuration consist only of the starting pattern, that is, the pattern that is available immediatly when the game is reset. The algorithm state is also simple and contains the current generation and population.
Each position is encoded to a string to be easily usable as a map property. The xy position of a cell is stringified to obtain the cell key – or property name – in the object. The following code shows that function and the simple conversion used.
This function is used in the cell accessor
getCell. This function obtains the
current value of a cell in the current generation. If a value is not defined for
that position (empty space) then a “dead” value of 0 is assumed.
There is also a mutator
putCell to change the value of a cell at a given
position. This mutator accepts a target generation in order to be usable by both
the evolution logic, that updates the next generation, and the initial loading
logic, that updates the current generation.
putCell function also updates neighbor cells with 0, or “dead”, if they
are undefined. This is done in order to explicitly define the space that needs
to be considered in each generation. Since cells can only born next to other
cells, if we define all the neighboring space then we just need to iterate
through all those positions, in the current generation, and calculate the
corresponding value for the next generation. If a cell becomes alive then it is
set as alive, in the next generation, and all it’s negbors are set as dead so
they are considered next time around. This algorithm is shown in the main
evolve function shown below.
As you can see, first the population count and the next generation is
reset. Then the algorithm iterates through all the positions of the current
generation and obtains the corresponding coordinates with the function
getCellKeyCoords, which provides the inverse of
For each position an all-field value is computed. An all-field value if
basically a sum of the cell and all it’s neighbors. At this point, the “dead”
value of 0 and “alive” value of 1 become helpful and we just need to add the
cell’s values. This is done in the
neighborhood function shown next.
This eggocentric way of computing the cell state – as described in Wikipedia – allows a more streamlined computation with easy to read cases instead of range comparisons with if statements. If the all-field is 3, then either the cell is alive and has 2 alive neighbors or is dead and has the required 3 neighbors. In any case, the cell is alive in the next generation. If the all-field is 4 then cell value keeps the same for the next generation. And in all the other cases the cell is dead. At the end of this cyle the next generation is computed and we have the resulting population count. So we just need to update the internal state and the cells representing the current generation.
With these function we already have a functioning Game of Life simulation once
we load a pattern into the current generation. This is done by the public
function. Curently no [standard game of life format][ggf] is supported. A new
one, which is very simple, was invented in a minute:
- Blank lines are ignored.
- Each line with some non-space caracter is considered part of the pattern.
- The pattern may be enclosed between pairs of \|.
- The character \| is ignored but any other character is an alive cell.
For example, a blinker can be represented as
| *** |,
| xxx |, or simply
ooo. The pattern will be interpreted and and placed in the middle of the
space. This is done by considering the number of lines and the maximum length of
Having a way of loading a pattern and a function to evolve the pattern into the
next generation we can provide the public
step functions that
connect the algorithm to the automaton or the game loop.
The only thing that is missing is the function
getColor that produces a color
for the cells. This function must be generic and accept any position. It must
also be able to provide a color for square of cells indicated by the width and
height. Since we are using black for cells that are alive we must calculate a
gradient, between black and white, that represents the proportion of alive cells
and dead cells.
Whenever we only have dead cells then we don’t produce a color and rely on the
background color. That was specified, together with what we consider the center
of the space, with the public properties
To put it all together, and actually run the first code sample shown, a simple HTML page was created. The main element of the page is the HTML canvas. Together with the canvas, some information is provided about the current state of the algorithm. Currently the number of steps – or generation – and the population is shown. There are also some controls to control the animation and choose the current pattern.
All the buttons are controlled by the game loop. When the loops is initialized
it binds the button
click event to the game’s functions. The pattern
selections uses an helper function to change the pattern and that is shown
The global object
loop is used to reach the algoritm and load the
pattern. This means that the pattern is the content of an HTML element. For
example, the Acorn pattern is defined as shown bellow.
The other important parts of the page are the game loop’s hooks passed in the initialization. These are used to update the game’s information after each step.
With all this setup we just need to put the key in the engine and start
it. Therefore the last element is the initialization of the loop, automaton, and algorithm by calling the public