A colorful version of Conway’s Game of Life
Posted by jimblackler on Oct 30, 2014
Here’s a web-based version of Conway’s Game of Life. The rules are the standard recipe but I’ve added colour a color effect to the cells. At startup the cells are assigned colors with random hues. Newly-created cells take the color most similar to the neighbouring cells. When cells die I leave a trace of their color in the vacant cell background.
Adding color makes the simulation more striking, and it also vividly illustrates how local patches of the simulation share common ancestry.
About Life
Conway’s Game of Life is a wonder of mathematics. Invented by mathematician John Conway in the 1970s, it isn’t really a game but a simulation experiment involving squares in a grid (‘cells’) that are either ‘live’ or ‘dead’. Any live cell without two or thee neighboring live cells (including diagonals) becomes a dead cell on the next turn (or ‘generation’). Any dead cell with three neighbouring live cells becomes live on the next generation.
From those very simple rules arises a fascinating array of complex behavior. The menagerie of structures and creatures that can emerge has been studied continuously since Conway invented his game. You can read all about Oscillators, Spaceships, Reflectors and more on LifeWiki and elsewhere. The small library of Life shapes that I include in my simulation were borrowed from the excellent resources on LifeWiki.
Life is one of those ideas that is so simple it begs for variations. For my project I decided to make an implementation that kept the basic Life rules but added colors to the cells.
Demo
My demo is written in JavaScript and uses Canvas for the graphics. You can vary the size of the grid and the update rate with the links at the top of the page, as well as toggle the color effect.
When a cell is newly-created a hue is determined which is formed by summing a 2D vector for each of the three live neighbours’ hues; representing the position on the circumference of a circle where the angle represents the continuous hue value. The hue of the new cell is taken as the angle between the origin and the end of the combined vectors (using Math.atan2). This way an ‘average’ can be obtained that does not tend towards any locality on the color spectrum.
As the simulation is so computationally extensive it can act as a benchmark of sorts between browsers. At the time of writing, Safari on OS X was giving the fastest results.
The source is available on GitHub and has a GNU license.
As always, any comments or enquiries are welcome here or at jimblackler@gmail.com.
A tree diagram (SVG) generation tool in JavaScript
Posted by jimblackler on Oct 16, 2014
This tool creates SVG (Standard Vector Graphics) files to illustrate information structured as a basic tree.
Here I define tree as an ordered graph without loops where every node has zero or one ‘parent’ nodes in the same tree.
It’s a very common structure in computing and will be familiar to most as the structure of folders on a personal computer (as seen in the ‘Unix’ example). It’s also the structure of classes in a single-inheritance object oriented programming language (as seen in the ‘Java’ example).
However lots of real world data can be formatted this way too. For instance an ‘org chart’ of the hierarchy of an organization (because everyone has a boss, apart from the boss of the company).
Project
I wanted to visualize binary search trees to help understand a problem, but I couldn’t find a simple tool to take tree data as text and to output it as a line drawing. I also became interested in the problem of arranging arbitrary tree arrangements neatly, in the original breadthwise order, without overlapping and with sensible spacing between elements. So, I decided to make a tree diagram tool myself.
It may be useful as a tool to generate diagrams of tree structures for documents, presentations and so forth, so I’ve put it online.
The tool is written in pure JavaScript and creates SVGs that all modern browsers can render. This means the scripts can also be dropped directly into web applications that create tree data on the fly, as a reporting/visualization tool. The source is freely licensed under GPL and placed on GitHub.
Use
To make your own diagrams all you have to do is visit one of the demo pages and edit the data (specified in classic tabular style, e.g:
My Root
My First Child
My Grandchild
My Second Child
This will generate the diagram below:
You can edit the options (provided as editable JSON in an edit box on the page) to customize the image in various ways. For instance setting "flipXY": 1 will convert the image to a horizontal diagram.
I won’t detail all the options here because it’s designed for experimentation; just play with the values and see what you get. You can change the relative size and margins of the nodes, line spacing in the labels, arrow size and direction and more.
To change the colors or line styles of the nodes and arrows, or the label font size and style, simply edit the CSS data on the page. For instance, editing the CSS as follows…
text {
text-anchor: middle;
font-size: x-small;
fill: white;
}
rect {
fill: green;
stroke: black;
stroke-width: 0;
}
.. would result in this diagram:
Method
The diagram generator has the task of building diagrams that have elements positioned and spaced sensibly, without nodes or lines overlapping, and making the best use of available space (the nominated rectangle the diagram may occupy). Element positions need to be considered as a whole, as repositioning any element will have a knock-on effect on any other elements it might now overlap, free space to better position, and so on.
After experimentation I developed a relatively simple method with all nodes having their vertical position fixed in a level based on the distance to their tree root. The horizontal positions are in order of the breath order of the nodes in the tree, but other than that, they are allowed to move horizontally. The method relies on identifying the one level which has least potential to be repositioned, laying this out with regular spacing and fitting the other rows around it.
Relative values are given in the options for the widths of nodes and the spaces between sibling nodes (nodes that share the same parent) and cousin nodes (nodes that are the same distance from their roots but don’t share the same parent).
-
The tree structure is converted into an array of levels to be displayed in rows.
-
Each level is measured for its minimum width given the spacing ratios in the
options. -
The row that occupies the most screen width is nominated as the fixed row.
-
All rows between the fixed row up to an including the root are now considered in turn. For nodes that have children (in the level below) they are given an ideal horizontal position as the average (horizontally) of their children.
-
A ‘sweep’ process then travels left to right across the nodes and forcing the rightmost node of each considered pair further right to ensure that it is not positioned too closely to its predecessor. As this may push nodes outside the diagram area, a return sweep performs the same operation from right to left with the rightmost element constrained to the available horizontal space.
-
These positions won’t result in overlapping elements. However because of the way the sweep operates, elements will often result in nodes positioned immediately to the right of neighbours when there is a large gap remaining that could be occupied. In order to have nodes occupy the central position in the available space, a third and fourth sweep are performed in mirror-image of the first two (right to left then left to right). Naturally after sweep four the elements are often positioned immediately to the left of neighbours. So, the positions after sweep two and sweep four are averaged to determine the final position of the nodes; non- overlapping and evenly positioned in the available space.
- A similar operation is performed on all the rows below the fixed row traveling downwards. On this occasion, the ideal horizontal position for the nodes is an even distribution of children underneath, with the group centered on their parent node.
Contact
I hope some find the tool useful or interesting. Check out the site and as ever, feel free to contact me on the comments or at jimblackler@gmail.com, or make requests via the GitHub page.