Mandelbrot Set
WHAT IS IT?
This model uses turtles and colored patches to generate an image of some portion of the Mandelbrot set. To understand the Mandelbrot set, we must first understand the following iterative relationship:
z(n+1) = z(n)^2 + z(0)
where z(n) is the value of z after n iterations, and z(0) is the initial value.
The set of complex z(0) values for which z(n) converges to a finite range of values (as n goes to infinity) is the Mandelbrot set.
Another way of defining the Mandelbrot set is in terms of Julia sets. If we start with a slightly different iterative relationship:
z(n+1) = z(n)^2 + c
where c is a complex constant and z(n) is again the value of z after n iterations, then the boundary of the set of z(0) values for which z(n) converges to a finite range of values is the Julia set. Different values of c give different Julia sets. In some cases, the Julia set is a connected, continuous set of points; in others, it is completely disconnected, with each point of the Julia set separated from the other points of the set. Another definition of the Mandelbrot set, then, is the set of c values for which the associated Julia set is a connected set.
Practically speaking, we can't iterate the sequence to infinity. Instead, we set a maximum number of iterations, and we compare the terms of the sequence with a threshold radius; for the Mandelbrot set, this threshold radius is 2. If the distance between z(n) and the origin becomes greater than the threshold radius at some point in the sequence, we know that z(0) is not a member of the Mandelbrot set, and we stop iterating. On the other hand, if n exceeds the maximum number of iterations, and z(n) has not yet exceeded the threshold radius, then we assume that z(0) is a member of the Mandelbrot set. (We could also keep track of the values in a sequence, to see if they are repeated at some point, indicating that the sequence is cycling, and thus finitely bounded; this isn't an approach that is well-suited to StarLogo, however.) Not surprisingly, we will get more accurate results if we select a large maximum number of iterations; however, for z(0) values which are in the Mandelbrot set, a larger iteration limit means we will iterate longer before coming to that conclusion.
Besides learning which z(0) values are members of the Mandelbrot set, and which are not, it is often useful to count how many iterations it takes before a sequence exceeds the threshold radius; in the immediate neighborhood of the Mandelbrot set, there are large changes in this number of iterations for small changes in the z(0) value. If we display some subset of complex numbers graphically, by plotting their x + yi complex values on the X-Y coordinate system, and we relate the number of iterations before a sequence to the color used to plot the z(0) that begins the sequence, then we will have a graphical representation of the Mandelbot set and the surrounding region, for the given value of c. Using colors in this fashion is sometimes referred to as "coloring by escape speed", where a lower number of iterations corresponds to a larger escape speed.
HOW IT WORKS
This model uses a number of turtles, each moving vertically along a portion of a single column, to draw the Mandelbrot set. Every time a turtle moves to a new patch, it scales the patch coordinates to a virtual coordinate system (allowing us to zoom in, to a certain extent), and begins iterating the sequence based on the scaled x and y values.
If the maximum number of iterations is exceeded, the turtle assumes that the sequence beginning with the z(0) value corresponding to its patch converges (i.e. the z(0) is in the Mandelbrot set), and it stamps the patch with the color selected by the user for the Mandelbrot set; otherwise, it stamps the patch with a color related to the number of iterations before the threshold radius was exceeded. The turtle then moves to the next patch; if that patch has already been stamped for the current Mandelbrot set drawing, the turtle dies.
HOW TO USE IT
The "Maximum # of Iterations" slider controls the maximum number of times a sequence will be iterated by a turtle, before the turtle assumes that the sequence converges. Lower values will result in the set being rendered more quickly, but with less accuracy. With higher values, the set is rendered more slowly, but more accurately. A starting value of 100 is reasonable in most cases, though some parts of the Mandelbrot set are rendered very differently with a higher iteration limit.
The next few controls have to do with the centering and scaling of the image. The "X Center" and "Y Center" monitors show the complex value (x + yi) that will be the center for the next drawing. When you press the "Set" button, it will remain pressed until you click some point in the StarLogo canvas; the point you click will be the new center. The "Reset" button sets the center to the point (-0.5, 0), which is the default.
The "Zoom Factor" slider is used to draw the Mandelbrot set with a magnification factor. By default, a scale value of 0 shows the entirety of the Mandelbrot set. Each increase by one zooms in by a factor of two.
The "Set Color" slider allows you to specify the color (using the StarLogo numeric color values) with which the turtle will stamp patches corresponding to points that are considered to be in the Mandelbrot set.
The "Divergent Color" slider controls how wide the range of colors is. If a sequence exceeds the threshold radius after the first iteration, then the patch will be stamped with this color; if it takes more iterations to exceed the threshold radius, the resulting color will be scaled between this color and the interior color.
The "Clear" button erases any previous drawing from the canvas. (Note: it is not necessary to press "Clear" before pressing "Draw". Doing so will cause the drawing to be done on a black canvas; otherwise, the new drawing will slowly replace the previous one.)
Press "Draw" to draw the Mandelbrot set on the canvas, based on the parameters set in the sliders. If the process is interrupted (by pressing the "Draw" button again, bringing it to the up position), and started again, drawing will begin again from the start.
THINGS TO NOTICE
Notice that the outer regions of the canvas generally will be drawn first; this is because the sequences that start with the complex values corresponding to these patches diverge very quickly (depending on the scale and centering, of course).
When the "Zoom Factor" slider is used to zoom in close on an area that includes a portion of the Mandelbrot set boundary/interior, the sequences starting with the z(0) values corresponding to the patches on the canvas will rarely diverge in a very small number of iterations; thus, the specified "Divergence Color" will generally not be used, and the range of colors visible on the canvas may be significantly limited vs. the range specified in the sliders. On the other hand, there are some regions of the Mandelbrot set where - depending on the maximum iterations specified - we won't see many (if any) pixels of the set color.
Notice that there will often be complexity revealed, after zooming in and redrawing, of which there was no hint at larger scales (though the features at the smaller scale will often resemble the features visible at the larger scale).
EXPLORATIONS
There is a natural relationship between the width of the color range selected (i.e. the difference between the interior color and the divergent color) and the maximum iterations. With a given maximum iterations value, there will be - at most - the same number of possible colors present in the image. So if the color range runs from 40 to 99, but the maximum iterations is 20, many of the possible color values will be unused. On the other hand, if the color range is 50 to 59, and the maximum iterations is 100, there will be some iteration values which, when plotted in color, are indistinguishable from others. These graphical relationships become trickier with different zoom levels, divergence thresholds, etc. Experiment with some combinations, to find Mandelbrot set drawings which you think best use color to reveal details. (Note that the StarLogo color spectrum is actually much more detailed than the documentation might lead you to believe. Although only integral values are documented, there are actually fractional values between them which will be displayed distinctly by StarLogo. In general, the number of distinct shades of any StarLogo color is between 50 and 90. However, at the lighter end of each color's shade spectrum, the colors may be nearly indistinguishable from white.)
THINGS TO TRY
Begin by drawing with a zoom factor of 0, maximum iterations set to 50, interior color set to 50, and the divergent color set to 99.
Next, set the zoom factor slider to 1, and redraw. Notice the additional detail that is now visible: structures that were hard to see at the larger scale are now apparent - but they are also very similar to structures which were visible before.
Click the "Set" button (to set a new drawing center) and click in one of the bulb-like structures around the edge of the Mandelbrot set. Increase the zoom factor to 3, and redraw the set. Notice the structures that are now visible, that weren't before.
Increase the maximum iterations to 150, and redraw. Notice the sharpening in the details around the set boundaries.
Try different values of the color sliders, to see how your choices can reveal or hide some of the details of the Mandelbrot set and its boundaries.
EXTENDING THE MODEL
Currently, the model scales color linearly, according to the number of iterations before divergence. Of course, there are many other ways we might scale color. For example, we could take the logarithm of the number of iterations, or the inverse of the number of iterations, etc. The result could then be used to select a color on the spectrum between the color used for the Mandelbrot set and the color used for the sequences which exceed the threshold radius in a single iteration. Each of these color mapping schemes would result in different characteristics for the "colored by speed" rendering of the Mandelbrot set and the surrounding neighborhood of the complex plane.
Although this model can zoom in (and back out), doing so requires that the set be redrawn from scratch. It should be possible (if a bit complicated) to extend the model so that a zoom in or zoom out could be done without having to clear and redraw the canvas completely. Similarly, it should be possible to "scroll" the view - i.e. to change the center of the view, slide the displayed set accordingly, and draw only those areas which are then uncovered.
STARLOGO FEATURES
The model uses the StarLogo "mouse-down?", "mouse-xcor", and "mouse-ycor" commands to allow the user to set a new drawing center by clicking on the canvas. However, when the user clicks outside the canvas, StarLogo returns mouse-xcor and mouse-ycor as if the click was in the outermoust row or column of the canvas; the model rejects any such values, to ensure that the mouse click actually did happen in the canvas.
Multiple turtles per column are used to draw the Mandelbrot set, with each column alternating up/down direction of turtle motion. For this approach to work, a turtle must be able to tell when a patch has already been stamped; but since a patch could have a color from the previous drawing (and since a patch can be stamped with the color black), the turtle can't simply look at the patch color to know if the patch has been stamped. So, this model declares a patch variable that holds the drawing generation in which the patch was last stamped; if this number is equal to the current generation, the turtle knows that the patch has already been stamped.
The turtle also needs to know if another turtle is currently on the patch and iterating the sequence for that patch; if so, there is no need for the new arrival to do so. This is accomplished by testing the value of "count-turtles-here"; if it is equal to one, then the turtle performing the test knows that it is the only turtle on the patch, and that it should begin the iteration of the sequence for that patch.
RELATED MODELS
As noted above, there is a relationship between Julia sets and the Mandelbrot set. There is a Julia set model in the models library, with an interface similar to this one.
CREDITS AND REFERENCES
This model was based on the Mandelbrot set model in the original StarLogo models library; the current version was executed by Nick Bennett (with suggestions from Irene Lee and Gordon McDonough) in March 2006. The basic algorithm was not changed, though variables were renamed from Spanish to English. The drawing order was changed - from a single turtle drawing one row, then moving to the next row, etc., to having several turtles per column, all moving vertically. Additional variables and sliders were included, to allow for a greater degree of control over the coloring, scaling, and centering.
Background information on the Mandelbrot set and Julia sets was obtained from Wikipedia (http://en.wikipedia.org/wiki/Julia_set and http://en.wikipedia.org/wiki/Mandelbrot_set), and "Julia Jewels: An Exploration of Julia Sets" (http://mcgoodwin.net/julia/juliajewels.html), Michael McGoodwin, March 2000.
Turtle procedures
;; Procedure: set-starting-position
;; Called by: draw-mandelbrot-set procedure (observer)
;;
;; Hide turtle and position it on an unoccupied patch, in a column determined by
;; the who number.
;;
to set-starting-position
hide-turtle
let [:set (who mod screen-width)]
setheading (180 * (:set mod 2))
loop [
setxy (:set - screen-half-width) (random screen-height)
if (count-turtles-here = 1) [
stop
]
]
end
;; Procedure: draw
;; Called by: draw-julia-set procedure (observer)
;;
;; Get the number of iterations in the sequence that starts with the point in
;; the complex plane corresponding to the current location. Stamp the patch
;; with the color corresponding to the number of iterations. Repeat until the
;; turtle lands on a patch that is already occupied, or which has already been
;; stamped for the current drawing of the Mandelbrot set.
;;
to draw
loop [
let [:iteration-count get-iterations]
ifelse (:iteration-count > max-iterations) [
stamp (base-color + color-width)
] [
stamp (base-color + (:iteration-count - 1) * color-interval)
]
set generation drawing-generation
set iterations :iteration-count
forward 1
if ((generation = drawing-generation) or (count-turtles-here > 1)) [
die
]
]
end
;; Procedure: get-iterations
;; Called by: draw procedure (turtle)
;;
;; Compute the point in the complex plane corresponding to the turtle's X and Y
;; coordinates; use this point as z(0). Iterate z(n+1) = z(n)^2 + z(0) until the
;; threshold radius is exceeded, or until the iteration limit is reached.
;;
to get-iterations
let [:orig-x ((xcor - x-offset) / computed-axis-scale)]
let [:orig-y ((ycor - y-offset) / computed-axis-scale)]
let [:x :orig-x]
let [:y :orig-y]
dotimes [:iteration iteration-limit] [
let [:new-x (:x * :x - :y * :y + :orig-x)]
let [:new-y (2 * :x * :y + :orig-y)]
if ((:new-x * :new-x + :new-y * :new-y) > 4) [
output :iteration
]
set :x :new-x
set :y :new-y
]
output (max-iterations + 1)
end
Observer procedures
globals [
computed-axis-scale ; Scale for drawing, computed in setup
x-scaled-center ; X coordinate (in complex plane) of drawing center
y-scaled-center ; Y coordinate (in complex plane) of drawing center
x-offset ; X difference between complex and StarLogo origins
y-offset ; Y difference between complex and StarLogo origins
color-width ; Size of the color range
color-interval ; Difference in color per iteration
base-color ; Starting color
iteration-limit ; Maximum iterations in a sequence
drawing-generation ; Number of times set has been drawn (since clear)
]
patches-own [
iterations ; Iterations for sequence beginning at patch
generation ; Last generation in which patch was painted
]
;; Procedure: Clear
;; Called by: Clear button
;;
;; Clear drawing area, and set generation counter back to zero.
;;
to clear
clear-patches
set drawing-generation 0
end
;; Procedure: draw-mandelbrot-set
;; Called by: Draw button
;;
;; Clear turtles, but not globals (we need to keep the values of the X and Y
;; coordinates of the point in the complex plane that is the center of the
;; drawing). Compute scale, center, and color values from the sliders. Set
;; iteration limit from max-iterations slider (so changing slider during
;; execution won't have unexpected results). Create turtles, and ask them to
;; draw.
;;
to draw-mandelbrot-set
clear-turtles
set computed-axis-scale
((min (screen-width / 3) (3 * screen-height / 8)) * (2 ^ axis-scale))
set x-offset (0 - computed-axis-scale * x-scaled-center)
set y-offset (0 - computed-axis-scale * y-scaled-center)
set base-color divergent-color
set color-width (interior-color - divergent-color)
set color-interval (color-width / max-iterations)
set iteration-limit max-iterations
set drawing-generation (drawing-generation + 1)
create-turtles-and-do (5 * screen-width) [
set-starting-position
draw
]
end
;; Procedure: set-center
;; Called by: Set button
;;
;; Wait for a mouse click, and - if click location is inside of outer edge of
;; patches (to protect against responding to a click outside of the canvas) -
;; sets the new center (in the complex plane) of the drawing. Wait for a short
;; interval after, to allow monitors to catch up.
;;
to set-center
wait-until [mouse-down?]
let [:click-x mouse-xcor]
let [:click-y mouse-ycor]
if (((abs :click-x) < screen-half-width)
and ((abs :click-y) < screen-half-height)) [
set x-scaled-center ((:click-x - x-offset) / computed-axis-scale)
set y-scaled-center ((:click-y - y-offset) / computed-axis-scale)
]
wait 0.2
end
;; Procedure: set-default-center
;; Called by: Reset button
;;
;; Reset center of drawing to default values. Wait for a short interval after,
;; to allow monitors to catch up.
;;
to set-default-center
set x-scaled-center -0.5
set y-scaled-center 0
wait 0.2
end