Phoenix’s tech blog

Let’s go back in time - do you remember sand simulator thing I wrote several months ago? I decided to tell more about it, mostly about internals and physics solver (here, and from now on, solver means the program that actually calculates the physics).

In case you have missed the post earlier, Sand And Below (SAB) is a sand simulator, kind of like Falling Sand Game (FSG). Except this is totally different solver, and I didn’t add iteration between different elements, like in FSG. Also it is in a way similar to Burning Sand game.

I didn’t really get to finish it, but I’ve made several test versions, which allow to play around with walls, concrete, water, cement, acid, sand, and ground/dirt. Last one also adds air, but it acts wrong really.

First of all, what are these sand games are about? Of course they are not about simulating particles with real physics parameters, because doing so would lag hard starting with 3000 particles (in best case!). These games, on other hand, can easily sustain 500000 to 1000000 particles, without causing major lag. (SAB @ 800×600 and 400000 particles runs at 30 fps).

The solution is to use a kind of a hack, we don’t simulate actual pieces, we create two dimensional array, where each cell specifies if there is a sand in current spot, or there is none, and we simulate/iterate through the array using specific set of rules.

The solver used in Sand And Below is my own FastSAB solver, which I think was not used anywhere before (I mean the same, or look-alike solvers). If you see similar stuff, e-mail me.

There are several versions of SAB available, you might want to try them all (each has some advantages):

FastSAB has these features:

Minuses:

Advantages over some other solvers (for example FSG):

So, lets start with the solver itself! I wrote SAB in Delphi, so all of the code here will be in Delphi. Don’t worry, it’s not hard, think of it as of psuedo code. (Small cheat-sheet: boolean = bool; integer = int; record = struct; array[…] = […])

First of all, there are 2 static arrays, used as source of data for the solver, and they fully define current state (apart from substance data):
//Sand array - the heart of engine. A = Type; Active - Physics enabled (dynamic! this is changed in realtime, to lighten up calculations)
Sand : array[0..W,0..H] of record A : Integer; Active : Boolean; end;
//If this is a solid wall
Solid : array[0..W,0..H] of Boolean;
This should speak for itself.

There is also helper array that shows whether sand was processed during the frame (you will see why you need it later)
//Was this sand cell processed already?
ID : array[0..W,0..H] of Boolean;

Then we define substances. First version had them in a static array, so for simplicity we are looking on first version.
//Everything is in special units
//Friction is 0..8, everything else makes it go crazy
//Void Sand Water Concr. Cement Acid Dirt
const Colors : array[0..6] of Integer = ($000000, $AFAF00, $0000AF,$4F4F4F,$AFAFAF,$00AF00,$7F3F00);
Friction : array[0..6] of Integer = (0 , 2 , 8 , 0 , 0 , 8 , 1 );
Density : array[0..6] of Integer = (0 , 200 , 100 , 50 , 150 , 50 , 250 );
Liquid : array[0..6] of Boolean = (False , False , True , False , False , True , False );
 
const DissolveTable : array[0..6,0..6] of Integer =
//Void Sand Water Concr. Cement Acid Dirt
((0 ,0 ,0 ,0 ,0 ,0 ,0 ), //Void
(0 ,0 ,0 ,0 ,0 ,0 ,0 ), //Sand
(0 ,500 ,0 ,0 ,100 ,0 ,300 ), //Water
(0 ,0 ,0 ,0 ,0 ,0 ,0 ), //Concrete
(0 ,0 ,0 ,0 ,0 ,0 ,0 ), //Cement
(0 ,100 ,50 ,100 ,20 ,0 ,150 ), //Acid
(0 ,0 ,0 ,0 ,0 ,0 ,0 ));//Dirt

Dissolve table is used when comparing elements for dissolving. The number is literally equal to chance of dissolving, the more - the less chance. It is used as DissolveTable[dissolver,other_substance].
Liquid - invokes extra calculations.
Density - compared against each other, things with lower density stay “on top” of other substance
Friction - explained below
Colors - nice colors =)

There is single function that processes the data, I called it PhysicsStep0 =D. It goes in 6 steps, and is executed 4 times per frame (original version had one frame each 25ms, fixed framerate). 6 steps are:

Let’s see source code of each step (added comments on most of lines):
Step 1 (determine active sands)

//Iterate through all sand
for x := 1 to High(Sand)-1 do
for y := 1 to High(Sand[0])-1 do begin
//Initially inactive
ID[x,y] := False;
//First check, if there are different sands around (not same type)
Sand[x,y].Active := not((Sand[x-1,y].A = Sand[x,y].A) and (Sand[x,y+1].A = Sand[x,y].A) and
(Sand[x+1,y].A = Sand[x,y].A) and (Sand[x,y-1].A = Sand[x,y].A));
//Second check, if there is something that cant dissolve it around, and not air
if Sand[x,y].Active and ((DissolveTable[Sand[x,y].A,Sand[x-1,y].A] = 0) and
(DissolveTable[Sand[x,y].A,Sand[x+1,y].A] = 0) and
(DissolveTable[Sand[x,y].A,Sand[x,y-1].A] = 0) and
(DissolveTable[Sand[x,y].A,Sand[x,y+1].A] = 0) and
(Sand[x-1,y].A > 0) and
(Sand[x+1,y].A > 0) and
(Sand[x,y-1].A > 0) and
(Sand[x,y+1].A > 0)) then
Sand[x,y].Active := False;
end;

Step 2 - gravity & liquid physics

//If there is where to fall
if (not ID[x,y]) and (not ID[x,y+1]) and (Sand[x,y+1].A = 0) then begin
Sand[x,y+1] := Sand[x,y];
Sand[x,y].A := 0;
ID[x,y] := True;
ID[x,y+1] := True;
end;
 
//If it's liquid
if Liquid[Sand[x,y+1].A] and (not ID[x,y]) and (not ID[x,y+1]) and (Sand[x,y+1].A > 0) then begin //Liquid physics
//Go through the sand, by comparing density
if (Density[Sand[x,y].A] > Density[Sand[x,y+1].A]) and (Random(5) = 0) then begin
K := Sand[x,y+1].A;
Sand[x,y+1] := Sand[x,y];
Sand[x,y].A := K;
ID[x,y] := True;
ID[x,y+1] := True;
end;
end;


Step 3 - dissolving

if (DissolveTable[Sand[x,y].A,Sand[x,y+1].A]) > 0 then begin
if (Random(DissolveTable[Sand[x,y].A,Sand[x,y+1].A]) = 0) then begin
Sand[x,y+1].A := 0;
end;
end;
 
if (DissolveTable[Sand[x,y].A,Sand[x,y-1].A]) > 0 then begin
if (Random(DissolveTable[Sand[x,y].A,Sand[x,y-1].A]) = 0) then begin
Sand[x,y-1].A := 0;
end;
end;
 
if (DissolveTable[Sand[x,y].A,Sand[x+1,y].A]) > 0 then begin
if (Random(DissolveTable[Sand[x,y].A,Sand[x+1,y].A]) = 0) then begin
Sand[x+1,y].A := 0;
end;
end;
 
if (DissolveTable[Sand[x,y].A,Sand[x-1,y].A]) > 0 then begin
if (Random(DissolveTable[Sand[x,y].A,Sand[x-1,y].A]) = 0) then begin
Sand[x-1,y].A := 0;
end;
end;


Pretty self-explaining - if any of neighbour pixels can dissolve us, throw a “dice” (random), and see if we need to remove this sand.

Step 4 - friction

//Friction
F := Friction[Sand[x,y].A] - Random(Friction[Sand[x,y].A] div 4);

Step 5 - movement
The longest step

if (not ID[x,y]) then begin
//If this sand was not processed. Select random direction of movement
K := Random(3); //Move left or right or dont move at all
L := (x-f >= 0) and (not ID[x-F,y]) and (Sand[x-F,y].A = 0); //Can move left?
R := (x+f <= High(Sand)) and (not ID[x+F,y]) and (Sand[x+F,y].A = 0); //Can move right?
 
if (K = 0) then begin //Fix direction 0 (left)
if (not L) and (R) then K := 1;
if (not L) and (not R) then K := -1; //Cant move
end;
if (K = 1) then begin //Fix direction 1 (right)
if (not R) and (L) then K := 0;
if (not R) and (not L) then K := -1; //Cant move
end;
 
//Priorities - sometimes sand has priority of moving into one direction than other. This happens on edges (as checked here)
if (x-f >= 0) and (Random(2) = 0) and (not ID[x-F,y+1]) and (Sand[x-F,y+1].A = 0) and (R) then begin //Priority to move left/down
K := 0;
end;
if (x+f <= High(Sand)) and (Random(2) = 0) and (not ID[x+F,y+1]) and (Sand[x+F,y+1].A = 0) and (L) then begin //Priority to move right/down
K := 1;
end;
 
if (x-f >= 0) and (K = 0) and (Sand[x-F,y].A = 0) then begin //Move left
Sand[x-F,y] := Sand[x,y];
Sand[x,y].A := 0;
ID[x-F,y] := True;
ID[x,y] := True;
end;
if (x+f <= High(Sand)) and (K = 1) and (Sand[x+F,y].A = 0) then begin //Move right
Sand[x+F,y] := Sand[x,y];
Sand[x,y].A := 0;
ID[x+F,y] := True;
ID[x,y] := True;
end;
if (K = -1) then begin //If we did not move, still process
ID[x,y] := True;
end;
end;


Step 6 - boundary wall

//By default there is one. This code "removes" it.
if not Borders then begin //Borders disabled?
for X := 1 to High(Sand)-1 do begin
Sand[x,High(Sand[0])-1].A := 0;
Sand[x,1].A := 0;
end;
for Y := 1 to High(Sand[0])-1 do begin
Sand[High(Sand)-1,y].A := 0;
Sand[1,y].A := 0;
end;
end;


You can find full source code here: http://fileserver.forest-tm.com/sand/FastSAB.txt

Rendering
Nothing much to say here, except I used blur in all versions, and differently colored pixels in newer version (it’s easy, just put it in sand structure). There is also simple dynamic lighting, very slow too (because rendering is per-pixel, not using any hardware acceleration, except for outputting the pixel buffer). Well, jet the screenshots speak for themselves:

More on rendering engine later, if you want (because it has nothing to do with the solver, it’s just working with 2d graphics, per-pixel =) )