Assignment 4: Functions

CSCI 141 
Assignment 4: Functions
1 Overview
For this assignment you will write a Python program that draws a Sierpinski Triangle using a method
called a chaos game.
The chaos game is played as follows. The user chooses the window size (say 300 by 300 pixels). Denote
the three corners of an isosceles triangle 1, 2, 3, where corner 1 is at the top center of the screen,
corner 2 is in the lower left of the screen, and corner 3 is in the lower right of the screen. Here’s some
pseudocode to help you understand how the chaos game works:
Let p be a random point in the window
loop 10000 times:
c = a random corner of the triangle
m = the midpoint between p and c
choose a color for m
color the pixel at m
p = m
This process will generate a Sierpinski Triangle like the one pictured below.
2 Details
1. One thing you might notice if you try this on paper (or if you carefully look at the image you
generate once it’s complete) is that the first few iterations of this game may produce points that
are not actually part of the Sierpinski triangle. Thus, you should start the process of generating
points, but don’t color the first few points you calculate. To be safe you should start adding
points to the image after 10 iterations.
2. You are provided with a skeleton code file called sierpinski.py. This file contains some code
to help get you started, including a function that sets up the Turtle graphics window for our
somewhat nontraditional turtle use case. In particular, take a look at the specification for the
turtle_setup function: this takes care of creating a turtle, and resizing the window to the
desired dimensions. Call this before beginning the chaos game iterations, and use the turtle it
returns to do all your pixel coloring.
3. The setup function changes the window so its coordinate system now has (0,0) at the bottom left corner, with positive x going right and positive y going up, so the top left corner is
at (0, canv_height),the bottom right corner is at (canv_width, 0), and the top right is at
(canv_width, canv_height). This helps to simplify the math when locating corners of the triangle. The setup function also calls tracer(0, 0), which you may recall disables automatic
re-drawing of the canvas. This means that to get your picture to show up, you need to call
turtle.update() yourself. For the sake of speed, I recommend re-drawing the picture only every
100 or every 1000 iterations so the drawing doesn’t take too long.
4. In this program, we’re not really using turtles for what they were meant for. Instead of drawing
lines as the turtle moves, we’ll use the turtle to color individual pixels on the canvas. Turtles
draw as they move, but they can also draw shapes, such as circles and dots; we’ll make use of the
aptly named dot method. To fill in a pixel, all you need to do is move the turtle to that pixel,
then draw a dot of size 1.
5. When the turtle draws via movement with the pen down, or via other methods such as dot, the
color it draws is determined by the turtle’s current color. You can change the turtle’s current
color using the (again, aptly named) color method. One way to specify colors is using various
standard color names ("red", "green", "purple", etc.). A more flexible way is to specify
how much red, green, and blue you want: some combination of these three primary colors can
represent all colors that your screen can display. When storing images on computers, we typically
store each R,G, and B value using a single byte (8 bits). That means a color is represented by
three numbers from 0 to 255, which is the maximum number representable using 8 bits. For
instance (255, 0, 0) is red, (0, 255, 0) is green and (0, 0, 255) is blue. Furthermore, (255, 255, 255)
is white and (0, 0, 0) is black.
6. In the figure on the first page, you can see that the colors of the pixels are related to their
coordinates. If you simply followed the pseudocode at the top of this document, but chose black
for the color every time, then you’d have a black and white version of the Sierpinski triangle.
That’s a good first step to make sure your chaos procedure is working correctly. Once you have
that working, you should figure out how to make the triangle prettier. The color scheme used
in the example above chooses each color value based on the distance from one of the corners. In
particular, the red color scales from 255 to 0 based on distance from corner 1, the green scales
with distance from corner 2, and blue scales with distance from corner 3. You may choose a
different scheme, but your colors should appear in a smooth gradient across the triangle, and
the corners should each be colored one of the “base” colors (red, green, and blue). This is not
too difficult in a square window but you need to be a little more careful in a non-square window
(when the width of the window is not equal to the height of the window).
3 Suggested Approach
This may seem like a big problem to solve all at once; in fact it is, so it is highly recommended that
you write functions to solve small pieces of the problem, then put them together into a solution to the
full program.
1. In class we wrote distance and midpoint functions. These will come in handy here, so copy
those into your code, and feel free to modify them as needed.
2. I included the pseudocode for the chaos game in the skeleton file. This is a handy way to keep
track of your overall program structure: start with pseudocode and piece-by-piece fill in code
that accomplishes each of the steps. Because each step has some complexity to it, you should
define functions that take care of the details of each step. That way, the code in your main
program will end up corresponding fairly closely to the lines of the pseudocode, and it will be
easy to understand.
3. Based on the pseudocode, decide what functions you’d like to have in order to make the algorithm
easy to implement. In my solution, I have almost one-to-one correspondence between functions
and lines in the pseudocode. To give one example, to choose a color for the point m, I have a
choose_color function. It takes a point and the three corners and calculates the RGB color
values based on distance of the point from each of the colors. This function in turn makes use of
the distance function.
4. Instead of immediately starting to code each function you’ve decided to write, try this instead:
write out the specification (docstring) for the function. This means deciding what the function
takes as arguments and what it returns. Once you have this, try sketching out the code for the
chaos game, using the functions (even though you haven’t written them yet!). In doing this, you
may discover changes that you want to make to your function specifications—make them now so
you don’t have to rewrite the code.
5. Now, go implement each of your functions. Start with the ones that will be needed to draw the
triangle in black. After finishing one function, test it. Use the interactive shell and/or put code
in your main program that checks whether the code does what you expect it to. For example, to
test my choose_color function, I first tried passing in each corner: I made sure the top corner
gave me (255, 0, 0) back, and so on for all three corners. Then I tried the bottom middle point on
the canvas, because it’s easy for me to calculate that its blue and green values should be about
128 (it’s equidistant from the green corner and the blue corner). Then test the center point - its
RGB values should all be equal because it’s equidistant from all three corners.
6. Finally, turn your sketch of the overall chaos game algorithm into real code that uses your
functions to draw the Sierpinski triangle. Make sure it works with different square window sizes
first (e.g., 200 by 200, 300 by 300). Then try testing it with unequal width and height (e.g., 200
by 300).
4 Hints
1. I defined three variables in my main program that hold the coordinates of the three corners, since
the corner coordinates are needed in several places. The functions that do calculations involving
corners need to take the relevant corners as parameters.
2. Drawing a black and white triangle is a great first step. You may want to start out simply
choosing black as the color for all pixels to ensure the geometry is all working correctly.
3. The distance and midpoint function used tuples to pack the coordinates of points together into
a single argument / return value. This is a design decision, and you may choose to use this
approach in your functions or not. For example, my function that colors a certain pixel a given
color has the following header:
color_pixel(turt, point, color)
where point is expected to be a 2-tuple point = (x, y), and color = (r, g, b) is a 3-tuple
of the RGB color values. I could also have written it
color_pixel(turt, px, py, r, g, b)
but I think it’s cleaner to pass points and colors to functions as tuples.
4. How solidly filled in your triangle is depends on how many iterations of the chaos game you run
and how large your canvas is. A smaller canvas has fewer pixels to fill in, so fewer iterations
will make a more solid picture, but it will have lower resolution. A large picture requires more
iterations but has higher definition. Feel free to experiment with running more iterations to get
larger, higher-definition triangles, but please turn in code that runs 10000 iterations and
runs in less than 5 seconds. To keep things fast, remember that you can choose how often
to call turtle.update(); for maximum speed, call it once after all your iterations are complete.
The images below show what you can expect your drawing to look like with 10000 iterations for
a few different canvas sizes.
Here’s a 200x200 output:
Here’s a 100x300 output:
Here’s a 200x100 output:
5 Guidelines
Please make sure your program follows these guidelines:
• Your code should run 10000 iterations of the chaos game and run in under 5 seconds.
• Your functions should not directly make use of (refer to) any global variables. Any information
a function needs to do its job should be passed into the function as a parameter.
• Your code should do all the drawing (i.e., color all pixels) with the Turtle object returned by
the setup function. Don’t create any additional turtles.
• Each of your functions, and the main program, should not be too long. Not counting comments,
docstrings, and blank lines, my main program (the part in the if __name__ == "__main__":
block) is just under 20 lines and each of my functions is less than 10 lines. If you find yourself
writing a continuous block of code that’s longer than about 30 lines (not counting comments and
blank lines), think about how you could break it up into logical subtasks and write functions to
accomplish each one.
• Your functions and variable names should be descriptive but not overly long. For example, your
corner 1 variable should probably not be called c1, nor should it be called
the_top_middle_corner_of_the_triangle. Somewhere in between is best.
Submission
Take a screenshot of the drawing produced on a canvas with width = 300, height = 120, and name
it triangle.png. Zip both files into a zip file called a4.zip and submit it to the A4 Code assignment
on Canvas. As usual, please fill out the A4 Hours survey with an estimate of the hours you spent on
this assignment.
Rubric
Submission Mechanics (10 points)
You submitted a zip file called a4.zip containing sierpinsky.py. 1
Your zip file also includes triangle.png, a screenshot of your program’s result on a
300x120 canvas.
4
Your sierpinski.py program runs in under 5 seconds. 4
sierpinski.py contains comments including your name, date, and description at the
top
1
Code Style and Clarity (36 points)
Your program defines at least two additional functions beyond the provided setup, distance, and midpoint functions.
10
Each function you introduce has a docstring containing a clear function specification. 8
Your functions do not make use of any global variables. 6
The main program and each individual function is not excessively long. 6
The names of functions and variable names are descriptive but not too verbose. 6
Correctness (34 points)
The triangle is drawn correctly for a square window 10
The triangle is drawn correctly for a non-square window 10
The first ten points generated are not added to the image. 4
Each corner is colored one of red, green and blue as described above 5
The colors gradually blend according to their distance from each corner 5
Total 80 points
6 Challenge Problem
Take a look at the following web page: http://mathworld.wolfram.com/ChaosGame.html. There
you can see how what we’re doing here is just one specific case of a general idea. The general idea is
you can have triangles, squares, pentagons, hexagons, etc. And you when you choose a random corner
and find the midpoint you could instead find the point that is 1/3 of the way to the corner, or 3/8 of
the way to the corner, etc.Make a copy of your main assignment program in a file named chaos.py.
In this file, implement the following function:
def chaos_game(canv_width, canv_height, poly_sides, ratio):
""" Run a chaos game on a canvas with size (canv_width, canv_height)
with n = poly_sides (i.e., a poly_sides-sided polygon)
and r = ratio (i.e., fraction of distance from the corner)
"""
This challenge may require usage of material we haven’t covered in detail (for example, lists will likely
come in handy to store the corners of the polygon). If you are trying to tackle this and encounter any
problems, come talk to me and I’d be happy to help. Successful completion of the challenge problem
is worth 5 points of extra credit. Submit chaos.py to the A4 Challenge assignment on Canvas.