theory.txt

模拟2维沙堆效果

1. INTRODUCTION

This is additional documentation for the sandpile simulation program. 
This document describes the theory behind how the sandpile works. 
You don't need it to run the program, but you might find it interesting, 
never the less. For information on how the program works, see the 
file manual.doc.

The background story is that in '95 a fellow student and I wrote a 
report about self-organized criticality (SOC). SOC systems are 
systems that reorganize themselves depending on what their 
environment is like. If you are familiar with Conway's "Game of Life" 
you already know a simple SOC system. (SOC systems are also 
known under many other names, like "dynamic", "self-organizing", or 
"complex adaptive" systems).

We found SOC systems to be rather fascinating, so I've decided to 
publish a resume of our report, which is the document you are 
currently reading. As an example of a SOC system we made a 
sandpile simulation for DOS. Now I've modified it for Win95, and 
the source code is published as freeware for your convenience.

Please note that although I believe what this document says about 
SOC theory and sandpiles is valid, I don't guarantee it 100%. Our 
sandpile project was, after all, merely chosen as a subject for a 
report in a single-semester course in programming. Besides, I'm not 
studying mathematics or physics, but economy. Also, please don't 
blame me if the simulation program messes up your computer 
(although I would like to hear about it). You carry any risks yourself 
when using the program.

The rest of this document will explain SOC systems and sandpile 
models in more detail. Also, the close relation between SOC and 
chaos will be explained.

2. THEORETICAL BACKGROUND

I'm not quite sure of it, but I think Per Bak et. al. should have the 
credits for publishing the first article on sandpile models in 1987. 
Whether it's true or not, this article made sandpile models very 
popular.

The term "sandpile model" refers to a relatively simple model, that 
loosely resembles how a real-life sandpile behaves when you add 
grains onto it. The pile will grow higher, but at the same time the 
grains you add will fall down the sides of the pile, causing more grains 
to fall down, etc. The idea is that you can't tell exactly when a grain 
will fall down and when it will remain where it was dropped. 
However, you can derive some general rules that will apply to the 
pile as a whole (an average view, if you prefer).

The growing sandpile behaves in a certain way, based on rules from 
SOC theory. Our purpose of simulating a sandpile was not to make a 
realistic model of a real sandpile, but to make a model that can be 
used to illustrate this theory.

2.1 Informal explanation of a sandpile model

Think of an ordinary pile of sand. You start with an empty surface, 
and by dropping 1 sand grain at a time (in the same point or in 
random points) the pile will grow steadily. The interesting thing is how 
the pile behaves when it grows. Every time a new grain is added in a 
point the pile may grow unstable in that point. The higher the point is 
situated relative to the neighboring points, the more unstable the point 
will become.

If the point becomes sufficiently unstable a number of grains will fall 
off the point and onto the neighboring points. This will increase the 
neighbors' unstability, and it is possible that more grains will fall 
down. It is also possible that the grains will just stop falling.
Sometimes, the one grain that was added from the start will cause 
entire avalanches, at other times, the pile will not change at all except 
in that one point. The theory that explains why the pile behaves like it 
does, is explained below.

2.2 A theoretical explanation

As mentioned earlier, our sandpile model is a SOC system. For that 
reason I will first explain the theory of SOC systems, before 
explaining the theory of sandpile models.

2.2.1 SOC systems

SOC systems have close relations to chaotic systems, but they differ 
in that SOC systems are less chaotic.

Let's first look at chaotic systems. A chaotic system is defined in 
physics science as a dynamic system (a system that develops). 
Furthermore, the system's future state cannot be predicted with 
certainty, because the starting conditions and the rules of the 
dynamics cannot be determined with sufficient accuracy.

Allthough the starting conditions can't be determined accurately they 
will still influence how the system develops. This means that a small 
initial uncertainty grows exponentially as the system changes (for 
example over time). This in turn means that the more accurate you 
want the predictions on the system to be, the more information about 
the starting conditions and rules you need. The amount of information 
needed grows exponentially, and this often makes long-term 
predictions virtually impossible, as you just can't collect enough 
information.

In SOC systems, on the other hand, the inaccuracy of the predictions 
does not grow by an exponential law, but much slower, by a power 
law. SOC systems, as opposed to chaotic systems, have the ability 
to adjust themselves, which means that they develop on the border of 
chaos. Per Bak et. al calls this "weak chaos".

Simply spoken, the special attribute of a SOC system is that as it 
develops it organizes itself around a critical factor. If the state of an 
element in the system reaches a critical value the element will change 
its state, which in turn often will influence the state of other elements. 
One or more elements may trigger a chain reaction. After the 
elements have settled in their new state, the system is organized in a 
new way.

This is illustrated by the sandpile model. A sandpile is a dynamic 
system where many elements interact with each other. The system 
(sandpile) will at some time in its development reach and exceed a 
critical value (it will become too high or steep). A change in a system 
with a critical value (in the form of an added sand grain) may at this 
time trigger chain reactions (avalanches) which will influence the state 
of the system (the height of the various points).

2.2.2 Types of sandpile models

There are 3 main groups of sandpile models:
  Critical height model
  Critical slope model
  Critical Laplacian model

Each group of models builds on different interpretations of the local 
height function h(x,y).

The critical height model is the one we used in our project, and we 
based it on a 2D-matrix. Each point (x,y) in the matrix has a value 
h(x,y) which represents the height. If this height at any time exceeds 4 
the point will topple. This is done in the way that the height in the 
neighbor points to the north (x, y-1), south (x, y+1), east (x+1, y), 
and west (x-1, y) each are increased by 1, while the heght in (x,y) is 
decreased by 4.

The advantage of changing only these four neighbors is that it won't 
matter in which sequence you change them. This is not the case if you 
change all eight neighbors. Sandpile models in which you change only 
the four neighbors are called abelian (or commutative (?) ), and they 
make the simulation a lot easier. The abelian method is not limited to 
the critical height model, it can also be used in the two other kinds of 
models. There are other methods for updating the neighbors than the 
abelian method. However, it is often the preferred choice, for 
reasons of simplicity.

The sandgrains in this simple model can actually fall uphill. This is not 
realistic, of course, if you want the model to behave like a real 
sandpile, but that was not our purpose. Besides, the SOC principles 
are still valid.

The critical slope model more realistically resembles a real-life 
sandpile. In this model you consider the local slopes (a slope is the 
height of a point compared to its neighbor points). If a local slope 
exceeds the critical slope value in any direction, the point topples. 
Avalanches based on this model don't seem to follow a power law.

The critical Laplacian model is based on a third way of calculating 
the height. This is called the local Laplacian L(x,y), and it's calculated 
as the average difference in height to all neighbor points. The formula 
is: L(x,y) = 4h(x,y)-h(x+1,y)-h(x,y+1)-h(x-1,y)-h(x,y-1). Like 
critical height model sandpiles, avalanches in Laplacian model 
sandpiles follow a power law, but with other exponents.

2.3 A word on cellular automata