Sandpile

Animates the evolution of an Abelian Sandpile on a finite two-dimensional integer lattice over discrete timesteps.

The sandpile is only one instance of an entire class of cellular automata which this project supports. The rendering and control logic is defined such that it correctly handles a generic two-dimensional cellular automaton of arbitrary finite size, so long as its transition function does not modify anything but the cell states (see Structure and CellularAutomaton.ts for more details).

Status

Project is live at: https://jamais-vu.github.io/sandpile/. Check it out!

Contents

1. Background
   1. Motivation
   2. Abelian Sandpile Model
      1. Transition Function
2. Structure
   1. General framework: Presentation-Abstraction-Control
   2. Defining a Cellular Automaton
3. Usage
   1. Usage Details
   2. View on Web
   3. Local Server
4. Future Development
   1. Parallel Programming
   2. Reflection and Rotational Symmetry
   3. Graph generalization of Sandpile grid
5. References

Background

Motivation

I became interested in the Abelian Sandpile Model and other cellular automata after finishing my first JavaScript project, an interactive Game of Life. The sandpile has a more complex transition function, and I wanted to see how much better I could do now that I had some experience with JavaScript.

I chose TypeScript because I had never used it before, and learning it felt like a natural next step after becoming comfortable with JavaScript. I'm very happy with that decision; TypeScript is great, it forces me to write clearer code and prevented many errors that would have otherwise occurred had I used JavaScript.

I also wanted to familiarize myself with mocha and chai, and get in the habit of unit testing my project code as I write it.

Abelian Sandpile Model

This section may be skipped if you're not interested in the specific dynamics of the sandpile. My implementation of the transition function is in /rules/sandpile.ts.

The Abelian Sandpile Model is a cellular automaton consisting of an n x m grid of cells. Each cell has an associated non-negative integer (the state of the cell) representing how many grains of sand are on that cell.

Each cell has up to four neighbors: the cells directly above, left, right, and below it.

Neighbors of the cell (x, y):

+------------+------------+------------+
|            | (x, y + 1) |            |
+------------+------------+------------+
| (x - 1, y) |   (x, y)   | (x + 1, y) |
+------------+------------+------------+
|            | (x, y - 1) |            |
+------------+------------+------------+

A cell on a side of the grid has three neighbors, and a cell on a corner of the grid has two neighbors. (This is in contrast to Game of Life, which defines the neighbors of a given cell to be all eight adjacent cells.)

Transition Function

In addition to the grid of cells, the Sandpile also has a transition function. The transition function uses the current (time t) state of each cell in the grid to determine the next state of the cell.

1. We add one grain to an arbitrary cell of the grid.

2. If every cell in the grid is stable (has at most three grains), then the grid as a whole is stable. In this case, the state transition is complete, and we are in the resultant state.

3. If at least one cell in the grid is unstable (has four or more grains), then the grid is unstable.¹

4. We pick an arbitrary unstable cell² and topple it: reduce its grain count by four, and add one grain to each of its neighbors. For cells which have four neighbors, this process does not alter the total count of grains in the grid; however, for cells on the sides or corners of the grid this process decreases the total count of grains in the grid. They "fall off" the edges.
   

5. When we topple an unstable cell, the grain added to each neighbor may make one or more of those neighbors also unstable. We topple these newly-unstable cells (an avalanche), which in turn may produce even more unstable cells, and so on.

6. After all that toppling, the grid will eventually be stable³. Then the transition function has finished.
   

   Click to expand transition function footnotes

   1: Technically, when we reach part (3) for the first time, there is at most one cell which could be unstable: the cell we added a grain to.
   2: The final stable state of the grid is not dependent on the order in which we topple unstable cells; i.e. toppling of cells is commutative (see Theorem 2.1 of ref [1] if you want a proof of this). In other words, a grid has only one possible final stable state, and this state is uniquely-determined as soon as the transition function adds one grain to the grid, before even a single unstable cell has been toppled.
   3: (TODO: It's intuitive to me but I'd like a simple proof to include here.)
   

So the grid is stable at each timestep — even though it may have contained an extremely-large number of unstable cells during the transition, the states it moves through during the transition are not "at" a timestep.

Structure

General framework: Presentation-Abstraction-Control

The application's entry point, script.ts, sets up the canvas and a Controller. The Controller then handles all of the application's logic, according to a Presentation-Abstraction-Control (PAC) framework:

                            User Interface
                                  |
                                  | UIEvents trigger EventListeners.
                                  | EventListeners trigger Controller method 
                                  | calls.
                                  |
                                  v
                      ------- Controller -------
Calls step methods.  |                         |  Passes CellularAutomaton
Gets grid/cells      |                         |    state to Drawing, to
  states.            |                         |    draw on canvas.
                     v                         v
            CellularAutomaton               Drawing
              (Abstraction)              (Presentation)

• Presentation: Drawing class
  • Renders gridlines and cell states on the canvas.
  • Only thing it "touches" outside itself is its given canvas rendering context.
• Abstraction: CellularAutomaton class
  • Handles transition logic of the cellular automaton.
  • Manages the complete history of the cellular automaton's state.
• Control: Controller class
  • Interface between the UI and the Presentation+Abstraction.
  • Class methods are called by EventListeners added in script.ts.
  • Calls CellularAutomaton class methods and gets CellularAutomaton state data
  • Passes CellularAutomaton state data to Drawing class methods.

Defining a Cellular Automaton

The /rules directory contains rules for specific cellular automata. Each /rules module exports a Rules object (defined in /util/types.ts, which contains the information necessary to define and draw a specific cellular automaton:

• transitionFunction - its transition function
• cellColors - a Map defining which cell states correspond to which colors
• maxInitialCellValue - whether cell states are initially 0 or randomly-populated from a range of integers

At creation, the static method Controller.createControllerFromRules() is passed a Rules object, as well as the canvas and size of cells to draw, and uses these to create a Controller which has:

• a CellularAutomaton on a grid fitted to the canvas, with the given transition function and initial cell states.
• a Drawing which uses the coloring rules of the specific cellular automaton.

This means changing which cellular automaton this application uses is as simple as changing which Rules we pass the Controller at initialization — the Controller automatically handles everything else.

Usage

You can view the animation on the web, or clone this repository and host your own HTTP server.

Usage details:

• By default, script.ts initializes the sandpile CellularAutomaton with a transition function which adds new grains to the center of the grid (rather than to a random cell).

• The demo starts paused.

• Jumping forward several thousand steps at once may take a few seconds, and jumping forward more than 10,000 steps at once may cause it to stop responding (I hope to make that faster in the future).

View on Web

• View the sandpile animation at this project's GitHub Pages deployment.
• The application is also live at Replit, but that one is not guaranteed to be up-to-date.

Local Server

Run this simulation on your computer by cloning the repository and hosting index.html on a local server.

Expand this if you want to host it locally, but are unfamiliar with how to do so.

I use the NodeJS package http-server, because it's very simple.

# In the directory where you want to save this repository
$ git clone https://github.com/jamais-vu/sandpile

# If you don't have the http-server package.
$ npm install http-server

# Navigate to the sandpile directory.
$ cd sandpile
e
# Start the HTTP server. It automatically uses 'index.html'
# The '-c-1' option disables caching (useful if you are editing the web page).
$ http-server -c-1

# When you are done, you can stop the HTTP sever by pressing Ctrl+C.

After starting the server, navigate your web browser to http://localhost:8080/index.html and you're done.

Future Development

Some cool ideas I may implement in my spare time.

Parallel Programming

Since toppling a cell in the grid only affects that cell's immediate neighbors, we can partition the grid into several subsets of cells, where any two cells in the same subset are independent (do not share neighbors). This means that, for each subset, we can simultaneously topple all cells in the subset without worrying about potential conflicts from concurrent topple processes accessing or modifying the same neighbor.

_{Partition of a 5 x 5 grid. No two cells of the same color share a neighbor.
(Image credit: P. Vahagn, P. Suren, and N. Hayk [2])}

I want to do this because it's a neat solution, and I'd like to become more familiar with parallel programming.

Status

• createVertexGroups, the function for creating independent subsets, passes tests. Have been experimenting with breaking up the transition functions to accept subsets of a grid, but I'll need to figure out how to call them in parallel to test them.

• Plan to check out Promise. I'm not clear on whether that's truly "parallel" but it may suffice. May also play around with Web Workers.

Reflection and Rotational Symmetry

_{Symmetries of the Abelian Sandpile}

When adding grains to the center, the sandpile exhibits reflection symmetry over the axes, and (on a square grid) fourfold rotational symmetry. This means we only need to consider the origin, positive x and y axes, and one quadrant; then we can transform the quadrant to create the remainder of the sandpile. This would effectively cut down the drawing iteration by 3/4, and possibly offer optimizations for computing transitions.

Status

• Not started.

Graph generalization of Sandpile grid

Instead of a two-dimensional integer lattice, where each cell has 4 neighbors, the Sandpile is represented by an undirected finite multigraph, where each vertex has an arbitrary number of neighbors. A vertex in the graph topples if its grain count is equal to or greater than its number of neighbors.

Unlike the grid, there is no "edge" for grains to fall off and be lost from the sandpile, so a single vertex is chosen to be the "sink" and does not topple no matter how many grains are placed on it.

Status

• Basic recursive implementation seems to work for very small graphs. For any graphs of an interesting size, it quickly exceeds the maximum call stack size. I like how concise the recursive implementation is, but I'm not sure there's a nice solution to avoid hitting the call stack limit, so I'm working on an iterative implementation.

• After I test that it's working, I'd like to visualize the vertices and edges, and animate transitions. That sounds like a good challenge; more complex than drawing a bunch of rectangles.

References

[1] N. Doman, "The Identity of the Abelian Sandpile Group", Bachelor Thesis in Mathematics, Faculty of Science and Engineering, University of Groningen, Groningen, Netherlands, 2020. Available: https://fse.studenttheses.ub.rug.nl/21391/.

[2] P. Vahagn, P. Suren, and N. Hayk, "The Investigation of Models of Self-Organized Systems by Parallel Programming Methods Based on the Example of an Abelian Sandpile Model", in Proceedings of CSIT 2013: 9th International Conference on Computer Science and Information Technologies, 23-27 September, 2013, Yerevan, Armenia. Available: https://csit.am/2013/proceedings.php.