Tag Archives: maths

Update: Conway’s game of life

As part of my website’s facelift I decided to update the Conway’s game of life (Live page) project. The content was rearranged to make more sense to the first time user, a the controls organised in a way that made them larger and easier to navigate. I also changed the links to different shapes to be gallery objects (similar to what I had for the Mandelbrot project.) This is also the first page to get the “You might also like…” feature at the bottom, which will soon appear on most other pages when I get time to add them.

Before and after

Conway before the update
Conway before the update
Conway after the update
Conway after the update
Conway after the update
Conway after the update

aDetector

One of the projects I have wanted to develop for a long time is a browser based particle physics experiment simulator. Such a project would generate events using Monte Carlo methods and simuate their interactions with the detector. This was made partly as an educational aid, partly as a challenge to myself, and partly because at the time I was feeling some frustration with the lack of real analysis in my job. As expected for a Javascript based CPU intensive appplication, this reaches the limits of what is possible with current technology quite rapidly.

Links

Live page V1
Live page V2
Live page V3
Live page V4
Live page V5
GitHub repository

Overview

The model for the detector is saved in an xml file which is loaded using the same methods developed in the Marble Hornets project. Particle data are currently stored in Javascript source files, but will eventually use xml as well. The particle interactions are simulated first by choosing a process (eg \(e^+e^-\to q\bar{q}\)) and then decaying the particles. Jets are formed by popping \(q-\bar{q}\) pairs out of the vacuum while phase space allows and then arranging the resulting pairs in hadrons. Bound states are then decayed according to their Particle Data Group (PDG) branching fractions, with phase space decays used. The paths of the particles are propagated through the detector using a stepwise helix propagation. Energy depositions in the detector are estimated, according to the characteristic properties of the detector components. A list of particles is then compiled based on the particles produced and these can be used to reconstruct parent particles.

The user has access to several controls to interact with the application. They can choose how to view the detector, using Cartesian coordinates and two Euler angles (with the roll axis suppressed.) The most expensive parts of the process are the generation of the event displays and the generation of the particle table. By default these are only updated after a certain interval, to allow the user to accumulate a significant number of events without being slowed down by the graphics. To save time the detector itself is rendered once in a cutaway view, and the particle tracks are overlaid on the saved image. Eventually the user will be able to get a full event display, including the detector response to the particle with glowing detector components etc.

The user has access to collections of particles, including electrons, muons, pions, kaons, photons, and protons. From these they can construct other particles, making selections as they do so. Once they have made parent particles they can then plot kinematic variables including mass, momentum, transverse moment, and helicity angle. This should, in principle, allow students to learn how to recreate particles and how to separate signal from background effectively.

Given the large amount of information available the user has access to a number of tabs which can can be collapsed out of view. This allows the user to run the application with the expensive canvas and DOM updates, and thus collect many more events.

This is still a work in progress, with reconstruction of particle being the next main priority. Eventually the user would be able to load their favourite detector geometry and beam conditions, then perform their analysis, saving the output in xml files and possible being able to upload these to a server. This would allow users to act as “players” with “physics campaigns”, including the SPS experiments, HERA experiments, B factories, LEP experiments, and LHC experiments. This is, of course, a very ambitious goal, and one which has been ongoing for over a year at this point.

See other posts tagged with aDetector.

Challenges

Challenge: A sophisticated model for the detector was needed.
Solution: The detector is split up by subdetector, with each subdetector having its own characteristic responses to different particles. The detector is split up in cylindrical coordinates, \((
ho,\eta,\phi)\), with each subdetector also being split into modules. Individual modules then react the particles for reconstruction purposes. Thus with a few key parameters even a sophisticated model can be stored in a few variables that can be tuned quickly and easily. (Resolved.)
Challenge: The detector shold have a three dimensional view that the user can control.
Solution: The detector is drawn using a wireframe with transparent panels. This is a method I developed in 2009 for a now defunct PHP generated SVG based visualisation of the BaBar electromagnetic calorimeter, which I used to show the absorbed dose as a function of detector region and time. The drawing algorithm is not perfect, as panels are drawn in order from furthest from the user to closest. This is sufficient for most purposes, but occasionally panels will intersect causing strange artefacts. Eventually this should be replaced with a much more stable, robust, and fast implementation, such as in three.js. (Resolved, to be revisited.)
Challenge: Particles should be modeled realistically and physically correctly.
Solution: Particles are modelled with the most important parameters (mass, charge, decay modes etc) taken from the PDG. Their kinematic properties are modeled using special four vector classes, and decay products “inherit” from their parents in a consistent manner. Particles at the highest layer of the tree are assigned their four momenta, and then their decay products are decayed, inheriting the boost and production vertex from their parents. This is repeated recursively until all unstable particles are decayed. So far this does not take spin into account, as everything is decayed using a phase space model. Particles with large widths have their lineshape modeled using a Breit-Wigner shape. As a result, particle have realistic looking jets and four momentum is conserved. This required the development of special libraries to handle these decays and kinematic constraints. (Resolved, to be revisited.)
Challenge: Particles decay trees must be traversed consistently.
Solution: This is harder than it sounds! Every time an event is generated, particles are recursively decayed for as long as phase space allows. The particles must then be traversed and dispalyed in the table, in a consistent manner. Ensuring that all particles are listed hierarchally without missing anything out takes some care. (Resolved.)
Challenge: Particles lists had to be prepared for the user.
Solution: The user has access to a handful of “building blocks” to play with. These are taken from the (generated) list of particles per event and filtered by the particle type. Further lists can be created or filtered from these lists, and parent particles can reconstructed from combining lists. This means having to provide special classes to handle the particles and ensure that no particles are reconstructed recursively (leading to infinite loops.) Apart from using reconstructed particles instead of generated particles, this has been resolved. (Resolved, to be revisited.)
Challenge: The user needs to be able to make histograms.
Solution: I had made histgorams for other projects, including the Reflections and Box plotter projects, so this was mostly fairly easy to do. Even so, being able to create new histograms of arbitrary scales and variables on the fly meant that this histogram class had to be more robust than previous projects. (Resolved.)

Screenshot

Screenshot of aDetector V5
Screenshot of aDetector V5

Complex polynomial

On the Numberphile YouTube channel I saw a video that gave a proof that all complex polynomials have at least one solution. The method involved moving one point about the complex plane while another is mapped around a path elsewhere in the plane. I decided to map this out using Javascript!

Links

Live page
GitHub repository

Overview

The proof states that for a reduced polynomial \(f\) of order \(n\), for values of \(u = re^{i\theta} \in \mathcal{C}, |r| \gg 1 \), the function \(z = f(u)\), \(z\in\mathcal{C}\) will take values of the order \( |z| \sim r^n\). The value of \(r\) is then slowly and smoothly reduced, as \(\theta\) is allowed to increase at a constant rate. After many iterations the value of \(z\) will tend towards a constant value, which is the constant term in the polynomial. As a result the path traced out by \(z\) will pass through the origin, giving at least one solution to the polynomial.

This is handled in Javascript by making finite steps in \(r\) and \(\theta\), with small steps in time. Both paths are animated, to show the behaviour of \(z\) as a function of \(r\) and \(\theta\). The results can be quite beautiful!

Challenges

Challenge: This project requires timed Javascript and complex number manipulationn.
Solution: Both these problems have been overcome many times before in other projects, so they weren’t a problem here! (Resolved)

Screenshot

Paths in parts of the complex plane
Paths in parts of the complex plane

Update: tricolor

Today I refactored much of the tricolor project (live page), a cellular automata simulator. It’s one of those projects that had a great scope for improvement and extension, and was actually an offshoot of the Conway’s Game of life project.

The most significant improvements were:

  • Giving the user more control over the parameters. Many new variables were added that the user can edit, including the number of “breeds” of cells, number of “families”, the size of the cells, how the play area wraps around in the \(x\) and \(y\) directions, the base health of the cells, and after how long they start to decay (a new feature.)
  • Addition of the history bar. This records the recent evolutiom of the simulation, allowing the user to see how changing the different varaibles affects the overall stability of the populations.
  • Refactoring to object oriented code. Initially the code borrowed from Conway’s Game of Life, where the history of the cells was not important. As a result the code was simply a two dimensional array of states. As the tricolor cellular automata became more sophisticated it became necessary to introduce a class to handle the cells. This simplified the code greatly.
  • The user can now view the “health” of the cells. Each cell has a health associated with it, and turning on the option to see the health clarifies where most of the changes are taking place. The regions close to the boundaries have less health, giving a dark outline. Large areas without any “food” lose health, making the decay more obvious/
  • The layout of the page was tidied up significantly. There is less whitespace and better use of existing space. There is still room for improvement though, as a single button should be used for changing all settings, and a description of all the parameters should be given. It should also be made explicit which changes of settings require the play area to be completely redrawn.

Screenshots

Sample screenshot
Sample screenshot
Example history showing transient behaviour.
Example history showing transient behaviour.

Mandelbrot explorer

This project estimates the Mandelbrot set using the HTML5 canvas. It’s one of my longest running projects that has been implemented in PHP, SVG, HTML5 canvas, HTML tables, and even in ROOT.

Links

Live page
GitHub repository

Overview

This projects presents a wide range of different challenges. The aim is to create a fractal browser that pushes the operating environment to the limit in terms of performance, while still being user friendly and responsive. In its current iteration the user clicks on the region of the fractal they wish to explore and the project zooms in to that region. The user can change the way the fractal is coloured by changing the palette its properties. They can also move from the Mandelbrot set to the corresponding Julia set. There is also the option to explore the cubic Mandelbrot set. Past iterations have included even more fractals, including Newton iterations and generalised Julia sets. However these have been removed in this iteration as they should be refactored into a separate fractal class rather than inserted by hand.

Challenges

Challenge: The algorithm must be responsive and make reasonable use of memory.
Solution: The iterations used in the algorithm can be expensive when the image approaches several hundred thousand pixels. Currently the algorithm uses a pixel object to manage the colour at a given point, and for arbitrarily large images a single pixel object is used in order to reduce the cost of creating and storing large numbers of these objects. The current iteration uses Javascript in the user’s browser, and most modern browsers deal with excessive memory usage sensibly, killing particularly bad cases. It is not desirable to cap a user’s capabulities when it comes to image size, so instead the algorithm forces the browser to fail relatively safely and without major inconvenience. Previously this project ran on PHP on a shared server, so memory use had to be monitored and was formally enforced on the server, making failure modes potentially dangerous. Once the canvas became available I switched to using it very quickly. Even so, running PHP locally overnight to generate very large images is still a sensible use of resounces. There are probably other areas where savings could be made. (Resolved, to be revisited)
Challenge: The algorithm must make reasonable use of CPU.
Solution: In many cases the fractals take several tens of thousands of iterations per pixel for several thousand pixels, leading to large CPU usage. In the context of Javascript this can cause serious performance issues for the user, affecting their whole computing experience and not just that associated with the browser session. To mitigate this the iterations are interrupted every \(100 ms\) and forced to wait for \(10 ms\) before continuing. In addition when several small canvases are populated they are pushed into a queue which is processed serially with interruptions. This reduces the impact on the user’s CPU significantly leading to much smoother performance and better response to user input. Even so, this should be revisited to make further savings and be more responsive to the user’s inputs. (Resolved, to be revisited)
Challenge: The user interface must be intuitive.
Solution: In some senses it will never be possible ot make the user interface entirely transparent, given the technical nature of the fractal’s inner workings. In spite of this the way the user navigates is relativelt straightforward, but more improvments can and should be made. (Resolved, to be revisited)
Challenge: The palettes should be easy to edit.
Solution: The asethetic properties of the fractals often depend on the choice of palette. The palette scales can be manipulated, using slders on the log scale. This solution borrows from another project being developed in parallel, and leads to an easier interpretation of the scaling and distorting of the palette scale. This method should be tested in a “focus group” style environment. The user should be able to create and store a palette from scratch with their own choice of colours stops. (Resolved, to be revisited)
Challenge: The user should be able to store fractals.
Solution: The user can currently choose to save a fractal to the server, storing the \((x,y)\) coordinates, zoom, and other factors. This uses AJAX requests with a PHP and MySQL backend, which has become fairly standard in my projects by now. This comes with the usual MySQL injection overheads and PHP safety issues. In the future, as the number of fractals in the gallery increases, the gallery should be orgainsed in some manner to reduce bandwidth and CPU usage. (Resolved, to be revisited)
Challenge: The project should support arbitrary fractals for future expansion.
Solution: At the moment the fractal algorithms are hard coded into the project. This needs to be more object oriented in the future so that other developers can contribute their own fractals. (Partially resolved, to be revisited)

Sample output

Mandelbrot explorer output
Mandelbrot explorer output

Wolfram rules

I enjoy playing with recreational mathematics and the Wolfram rules are a rich source of complex behaviour from simple rules. So I created this project to explore how the rules can lead to different patterns.

Links

Live page
GitHub repository

Overview

This project allows the user to input different rules to create different patterns. The results are displayed in an HTML table which is automatically generated. I cannot remember the motivation for using an HTML table rather than the canvas, as there are obvious disadvantages to using a table, even if it does arrange the results in a semantic manner.

Challenges

Challenge: The interface has to be relatively intuitive.
Solution: Although the interface is simple, I am not satisfied that it is intuitive enough for someone new to Wolfram rules. This may need to be revisited, with some example rules explained to show how the game works. (Resolved, to be revisited)

Sample output

A rather interesting Wolfram pattern
A rather interesting Wolfram pattern

Pebbling a Chessboard

One of the channels I follow on YouTube is called Numberphile, and they give plenty of good ideas for mathematical games. In this game the user has to move pieces around a chessboard in order to liberate “clones” from a prison. On Numberphile, they suggested playing this game using an actual chessboard, but I decided that a better way to do it would be to write my own game. So here it is.

Links

Live page
GitHub repository

Overview

The user interacts by clicking on the clones it wants to move around. In addition to this the user can create their own puzzles. Since I had already developed a lot with the canvas, this was simply a matter of using existing experience to make a game.

Challenges

Challenge: Making the weights.
Solution: Ideally the weights of the squares should be displayed when requested. In Firefox this worked fine, but not in Chrome. The reason for this is that I wanted to make a fraction line with a length proportional to the number of digits in th denominator. This meant I had to use a log10 function, but his does not exist in Chrome. After much debugging I found the problem and fixed it. This one bug prevented me from sending this page to Numberphile within a few days of making the game. (Resolved)

Sample game

A sample game of pebbling
A sample game of pebbling

Tricolor (cellular automata)

While investigating Conway’s game of life I wanted to see if I could easily extend the framework I’d developed to explore other systems. One of the more interesting cellular automata is the rock-paper-scissors system where three populations feed on each other.

Links

Live page
GitHub repository

Overview

The algorithm used to make the rock-paper-scissors cellular automata is does not seem to be well documented in an easy to obtain source, so I had to interpet much of the algorithm based on subjective descriptions. Each cells has a health which can take a value between \(0\) and \(10\). If a prey species is adjacent to its predator species then the prey species gives a health point to the predator species. When the prey species health reaches \(0\) it is replaced by a predator species. The result is that this creates spiral patterns on the canvas.

Challenges

Challenge: The algorithm needed some experimentation and tweaking to get right.
Solution: There are numerous papers and articles about how these algorithms work, but I couldn’t find a source that was explicit or that I could understand. As a result I had to create my own algorithm and tweak it until it was stable. Hopefully others users can read my code and develop it further. (Resolved)

Sample outputs

Sample 1, early in the evolution of a system
Sample 1, early in the evolution of a system
Sample 2, late in the evolution of a system
Sample 2, late in the evolution of a system

Sliders

I was playing a PuzzelScript game involving sliding blocks that i just couldn’t solve. So I wrote an algorithm to solve it.

Links

Live page
GitHub repository

Overview

The algorithm used is a simple backtracking algorithm to find the optimal solution (the one using the fewest moves.) The user can create an arbitrary puzzle for solution, and then the algorithm attempts to find solutions, giving the user progress updates as it does. Once the solution is found it’s written out for the user, and the solution is animated.

Challenges

Challenge: The algorithm itself had to be written and optimised.
Solution: Although the algorithm was relatively easy to write, there is still at least error, as it fails to find a solution for a problem in 12 steps, instead giving a solution in 13 steps. This error has yet to be found. By optimising a few steps, the algorithm was significantly improved. (Resolved, to be revisited)
Challenge: The user should be able to create their own puzzles.
Solution: This was achieved quite easily using my experience making tile based games. I used all the normal mouse event listeners. (Resolved)
Challenge: The solution is animated.
Solution: It turns out that animating the solution was relatively easy once the graphics had been made. The steps are handled using the normal window.setTimeout method. (Resolved)
Challenge: The algorithm should not max out the user’s CPU for more than 30 seconds.
Solution: Using the user’s CPU for too long causes alerts to be raised in most browsers. The algorithm takes time to sleep as it progresses using the window.setTimeout method to free up the user’s CPU from time to time. (Resolved)
Challenge: The progress is animated.
Solution: I’ve used CSS based progress bars in the past before, but this is the first time I’d animated them. The only hard part here was estimating the number of possible combinations of \(n\) moves, and then scaling the bars accordingly. (Resolved)

Screenshots

An example puzzle, animating the solution
An example puzzle, animating the solution
Dynamic status indicator
Dynamic status indicator
Automatically generated solution
Automatically generated solution