Conway’s game of life

Conway’s game of life is a very famous mathematical model with a rich variety of “creatures” that can interact with one another. This script is a simple interactive sandbox where the user can “paint” cells to create different shapes. There are a number of predefined boards that the user can choose to investigate some small and interesting patterns as they evolve.

Overview

The underlying mathematics is very simple. Conway’s game of life follows three simple rules:

1. A dead cell comes to life if there are three adjacent cells which are alive.
2. A living cell dies if there are fewer than two adjacent cells which are alive.
3. A living cell dies if there are more than three adjacent cells which are alive.

This is achieved by simply iterating over the board where each cell has two possible states (dead/alive) as well as the state from the previous turn. This procedure is then wrapped up in a series of window.setTimeout calls to allow the board to evolve.

Challenges

Challenge: The user must be able to paint cells to make shapes. The interaction must match the underlying grid.
Solution: Overcoming this challenge was largely a matter of seamless performance as well as correct handling of events. This was surprisingly straightforward given the lack of cross browser support for finding the cursor position. (Resolved)
Challenge: Ideally this should be an infinite sandbox.
Solution: After toying with the idea of an unlimited size of board the stretches to match the user’s patterns it was decided that this would be unfeasible. As the size of the board increases (for example, due to gospel gliders moving off to infinity) the amount of memory required to contain the game would increase to dangerous levels. In addition the splicing of additional columns (and to a lesser extent, rows) of the board would incur a significant CPU cost. The board is sufficiently large for most interesting patterns. (Resolved)
Challenge: Saving patterns with markup.
Solution: One of the most useful features was for users to be able to share their patterns with other people. To do this there is a link which automatically updates, storing the current board as a string as a url argument. This is then parsed, which turned out to be quite simple, and centred on the board. (Resolved)

Sample output

The gospel glider gun:

Box filler

This is a rather frivolous script I wrote to serve some sort of purpose, but I forget exactly what that purpose was. I think it may have been to create a random sitemap using images from various pages. It takes rectangular array of squares and fills it with squares (or boxes) of random sizes. Then to make it look more attractive it fills each rectangle with a picture from placekitten.

Challenges

Challenge: The only real challenge here is to make sure none of the squares end up more than one box.
Solution: This challenge is overcome by choosing a square at random which has not yet been used, then finding the largest possible box size starting from that square, $$n$$. A random number is thrown in the range $$1,n$$ to determine the box size. Each square which fits in this box has it status changed to “used”. This process is repeated until all squares are accounted for. (Resolved)

Lots of kittens:

Box plot maker

One of the most popular ways to compare results in particle physics is to create plots that show different results with horizontal bands (sometimes known as boxes), making comparisons easier on the eye. Unsatisfied with the quality of available solutions at the time, I created my own scripts which would make these plots for use in my thesis.

Overview

The tool allows the user to create a plot in several steps. Each entry can be styled quickly and simply, and bands can also be added around different groups of results. The user can specify up to three uncertainties (for example, statistics, systematic, and theoretical) which can be asymmetric. The output is an SVG document, giving a very clean and slick image that scales well. Unfortunately this is not as well suited for creating bitmaps, and also relies on server side (PHP) scripting.

Challenges

Challenge: The axis must be generated dynamically, ensuring that the range looks sensible and attractive.
Solution: Through some cunning mathematics the range is automatically chosen, with a suitable precision. Since the aim is to make the comparison by eye of different results easy the precision is less important than giving a good sense of scale, so fewer tick marks are preferred. (Resolved)
Challenge: It’s currently not possible to enter a block of text to create an image.
Solution: Add a textarea to input user defined text and a parser to read this input. This would benefit greatly from a simple custom markup language. (To be done)
Challenge: It would be nice to have an output to HTML canvas.
Solution: Since the SVG is already written, it would be easy to write to canvas as well. This would require rewriting the code in Javascript, which is relatively straightforward to do. If there is demand from the particle physics community I will spend some time refactoring the code. (To be done)

Sample output

Image from the conclusion my thesis:

$$Z$$ boson width:

$$X(3872)$$ mass:

One of my hobbies is creating fractals and one of the most interesting is the Apollonian gasket. An area defined by some arcs and straight lines is recursively filled with circles and in all cases (except the trivial case of a single circle) this process recurses infinitely, making counting circles challenging.

Overview

Circles and lines are defined in much the same way (with lines having an infinite radius, and vanishing inverse radius) and from this point lines will be referred to as circles. There is then a relatively straightforward relationship between the position of a circle and the three circles/lines which enclose it. For three circles $$[c_1,c_2,c_3]$$ that enclose a circle $$c_4$$, the radii are related by:

$r_4 = \frac{r_1r_2r_3}{r_1r_2+r_2r_3+r_3r_1+2\sqrt{r_1r_2r_3(r_1+r_2+r_3)}}$

where $$r_i$$ is the radius of the $$i$$th circle. The centres of the circles, $$(x_i,y_i)$$ for the $$i$$th circle, are related by:

\begin{eqnarray*}
A_{12} & = & x_1^2 – x_2^2 + y_1^2 – y_2^2 + (r_2+r_4)(r_2+r_4) – (r_1+r_4)(r_1+r_4) \\
A_{13} & = & x_1^2 – x_3^2 + y_1^2 – y_3^2 + (r_3+r_4)(r_3+r_4) – (r_1+r_4)(r_1+r_4) \\
B_{12} & = & 2(x_2-x_1) \\
B_{13} & = & 2(x_3-x_1) \\
C_{12} & = & 2(y_2-y_1) \\
C_{13} & = & 2(y_3-y_1) \\
x_4 & = & \frac{A_{12}C_{13}-A_{13}C_{12}}{B_{13}C_{12}-B_{12}C_{13}} \\
y_4 & = & -\frac{A_{12}B_{13}-A_{13}B_{12}}{B_{13}C_{12}-B_{12}C_{13}}
\end{eqnarray*}

Three circles used to create a new circle are known as a triplet. Each time a new circle is created from a triplet this introduces three new “holes” in which additional circles can be added. The three new triplets associated with these holes are then $$[c_1,c_2,c_4],[c_2,c_3,c_4],[c_3,c_1,c_4]$$.

Challenges

Challenge: The first challenge faced was to correctly reconstruct a new circle from a given triplet. There is a degenerate case where the centres of the circles in a triplet are collinear and none of the circles contains another circle. A degenerate collinear triplet can never emerge if the first triplet is not a degenerate collinear triplet.
Solution: The equations given above always find a new circle for a given triplet. Degenerate collinear triplets are ignored. (Resolved)
Challenge: As triplets are processed this introduces new triplets. These can lead to a few problems, including runaway memory and CPU usage, as well as the algorithm never completing one part of the gasket before moving on to another.
Solution: There is a limit on the number of circles that can be produced. There is a stack of triplets and new triplets are added to this. As triplets are processed, they get removed from the stack. In this way the gasket can be filled uniformly, removing triplets keeps memory usage low, and the limit on the number of circles stops the algorithms before CPU use becomes an issue. The result is an image where some areas may look sparsely populated. This algorithm should be revisited to make it more robust. (Resolved, to be revisited.)

Sample output

A initial triplet of circles:

An initial triplet of lines:

ASCII art generator

After talking to a friend who suggested I write a text based adventure game I decided could use a way to generate graphics that could be displayed as text. To achieve this I used the HTML canvas to analyse images and comapared the distribution of colours with various characters, providing graphical, textual, and HTML outputs.

Overview

The tool allows the user to choose various character sets for processing the images, including particles for images related to particle physics. The user can also choose which display modes to use, including “colour”, “black and white”, “red green, and blue”, “pixelate”, “Matrix”.

There are two rules for determining which characters to use, which are “parsimony”, and “random”. Parsimony chooses a single character of a single colour that best matches the local pixels.

Strategy

The source image is divided into rectangles of equal size. The rectangles are then painted to a canvas one by one, and the pixel colours analysed to define a single characteristic colour for the rectangle depending on the mode used. (For example, when the mode is “black and white” the characteristic colour is $$(\bar{r}+\bar{g}+\bar{b})/3$$, where $$\bar{r}$$ is the average red value of the pixels, and similarly for green and blue.)

For each rectangle each character is tested one by one to find the best match between the pixels in the source image and those in the character using the characteristic colour. To find the character with the best match a parsimony parameter, $$p$$, is defined as the sum of the squares of the differences between the rgb values of the pixels between the character and the source image. The character with the smallest value of $$p$$ is chosen. The expression for $$p$$ is:

$$p = \sum_i \left[ (r_i^s-r_i^c)^2 + (g_i^s-g_i^c)^2 + (b_i^s-b_i^c)^2 \right]$$

where $$r_i^s(c)$$ is the r value of the $$i$$th pixel in the source image (character), and similarly for green and blue.

This character then gets drawn to a large canvas for graphical output, added to a span element for textual output, and added to a textarea element for HTML output.

Challenges

Challenge: The versatility of the tool is limited by the same origin policy restrictions, meaning that currently users can only download image generated from sources files on the same server.
Solution: Create a secure and reliable service for uploading images to a temporary directory on the server. (To be done)
Challenge: In textual output, the font spacing requires tweaks depending on the browser used.
Solution: Edit the CSS to ensure consistent display of text between different clients. (To be done)
Challenge: For large images and large character sets the processing can cause the browser to freeze up and issues warnings.
Solution: The processing is split into “spurts” which consist of a fixed number of steps each. The window.setTimeout method is used to moderate the CPU load. (Resolved)

Sample input and output

Source image:

Normal settings (colour mode, integers character set, parsimony rule):

Different modes:

Different character sets:

Random rule:

print ‘Hello world!’

This is a blog where I summarise the various computing, graphics, and video projects I’ve worked on, from the small and frivolous to the vast and powerful.