Week 4: Animating the Sieve

Contents

1 Introduction
2 Graphics in Pygame
3 Animating the Sieve
4 Exercises

Last week, we used an ancient algorithm -- the Sieve of Eratosthenes -- to find all the prime numbers less than N. This week, we will use graphics to illustrate the pattern of the primes. Along the way, we'll learn a lot about the graphical abilities of Python.

Introduction

The Sieve algorithm can be illustrated graphically with pen and paper, using a number square like the one below:

On the Wikipedia page, you can find a colourful animation of the process of "crossing off" multiples of 2, 3, 5, etc.

Last week, we wrote a program to implement the Sieve algorithm with lists. This week we will write a graphical Python program to illustrate the process of crossing off numbers, by generating images like this one:

Here, each of the numbers from 0 up to (197)^2 corresponds to a "pixel" on screen: i.e. a tiny coloured square. The numbers increase as we read from left to right, and top to bottom, across the image (this is just a larger version of the number square). The white pixels are prime numbers (e.g. 5), and the blue pixels are composite numbers (e.g. 6 = 3 x 2).

To harness the graphical abilities of Python, we will use two packages: numpy and pygame. The first, numpy, is for scientific computing with Python. The second, pygame, is a set of Python modules designed for writing games. We will use it today to display images. To follow this tutorial, you need to have these packages installed: please see here for instructions.

Graphics in Pygame

Display an Image

Let's load an image from file, and display it on screen, using pygame.

Open a new Python file, and save it. Now download the image file, attached at the bottom of this page, pi-cubed.png, and save it in the same directory as your Python file (or you can another image file). Now try adding this code to your file:

import pygame              # Import the pygame package
pygame.init()              # Initialize all imported pygame modules
filename = "pi-cubed.png"   # The filename of the image file
image = pygame.image.load(filename) # Load the image from file
size = image.get_size()    # Find the dimensions of the image

screen = pygame.display.set_mode(size)  
                            # Initialize a window for display, of dimension "size"

screen.blit(image, (0,0)) # Copy the image onto the screen
pygame.display.set_caption(filename) # Set the caption at the top of the window
pygame.display.flip() # Update the full display Surface to the screen

What does this code do? Let's go through it line-by-line. First, we import the pygame package, and initialise it. Then, we load the image file, and find out how big it is (get_size() returns an (x,y) pair, called a tuple, specifying the width (x) and height (y) of the image in pixels). Next, we create a new window of the same size as the image, and copy the image into it using "blit". Finally, we update the window so that the image is displayed on screen.

Try running this code -- does it work for you? If not, take a look at the error message. Can you work out what's wrong? Here are some possibilities: (1) pygame is not installed, (2) you are not using Python version 2.7 (i.e. IDLE, rather than IDLE3), (3) the image file could not be loaded, perhaps because it's not in the same directory as your Python file.

There is one problem with this program: once the window has appeared, we can't seem to close it down! To fix this problem, we need to add code which responds to events as they happen. In this case, to respond to the user's request to close the window. A minimal example is given below:

done = False
while not done:
   event = pygame.event.wait()
   if event.type == pygame.QUIT:
       done = True
pygame.quit()

What does this code do? Well, it responds to "events" as they arise. What is an event? Whenever the user clicks a mouse button, or presses a key, or closes the window, a new event is created, and added to the "event queue". The code above repeatedly checks the event queue for new events (using event.wait()) and responds accordingly. In this code, the only event that causes a reaction is the "QUIT" signal. For more on events in Pygame, see here.

A program display_image.py combining the both code snippets is attached at the bottom of this page.

Drawing

Programs with a "User Interface" are often event-driven. They wait for events, and respond accordingly. Let's explore this approach by writing a simple program which lets the user draw straight lines in a window. We will check the event queue for "mouse click" events.

Try replacing the "while not done" loop with the following code.

pts = []
done = False
while not done:
    event = pygame.event.wait()
    if event.type == pygame.MOUSEBUTTONDOWN:
        if event.button == 1:
            x, y = event.pos
            pts.append((x,y))
            if len(pts) > 1:
                pygame.draw.line(screen, blue, pts[-2], pts[-1], 1)
            pygame.display.flip()
        else:
            pts = []

Do you see how it works? The program responds to a left mouse button click, by (a) reading the coordinates of the cursor's position on the screen, and adding to a list, (b) drawing a new line if there are two or more points in that list. It responds to a right button click by resetting the list of points.

A simple program draw.py can be found at the bottom of this page -- give it a go!

Object-Orientated Programming

You may find the code above confusing, because it looks rather different to the examples from previous weeks. This is because we have encountered another new idea: object-orientated programming. But what are objects? Roughly speaking,

an "object" corresponds to a useful concept to help the programmer
an object has named members (data fields) and methods (functions)
new objects are created ("instantiated") by the program from their definition
objects are defined by classes.
classes are arranged in a hierarchy

Object-Orientated Programming is a very powerful technique. But it can be confusing at first. For example, how do we understand a statement like this?

screen = pygame.display.set_mode(size)

Here:

pygame is a set of modules designed for writing games
display is the specific pygame module for controlling the display window and screen
size is a tuple (x,y) specifying the width and height of the display
set_mode() is a function in the display module which will create a new display Surface.
Surface is a pygame object for representing images. It is defined by a class, which defines its methods (functions) and members (data fields)
The function set_mode returns a link to a new "instance" of the Surface class. In other words, it creates an object from its class definition. We assign the link to the object to a variable (screen), so we can use it later in the program.

Now let's look at how we use the Surface object. The very next line is:

screen.blit(image, (0,0)) # Copy the image onto the screen

Here, we are calling a method (a function) defined in the Surface class: namely, blit. Blit copies one Surface onto another Surface. In this case, we are copying the "image" Surface (previously obtained with pygame.image.load) onto the display Surface.

Animating the Sieve

We have seen how to load and display an image, and how to draw lines in a window. Along the way we've learnt a little bit about object-orientation. Our aim in this section is to learn how to modify the pixels individually (i.e. modify the tiny squares that make up the picture).

As we've seen, Pygame uses a particular "object" for representing images, called a Surface. Unfortunately, this object does not give us direct access to the pixels themselves. Fortunately, there is a closely-related module which gives us just what we need. Surfarray is a pygame module for accessing surface pixel data using array interfaces.

We can think of the screen as being made up of a table of pixels. Each value in the table corresponds to the color of a particular pixel. In pygame, this table is represented by a 2D array. We can modify the pixels individually, by modifying the values in the array.

Arrays

What is an array? An array is data structure (type of memory layout) that stores a collection of individual values that are of the same data type. All of the items placed into an array are automatically stored in adjacent memory locations. This makes it efficient for a program to access and process the information stored in an array.

How is an array different to a list? A list is much more flexible: you can store different types of information in a list (e.g. a = [3, 3.1, 'aardvark']) and Python makes it very easy to extend and manipulate lists. However, this flexibility comes at a cost: lists are slow/inefficient ways of storing large amounts of data of the same type, of fixed length/dimension.

What is a 2D array? A 2D array is like a table of data. Whereas the elements in a 1-dimensional array are referenced with a single index, the elements in a 2-dimensional array are referenced with two indices, corresponding to the "row" and "column" position.

How do I define an array in Python? Arrays are not implemented in the core language, although you can use list-of-lists. Arrays are implemented by numpy, a package for scientific computing. So to use arrays, you first need to import numpy

Accessing and Modifying Pixels

Now we want to modify the pixels directly. Let's write some example code. The first part will create a new window - you've seen how to do this already:

import pygame
import numpy
Nwid = 256
size = (Nwid, Nwid)
pygame.init()
screen = pygame.display.set_mode(size)
pygame.display.set_caption("Setting individual pixels")

I have chosen to make the screen a square of width 256. This is a special number for computers: 256 = 2⁸. One byte of memory is 8 bits, each of which is either 1 or 0. So one byte of can represent one of 256 different numbers (i.e. 0,1,2, ... 255). Colours are specified by three RGB values: the amount of red, the amount of blue and the amount of green. Each number should be between 0 and 255.

Now we need some code to: (i) read the array of RGB values representing the pixels, (ii) modify that array, (iii) write the modified array of pixels back on to the screen. Let's try this:

arr = pygame.surfarray.array2d(screen)  # get the 2d array of RGB values
for i in range(Nwid):
    for j in range(Nwid):     # loop over the 2d array
        arr[i,j] = i*j*256 % (256**3)   # modify the colour value
pygame.surfarray.blit_array(screen, arr)  # write the array to screen
pygame.display.flip()         # update the screen

Can you see what this code does? If not, try looking up each statement in turn. Here, the colour value is specified as a value between 0 to 2^24 - 1. If c is the colour value, then c / (256**2) gives the red value, c / (256) gives the blue value and c % 256 (the remainder) gives the green value.

Try this code. A complete version is given in the file pixels.py below. Hopefully, when you run it, you will see a window that looks something like this:

Do you understand why?

Writing the Program

You have now learnt just enough to try writing a program to animate the Sieve of Eratosthenes. If you are feeling confident, you may go ahead and try to write it for yourself. You will need to combine the Sieve algorithm, from last week, with the graphical ideas from this week. Before you start writing your program, it's a good idea to write out the key steps in words:

Set the width N of the number square
Initialize pygame
Create a new window of size N x N
Set up an array to represent the pixels in the window
Start a loop to: handle events (e.g. closing the window), and take successive steps of the algorithm.
Successively update the pixel array, and refresh the screen

It's a good idea to ask your program to take a pause between each step of the Sieve algorithm. You can do this with a statement like:

pygame.time.delay(interval)

where interval is the length of the pause in milliseconds (i.e. 1000 milliseconds = 1 second).

An example program is attached below sieveanim.py

Exercises

Check that you can run the example program sieveanim.py on your computer. Now test your understanding with the following exercises:

Reduce the magnification factor to 2
Increase the width of the number square to 400
Change the colours from blue to red, and white to yellow
Try using a rectangular, rather than square, grid
Respond to a mouse click by telling the user which number they've clicked on
Write a new multi-coloured version of the Sieve which illustrates how many factors a number has.

display_image.py

(1k)

Sam Dolan,

21 Apr 2013, 13:09

v.2

draw.py

(1k)

Sam Dolan,

21 Apr 2013, 13:09

v.2

sieveanim.py

(2k)

Sam Dolan,

22 Apr 2013, 02:45

v.2