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 Perl) this basic lattice model of stochastic physics and to generate image(s) and animation(s) of the process.

The animations are an optional extra for undergrads, but are required for graduate students.

In completing the assignment, you will gain experience using Perl objects and generating graphics from Perl, as well as exposure to a very simple biophysics model for molecular dynamics.

Diffusion-limited aggregation

The basic description of the model, diffusion-limited aggregation, can be found on Wikipedia:

• Diffusion-limited aggregation (Wikipedia)

A summary is as follows:

• 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.

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 (50 x 50 or 100 x 100) grid, though your final images/movies can involve larger images.

Grading

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:

• 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 perl's build in rand function).
• 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.

You will turn in a compressed file containing:

1. Code that implements the most basic algorithm (you can use the same color for each pixel, or a random color). This should be called hw8_simple.pl, and take two arguments:
   1. The size of the grid on which to run the algorithm (i.e. 80 means an 80x80 grid)
   2. The name of the output file. You should output an uncompressed png image to this filename. i.e.
      perl hw8_simple.pl 99 out.png
      would produce something that looks like this: .
2. (Optionally, for >80 pts) Code that elaborates on the basic algorithm. Turn in this final code as hw8_final.pl.
3. (Optionally, if you did the above) A word processed document that explains the changes you made, and the significance/implications of the results.
4. (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.

Images and movies will be generated using the following tools:

• The GD Perl Module and GD Graphics Library
  • For reviews/tutorials of Perl object syntax, try here, here or here; or check out the book by James Tisdall (ISBN:0596003072). Also, a brief explanation of the bare bones "what you need to know" to do this assignment is here.
  • A short primer on images is here. Read this if you've never worked with images in code before!
  • For examples of code using the GD Perl module, see here. You should make sure that you can properly execute the sample code at the top of that page before proceeding!
    • Note that the output of this code is a binary image file. This file will not display correctly if you view it in the terminal (it will look like a garbled string of nonsense characters). What you need to do is redirect the output of your program to a file using standard Unix-shell redirection techniques (e.g. ./myprogram.pl >mypicture.png) and then open that file using an image viewing program (most web browsers can cope).
  • Suggestions for implementing the diffusion: Use an image object to keep track of the lattice (GD::Image), and then use $image->getPixel to check if a lattice cell is empty and $image->setPixel to fix a particle in the grid, where $image is a reference to an Image object.
  • For your convenience, a list of colors followed by their RGB numbers is posted here. Use this as you wish. You might also want to investigate the graphics-colornames.pm module.
  • To get GD for windows activeperl
    1. open a command prompt, type ppm
    2. After it has loaded up, hit ctrl-1, then search for ppm. Add ppm-repositories to your install list. Then hit file->run marked actions.
    3. Go to Edit->preferences and then click on the repositories tab. Add the theory58S repository to your list.
    4. Now search for GD. Add the GD module to the list of modules to be installed. Again hit file->run marked actions.
    5. CRITICAL NOTE - Unlike in Unix, you MUST call binmode on your output file before writing an image file out in windows. I.e.
       open(OUTPUT, '>', 'tinker.png');
binmode(OUTPUT);
print OUTPUT $img->png;
       
• The Berkeley MPEG Encoder (for movies only)

-- IanHolmes - 26 Aug 2007