## Description

## 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 200×200 output:

Here’s a 100×300 output:

Here’s a 200×100 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

300×120 canvas.

Your sierpinski.py program runs in under 5 seconds. 4

sierpinski.py contains comments including your name, date, and description at the

top

Code Style and Clarity (36 points)

Your program defines at least two additional functions beyond the provided setup, distance, and midpoint functions.

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.