Diffusion-limited aggregation homework
This homework assignment is a little different from the bioinformatics-oriented exercises that we've done previously.
It involves simulating a random process of growth, that is similar to some models of the growth of bacterial colonies, but also turns up in physics (materials, crystals and other areas).
The purpose of the assignment is to simulate (with Python) this basic lattice model of stochastic physics
and to generate image(s) and animation(s) of the process.
The animations are an optional extra - currently for the Python implementation, there are no instructions on animations; if you can find a way to do them, however, extra points for that!
In completing the assignment, you will gain experience using Python objects and generating graphics from Python,
as well as exposure to a very simple biophysics model for molecular dynamics.
The basic description of the model, diffusion-limited aggregation, can be found on Wikipedia:
A summary is as follows:
It is suggested that you use one pixel per grid cell when generating your images of the grid. You should develop your code with a small grid (50 x 50 or 100 x 100), though your final images/movies can involve larger images.
- The simulation takes place on a 2D lattice or grid.
- A fixed particle is first placed at the center of the grid.
- A free particle is then released at a random position on the edge of the grid.
- The free particle performs a random walk: at each step, it randomly tries to move left, right, up or down one cell on the grid.
- If the destination cell is empty, the move is successful and the particle attempts another move (and another, and another...)
- If the destination cell is beyond the bounds of the grid, the move fails and another move is attempted.
- If, at any point, the free particle tries to move into the cell containing the fixed particle, then it does not move, but instead "sticks": it becomes a fixed particle itself, and another free particle is released from the edge of the grid.
- The simulation terminates as soon as a free particle "sticks" (i.e. becomes fixed) in a cell at the edge of the grid.
You will be graded on the correctness, efficiency and readability of your code, and on the general grooviness of your images.
You are encouraged to play with the parameters of the model, and experiment with variations. The highest grade you can get without any variations is 80, and exceptionally interesting variations can get you up to 110.
Example variations might include:
You will turn in a compressed file containing:
- seeing what happens if, instead of the free particle "sticking" as soon as it bumps into a fixed particle, it occasionally "rebounds" with some probability.
- color-coding the fixed particles according to some criteria (time of release, duration of drift, distance from center...)
- graph number of random moves needed before making an encounter vs. number of stuck particles already present, using data from several runs.
- document any observed effects from different random number generators (you have to go dig up more than just the
- release multiple particles at once, maybe allow them to stick to each other.
- release particles according to a Gaussian or other distribution along the edge rather than a uniform one (i.e., particles are more likely to be released from the middle of a given edge than either end [i.e., a corner], with probabilities distributed according to some non-uniform distribution).
- Code that implements the most basic algorithm (you can use the same color for each pixel, or a random color). This should be called hw10_simple.py, and take two arguments:
- The size of the grid on which to run the algorithm (i.e. 80 means an 80x80 grid)
- The name of the output file. You should output an uncompressed png image to this filename. i.e.
$ python hw10_simple.py 99 out.png
would produce something that looks like this: .
- (Optionally, for >80 pts) Code that elaborates on the basic algorithm. Turn in this final code as hw10_final.py.
- (Optionally, if you did the above) A word processed document that explains the changes you made, and the significance/implications of the results.
- (Optionally, if you did the above) Interesting images/movies, the source of which should be explained in the word processed document.
Implementation, hints, and tips.
There are a number of tools you can use to generate images and movies - some of it you may have to explore yourself. Here are some tools you can use:
- The Python Imaging Library and the associated Image module. You'll want to look into the documentation from the front page. The Image module has ways of generating an image file and reading pixel data into it.
- TO INSTALL THE PIL: Go to the linked webpage above.
- Windows: Click on the link for
PIL 1.1.7 for Windows for your version of Python. If you're not sure which version you have installed, open a shell and type in
>>> help(). It should then say, "Welcome to Python 2.X!" with your version number there. Run the file.
- Mac: Click on the link where it says: "Additional downloads may be found here." In the long list of files that show up, the top one is for Macs (called
PIL-1.1.7a2-py2.5-macosx10.5.mpkg.zip. Grab that and install it.
- Once you've installed it, you should be able to import PIL or any of its modules in Python as described in the manual!
These aspects are less well assembled and guided right now, so you may have to do some fiddling. Feel free to ask me questions as usual.
-- IanHolmes - 26 Aug 2007
-- BenjaminEpstein - 30 Nov 2012 (Python update)
- A short primer on images is here. Read this if you've never worked with images in code before!
- Save your file as a
.png file. a save function is available in that module.
- Suggestions for implementing the diffusion:
- Generate a matrix as you've done before, work with one particle at a time, and code up an algorithm as above to keep track of where the pixel is. When you're done, process the data from the matrix to load into the image file.
- For your convenience, a list of colors followed by their RGB numbers is posted here. Use this as you wish.
- The Berkeley MPEG Encoder (for movies only)