
Percolation Simulation

This is a simulation of aspects of mathematical percolation theory.

For other percolation simulations, see Category:Percolation Simulations, or:
1D finite grid simulation
Mean run density 
2D finite grid simulations
Site percolation | Bond percolation | Mean cluster density

Given an 



M
×
N


{\displaystyle M\times N}

 rectangular array of cells numbered 




c
e
l
l

[
0..
M
−
1
,
0..
N
−
1
]


{\displaystyle \mathrm {cell} [0..M-1,0..N-1]}

, assume 



M


{\displaystyle M}

 is horizontal and 



N


{\displaystyle N}

 is downwards. Each 




c
e
l
l

[
m
,
n
]


{\displaystyle \mathrm {cell} [m,n]}

 is bounded by (horizontal) walls 




h
w
a
l
l

[
m
,
n
]


{\displaystyle \mathrm {hwall} [m,n]}

 and 




h
w
a
l
l

[
m
+
1
,
n
]


{\displaystyle \mathrm {hwall} [m+1,n]}

; (vertical) walls 




v
w
a
l
l

[
m
,
n
]


{\displaystyle \mathrm {vwall} [m,n]}

 and 




v
w
a
l
l

[
m
,
n
+
1
]


{\displaystyle \mathrm {vwall} [m,n+1]}



Assume that the probability of any wall being present is a constant 



p


{\displaystyle p}

 where

 



0.0
≤
p
≤
1.0


{\displaystyle 0.0\leq p\leq 1.0}


Except for the outer horizontal walls at 



m
=
0


{\displaystyle m=0}

 and 



m
=
M


{\displaystyle m=M}

 which are always present.

The task

Simulate pouring a fluid onto the top surface (



n
=
0


{\displaystyle n=0}

) where the fluid will enter any empty cell it is adjacent to if there is no wall between where it currently is and the cell on the other side of the (missing) wall.

The fluid does not move beyond the horizontal constraints of the grid.

The fluid may move “up” within the confines of the grid of cells. If the fluid reaches a bottom cell that has a missing bottom wall then the fluid can be said to 'drip' out the bottom at that point.

Given 



p


{\displaystyle p}

 repeat the percolation 



t


{\displaystyle t}

 times to estimate the proportion of times that the fluid can percolate to the bottom for any given 



p


{\displaystyle p}

.

Show how the probability of percolating through the random grid changes with 



p


{\displaystyle p}

 going from 



0.0


{\displaystyle 0.0}

 to 



1.0


{\displaystyle 1.0}

 in 



0.1


{\displaystyle 0.1}

 increments and with the number of repetitions to estimate the fraction at any given 



p


{\displaystyle p}

 as 



t
=
100


{\displaystyle t=100}

.

Use an 



M
=
10
,
N
=
10


{\displaystyle M=10,N=10}

 grid of cells for all cases.

Optionally depict fluid successfully percolating through a grid graphically.

Show all output on this page.




package require Tcl 8.6
 
# Structure the bond percolation system as a class
oo::class create BondPercolation {
    variable hwall vwall cells M N
    constructor {width height probability} {
	set M $height
	set N $width
	for {set i 0} {$i <= $height} {incr i} {
	    for {set j 0;set walls {}} {$j < $width} {incr j} {
		lappend walls [expr {rand() < $probability}]
	    }
	    lappend hwall $walls
	}
	for {set i 0} {$i <= $height} {incr i} {
	    for {set j 0;set walls {}} {$j <= $width} {incr j} {
		lappend walls [expr {$j==0 || $j==$width || rand() < $probability}]
	    }
	    lappend vwall $walls
	}
	set cells [lrepeat $height [lrepeat $width 0]]
    }
 
    method print {{percolated ""}} {
	set nw [string length $M]
	set grid $cells
	if {$percolated ne ""} {
	    lappend grid [lrepeat $N 0]
	    lset grid end $percolated 1
	}
	foreach hws $hwall vws [lrange $vwall 0 end-1] r $grid {
	    incr row
	    puts -nonewline [string repeat " " [expr {$nw+2}]]
	    foreach w $hws {
		puts -nonewline [if {$w} {subst "+-"} {subst "+ "}]
	    }
	    puts "+"
	    puts -nonewline [format "%-*s" [expr {$nw+2}] [expr {
		$row>$M ? $percolated eq "" ? " " : ">" : "$row)"
	    }]]
	    foreach v $vws c $r {
		puts -nonewline [if {$v==1} {subst "|"} {subst " "}]
		puts -nonewline [if {$c==1} {subst "#"} {subst " "}]
	    }
	    puts ""
	}
    }
 
    method percolate {} {
	try {
	    for {set i 0} {$i < $N} {incr i} {
		if {![lindex $hwall 0 $i]} {
		    my FloodFill $i 0
		}
	    }
	    return ""
	} trap PERCOLATED n {
	    return $n
	}
    }
    method FloodFill {x y} {
	# fill cell
	lset cells $y $x 1
	# bottom
	if {![lindex $hwall [expr {$y+1}] $x]} {
	    if {$y == $N-1} {
		# THE bottom
		throw PERCOLATED $x
	    }
	    if {$y < $N-1 && ![lindex $cells [expr {$y+1}] $x]} {
		my FloodFill $x [expr {$y+1}]
	    }
	}
	# left
	if {![lindex $vwall $y $x] && ![lindex $cells $y [expr {$x-1}]]} {
	    my FloodFill [expr {$x-1}] $y
	}
	# right
	if {![lindex $vwall $y [expr {$x+1}]] && ![lindex $cells $y [expr {$x+1}]]} {
	    my FloodFill [expr {$x+1}] $y
	}
	# top
	if {$y>0 && ![lindex $hwall $y $x] && ![lindex $cells [expr {$y-1}] $x]} {
	    my FloodFill $x [expr {$y-1}]
	}
    }
}
 
# Demonstrate one run
puts "Sample percolation, 10x10 p=0.5"
BondPercolation create bp 10 10 0.5
bp print [bp percolate]
bp destroy
puts ""
 
# Collect some aggregate statistics
apply {{} {
    puts "Percentage of tries that percolate, varying p"
    set tries 100
    for {set pint 0} {$pint <= 10} {incr pint} {
	set p [expr {$pint * 0.1}]
	set tot 0
	for {set i 0} {$i < $tries} {incr i} {
	    set bp [BondPercolation new 10 10 $p]
	    if {[$bp percolate] ne ""} {
		incr tot
	    }
	    $bp destroy
	}
	puts [format "p=%.2f: %2.1f%%" $p [expr {$tot*100./$tries}]]
    }
}}