Project 4: DLA and DBM

CS 7492, Spring 2015

Due: Saturday, March 18, 2017

Objective

The goal of this project is to gain experience in creating branching structures, such are found in coral, lichen, and bacterial colonies. You will implement two algorithms for creating branching patterns: diffusion limited aggregation (DLA) and the dielectric breakdown model (DBM). These two algorithms have different computational characteristics, as they select where to add growing materials in different ways. Also, both of these simulation methods have the means to control the thickness of the branches.

DLA and DBM

In this project, you will implement two different methods of creating branching models. Both of these algorithms create a pattern using a regular grid of squares. They are quite different, however, in how new cells are added to the growing pattern. The Diffusion Limited Aggregation (DLA) algorithm used a random walk to add cells. The Dielectric Breakdown Model (DBM) uses electrostatic potential to select where to grow the pattern. Both grown methods have a tunable parameter that modifies how thin or thick the pattern will be. For DLA, this is the stickiness parameter, which varies from 0 to 1. Stickiness of 1 will create the most skinny patterns. For DBM, this parameter is eta, and it varies from zero to infinity. Valuse of eta near zero give thick patterns, and larger values give more skinny branches.

Here are some requirements of your simulator:

Your simulator should act on this set of keyboard commands:

Initialization:   For almost all of the pre-programmed keys, you will begin the growth pattern with a single "seed" cell in the center of the grid. For keypress zero, you will create initial pattern of cells of your own choosing. Be creative, and be sure to use more than one cell in your initial pattern. Since it is trickier to initialize the DBM algorithm for more than one seed, we are just doing this for the DLA algorithm.

Drawing the Grid: In order to display enough cells for a complex branching pattern, you should draw each cell of the grid as just a few pixels. For this reason, I ask that you draw the cells as 2x2 pixels.

DBM Algorithm: The DBM algorithm is fairly elaborate. Your resources for this part of the project are your class notes and the paper by Kim et al's paper. Some of the equations discussed below for DBM come from this paper.

Here are example images for DLA, using stickiness parameters of 1, 0.1, and 0.01:



Here are example images for DBM, using eta parameters of 0, 3, and 6:



As usual, we will use "Processing" to carry out this assignment:

http://www.processing.org/

For any large project such as this, I recommend backing up your work often. You don't want to put in a ton of work and then accidentally delete all of it. I suggest making a new copy of your entire work folder every hour or so, and giving each new copy a higher number. Don't worry about file sizes -- source files are tiny. I also recommend copying all of your backups to a different computer once each day for extra safety.


Suggested Approach

As always, you can follow my suggestions or not, depending on your level of confidence about implementing this project.

DLA is the more simple of the two algorithms, so I recommend beginning with this one. The first thing to do is to create a grid data structure, just like the one for the Life cellular automaton. You will want this grid to be integers, not booleans, for later, when you implement DBM. Initialize the grid with a single "seed" cell in the center of the grid. Next, select a random position on the grid at which to start, and start a random walk at that position. You should not store the positions of the random walk in the grid. For debugging purposes, you may want to draw the motion of this point. You can choose any of several options for how to handle the point wandering off the edge of the grid. You can use toroidal wrap, you can "bounce" it back into the grid, or you can start it at a new, random place in the grid. Once you have your random walk working, modify the algorithm to check whether the walk is next to a grid cell that is already occupied. If it is adjacent to an occupied cell, then change the grid point at which the walk is positioned to be occupied, and start a new random walk. When you are at this stage, you have successfully implemented DLA.

You should next modify your DLA code to randomly choose whether the random walk "sticks" to an occupied cell. Do this by selecting a random number and comparing it to the stickiness factor. A stickiness factor of 1 means the random walk always sticks. If a point does NOT stick, just let it keep randomly walking. Do not end its walk and start a new walk -- this will not produce the correct pattern, it will just produce the same pattern as if stickiness was one, but much more slowly.

Next, you should start to tackle DBM. This algorithm still requires a grid, but it also requires that you track two lists of cell positions. For this reason, I recommend creating a "cell" data type that specifies its integer location (i,j), and also a floating point variable for its electrostatic potential. One of the list of cells you should maintain is a list of all cells that have been added to the growning pattern. The second list of cells are the candidate cells, which are those cells that are next to the growing pattern but have not yet been selected to be added to the pattern. You can use the ArrayList data structure to implement these lists.

You will want to store three possible values in the grid: EMPTY, CANDIDATE, and FILLED. Initialize the grid as EMPTY, except for one FILLED cell in the grid center. Also, create a "cell" data type for this center cell and put it on the growing pattern list. Next, mark the eight cells surrounding this seed as being CANDIDATE, and place eight cells representing these cells on the list of candidate cells.

At the heart of the DBM algorithm is selecting where to grow the pattern based on the electric potential at the candidate cells. Initially, each candidate cell has a potential that is based on its distance to the one seed cell. You will eventually need to implement two routines that relate to calculating potentials. First, you should implement a routine that calculates the potential at a give cell based on the effects of every cell in the pattern list. This is a matter of calculting the distance from the given cell to each cell in the pattern list, and applying the correct radial basis function (equation 10 in the paper). Next, you should implement an routine that quickly updates the potential of an old candidate cell based on a newly added cell to the pattern. This is based on equation 11 of the paper.

Once you have the above data structures and routines implemented, you are ready to put together the pieces of the algorithm. Here are the steps needed to grow the pattern by one cell: The last piece of implementing DBM is to select a candidate cell at which to grow the pattern. This is done by calculating a value p_i at each candidate cell based on the potential of a cell. You will need to make several passes over the list of candidate cells to do this. You might also wish to augment your "cell" data type to have additional variables in which to store some of the values that you will calculate (Phi_i_eta, p_i, partial_sum_i). First, calculate the minimum and maximum value over all the potentials of cells in the candidate list. Next, calculate the value Phi_i for each candidate cell based on equation (13), raise it to the power of eta, and store this value (Phi_i_eta) in the data structure for a candidate cell. Distances should be measured in units of pixels, and the value for R_1 should be one. Calculate the sum of all such Phi_i_eta. Now, for each candidate cell, calculate p_i by dividing Phi_i_eta by this sum. Store the value for p_i in each candidate cell. Next, go through the list of candidate cells again, calculating and storing the partial sum of the values p_i up to the i-th cell, and store it in a variable partial_sum_i for the candidate cell. Then, create a random number R in the range of 0 to the partial sum of the last cell in the list (which is actually the sum of all the p_i). Go through the list of candidate cells on last time, and stop at the candidate for which R is less than partial_sum_i. This is the cell that is to be added to the growning pattern.

Tips on Debugging DBM:   Recognize that if eta equals zero, then all the values for p_i are exactly the same, so you are essentially selecting from the candidate cells at random. You can substitute random selection for the more elaborate method of selecting cells based on their potential, and see if you get the same results. Note that each time you add a new cell to the pattern, you should be adding between one and five new candidate cells to the list. Each time you take a simulation step, you can print out how many candidates are being added. As a sanity check, you can also print out the number of cells in the list of pattern cells. This count should grow by one for each step of the algorithm. To debug the math of the candidate cell selection, print the locations and the various values of the candidate cells (potential, Phi_i, etc) for the first two iterations of the simulation. Compare these values to those you calculate by hand. You might also draw the grid cells in different colors to distinguish EMPTY, CANDIDATE, and FILLED.


Turning In Your Assignment

Turn in your Processing code for this project on T-square. If your project includes more than one .pde file, zip them together into a single file.


Authorship Rules

The code that you turn in must be entirely your own. You are allowed to talk to other members of the class and to the teacher about general implementation issues. It is also fine to seek the help of others for general programming questions about Processing. You may not, however, use code that anyone other than yourself has written.  Code that is explicitly not allowed includes code taken from the Web, from books, from previous assignments or from any source other than yourself. You should not show your code to other students. Feel free to seek the help of the teacher for suggestions about debugging your code.