Lab 5 Diffusion Limited Aggregation
Aims
The aim of this lab is to continue our exploration of TDD in C++ by developing a simulation of diffusion limited aggregation
- Introduction to DLA simulations
- Understanding Random number classes
- Creating Image Sequences
- Using Command Line Arguments
Introduction to DLA
Diffusion-limited aggregation (DLA) is the process whereby particles undergoing a random walk due to Brownian motion cluster together to form aggregates of such particles. This theory, proposed by T.A. Witten Jr. and L.M. Sander in 1981,[1] is applicable to aggregation in any system where diffusion is the primary means of transport in the system. DLA can be observed in many systems such as electrodeposition, Hele-Shaw flow, mineral deposits, and dielectric breakdown.
The following images show a run of the demo program we are going to generate with the random walker path shown in red, the second vidoe the results from a longer run using multiple seed points.
Algorithm Outline
The Image class we developed in
Lab4 has it’s origin in the top left corner and dimensions of width and height, but stored as a series of rgba values in a numpy array.
We can use this as a map for our data values for the DLA simulation, where we use the alpha channel to store an aggregated value and the RGB values to set the pixel colours for our visualisation.
We then use the following process to run the simulation.
graph LR
A[Seed Image <br> with Pixels] -->B[Choose Walker <br> Start Position]
B -->C[check local <br>pixels]
C --> D{Found Seed?}
D -->|Yes| E[Update Image]-->B
D -->|No| F[Walk To <br> New Position]
F -->C
This will result in a situation similar to the one shown in the image below.
To choose our next position in a random walk all we need to do is choose a random integer in the range -1 -> +1 and add this to the x position, and choose a different random number for the y position. As we are not concerned about the walker path crossing this makes it much simpler.
For this simulation we are going to generate a simple class as it helps with our C++ practice, however for something as simple as this we may not always need to use a class
classDiagram
class Image {
-int _width
-int _height
-np.ndarray _rgba_data
+width: int
+height: int
+pixels: np.ndarray
+shape: tuple[int, ...]
+__init__(width: int, height: int, fill_colour: Union[rgba, tuple, None])
+set_pixel(x: int, y: int, colour: rgba)
+get_pixel(x: int, y: int) Tuple[int, int, int, int]
+clear(colour: rgba)
+save(name: str)
+line(sx: int, sy: int, ex: int, ey: int, colour: rgba)
+rectangle(tx: int, ty: int, bx: int, by: int, colour: rgba)
+__getitem__(key: tuple[int, int]) rgba
+__setitem__(key: tuple[int, int], colour: rgba)
}
class DLA {
+width: int
+height: int
+image: Image
+__init__(width: int, height: int)
+random_seed(): None
+save_image(filename: str): None
- _random_start(): tuple[int, int]
+walk(): bool
+finalize_image(): None
}
DLA o-- Image
Simulation loop
Once we have our Walker class generated we need to use it in main.cpp to do our simulation. The basic loop will look like this and is similar to a game loop.
graph LR
A[setup walker] -->B[Seed image]
B --> C{Step<br>Sim}
C -->|Finished| D[EXIT]
C -->|update| E{Found<br>point}
E -->|yes| f[Save Image]
E -->|no| h[reset walker<br>start]
h -->C
f-->C
Getting Started
As the Image and RGBA class have already been tested in the previous labs we can just use them, we are also not going to use a TDD approach for this session as the Walker class will be creating a visual output we can use for debugging.
To start with we will generate a new folder in our labs GitHub repo.
uv init DLA
cd DLA
As we want to use the Image class we used in the previous examples we need to add it to our pyproject.toml file. We need to add this manually as the Image class is not on PyPI.
dependencies = [
"image"
]
[tool.uv.sources]
image = { path = "../Lab4/Image" }
Command line arguments
Command line arguments allow us to modify how the program runs by using command line options. In Python, the standard library for this is argparse.
The argparse module makes it easy to write user-friendly command-line interfaces. The program defines what arguments it requires, and argparse will figure out how to parse those out of sys.argv. The argparse module also automatically generates help and usage messages.
Here is an example of how to use argparse to get the width and height for our DLA simulation.
import argparse
import sys
def main():
# create a parser object
parser = argparse.ArgumentParser(description="Simple DLA simulation")
# add arguments
parser.add_argument("--width", "-w", type=int, default=200,
help="image width in pixels")
parser.add_argument("--height", "-h", type=int, default=200,
help="image height in pixels")
# parse the arguments from the command line
args = parser.parse_args()
# get the values
width = args.width
height = args.height
print(f"Creating DLA with width={width} and height={height}")
# Now we can create our DLA instance
# dla = DLA(width, height)
# ... rest of the simulation code
if __name__ == "__main__":
main()
To run this code, you would save it as a Python file (e.g., dla_sim.py) and execute it from your terminal:
# Run with default values
python dla_sim.py
# Run with custom width and height
python dla_sim.py --width 500 --height 500
# Get help
python dla_sim.py --help
This will produce the following output for the help command:
usage: dla_sim.py [-h] [--width W] [--height H]
Simple DLA simulation
optional arguments:
-h, --help show this help message and exit
--width W, -w W image width in pixels
--height H, -h H image height in pixels
Lets Play
The good thing about doing simulations is once they are working you can play and experiment to see what happens. Here are some ideas to add to you code and “play”
Add more command line options.
My demo has the following options, try and add them to your argparse setup.
usage: dla.py [-h] [-w WIDTH] [-H HEIGHT] [-i ITERATIONS] [-f FILENAME]
[-p PATH] [-e EXT] [-t IMAGESTEP] [-s SEEDS]
Simple DLA simulation
optional arguments:
-h, --help show this help message and exit
-w WIDTH, --width WIDTH
image width (default: 200)
-H HEIGHT, --height HEIGHT
image height (default: 200)
-i ITERATIONS, --iterations ITERATIONS
number of simulation iterations (default: 1000)
-f FILENAME, --filename FILENAME
Basefilename for saving (default: image)
-p PATH, --path PATH path to prepend to file (default: ./)
-e EXT, --ext EXT image file extension (default: png)
-t IMAGESTEP, --imageStep IMAGESTEP
how many steps before saving an image (default: 10)
-s SEEDS, --seeds SEEDS
number of seeds (default: 1)
Think of other elements you can add to this and add them.
Adding colour
This page has many examples showing different coloured versions of the DLA. Try to change the colour over time when adding the particles.
Using different seeds
At present we have a single seed point (or multiple single seeds), trying lines and other elements as the seed points.
Random sticking
At present we always stick to a point and we use the alpha value trigger of 255 to say there is an value present. We could accumulate over longer values (for example add each time we encounter) but only add when a certain threshold is found. We could use a random value to say if the particle sticks or not.