Project 4: Turtle Behavior

Dan Garcia, 2006-04-24

"He felt that his whole life was some kind of dream and he sometimes wondered whose it was and whether they were enjoying it."

-- Douglas Adams (1952 - 2001), "The Hitchhiker's Guide to the Galaxy"

Background

[You need to be using an Java-enabled browser to see this demo.]
Figure 1. Boids flocking motion by Craig Reynolds

The field of Artificial Life is, shall we say, alive and well! The core idea is that simple rules can sometimes yield very sophisticated emergent behavior. The animation above is a perfect example of this -- there are only three steering behaviors (Separation, Alignment, Cohesion) in this simulation, but witness the complexity to the movements of individuals and the collective. We call the project Turtle Behavior as a nod to the wonderful work done by the Logo community in creating a simple Turtle Graphics micro world.

We will provide you with a "sandbox", or in this case, an "Arena" to exercise your newly-formed Classes and Objects muscles. Within a Graphical framework, you'll implement very simple behaviors in a fun two-dimensional flatland world running on top of Tkinter, the Python interface to the Tk graphical user interface toolkit (GUI). We have quite a bit of explaining to do in order to get you up to speed with the code, so let's get started.

Our First Artificial Life Simulation : Arena, Turtles and Vectors, oh my!

You will be programming the behavior of Turtles who live inside an Arena, and each of these is represented by a Python class. We provide a Vector class (to handle the representation and arithmetic of simple 2D Vectors), and a Color class (we'll import later), both of which you'll find very handy. Let's look at the simplest Python program that does all of this, simple.py:

from Tkinter import *                  # Import everything from Tkinter
from Arena   import Arena              # Import our Arena
from Turtle  import Turtle             # Import our Turtle
from Vector  import *                  # Import everything from our Vector

tk = Tk()                              # Create a Tk top-level widget
arena = Arena(tk)                      # Create an Arena widget, arena
arena.pack()                           # Tell arena to pack itself on screen
arena.add(Turtle(Vector(200,200), 0))  # Add a turtle at (200,200) heading 0=up
tk.mainloop()                          # Enter the Tkinter event loop
Figure 2. The program simple.py, which brings up a Tk Arena with a single, solitary Turtle inside.

The comments tell the whole story, but here's what is happening in a nutshell: We first import the necessary packages from Python (Tkinter) and us (Arena, Turtle and Vector). Then we create a top-level Tk Widget, an Arena (the default size is 400x400), pack the Arena in the Widget, add a turtle to the Arena, and pass control to the main Tkinter event loop. It's pretty simple. What happens when you run python simple.py? A window pops up with the following inside (here's a screenshot from a Mac):

The GUI from simple.py
Figure 3. The GUI that results from running simple.py

GUI Controls

The four buttons are straightforward:

Running our first program, simple.py

So what happened when we clicked run with our first turtle program, simple.py? (drum roll please, hold on to your seats)

Nothing.

Huh? All that meat and no potatoes? Just ain't right, like green tomatoes. Let's look a little deeper. Remember, that one turtle was being asked for its next state by calling its getnextstate() method. Was was its state in the first place? The default Turtle initialization method (__init__) asks for:

What does Turtle.getnextstate() look like? Very good question.
def getnextstate(self):
    """Determine the turtle's next step and return its new state."""
    return self.position, self.heading
Figure 4. The getnextstate method within the Turtle class.

Note that the state returned is a tuple containing the current position and heading -- i.e., the next state is the same as the current state and the Turtle is not going to move! That explains everything. Well, then, how would we get it to move? Let's define a new type of Turtle, based on this basic Turtle, that moves in a straight line.

Our Second Simulation, WalkingTurtle.py

To create this simple Walking (in a straight line) Turtle, we could copy all the code for Turtle.py and just modify what we need. When I wrote "copy all the code" a moment ago, large and annoying bells should have gone off in your head. Remember, we're wearing our Object Oriented Programming hats, folks! What we're going to do here is inherit our behavior from a base class (here simply Turtle) and override what we need (which will be simply __init__ and getnextstate). Here's what WalkingTurtle.py looks like:

from Turtle import Turtle
from Vector import *
from Color import *

class WalkingTurtle(Turtle):        ### Inherit behavior from Turtle
    """This turtle walks in a straight line forever."""

    def __init__(self, position, heading, speed, fill=blue, **style):
        Turtle.__init__(self, position, heading, fill=fill, **style)
        self.speed = speed

    def getnextstate(self):
        """Advance straight ahead."""
        return self.position + unit(self.heading)*self.speed, self.heading
Figure 5. The WalkingTurtle class, WalkingTurtle.py.
How does this work? The class WalkingTurtle(Turtle): line says that WalkingTurtle is going to derive its behavior from the base class Turtle. What follows are the things that make a WalkingTurtle unique -- that is, the methods we're overriding. We override __init__ because we need more information than just position and heading and outline + fill + width. We need a speed! We also want to visually indicate that WalkingTurtles are different from boring Turtles, so we change the default fill to blue. We had to import Color we authored to be able to just say 'blue' and not have it cause an unbound variable error.

We also need to override getnextstate, because the speed we're initialized with will affect our position. Remember basic Physics? The equation you see implemented above is the simple vector relation: Position_next = Position_current + |Heading| * speed, where Heading is a vector pointing in the direction we're facing. unit() is part of the Vector class which takes in a scalar heading -- a number in the range [0, 360) -- and returns a unit vector pointing in that direction. It's not that bad. To run it, we use the exact same code from simple.py, but replace every reference of Turtle with WalkingTurtle and we have to pass in a value for its additional argument, speed. Let's give it a speed of 1 for now:

Figure 6. The simulation from WalkingTurtle.py. If you can't view this movie, download Quicktime from Apple.
You see that our walking turtle just walks straight off the screen. Why doesn't it stop at the top? Why doesn't it bounce off the title bar? The simple answer is that the view you see in the window is just a view into an infinite plane. The turtle doesn't know about any boundaries (because none have been defined), so it just moves merrily off the top of the screen. You might think about how to create a BouncingTurtle which would bounce off the walls or WrappingTurtle which would "wrap" from Left<->Right and Top<->Bottom (as in the old Atari game of Asteroids).

Variety is the very spice of life!

Now that we've put one Walking turtle into our simulation as an independent agent, there's nothing stopping us from adding 999,999 others into our simulation (although, um, it'll be a little slow). Each could have a random position on the screen (the randrange function in the random package is useful here), heading and speed. They'd all sprint off the screen as if someone yelled fire in their crowded Arena. You could even give each a different color!

Our simulation is more powerful than that, however. Is our simulation limited to only a boring, homogeneous collection of walking turtles with varied initial conditions? No! Sure, some could be, but some could be BouncingTurtles (who would inherit their behavior from WalkingTurtles but simply overrode getnextstate)! Some could be turtles that followed another turtle. Some could be turtles that tried to move to the average position of a group, and would probably have flocking behavoirs. Some could be predators and some could be prey. Some could be simulating taxis driving down New York City streets. The possibilities are truly endless. Watch The Matrix a few more times and you'll see how powerful this could be.

"Wait!", you're saying, "How is that possible? How does any turtle know about its neighbors (say, to follow one)?" It's simple -- you could have a class variable (Python calls them Class Objects) that stored all of one type of Turtle ever created. After initialization, there could be a special method that you would invoke for each Turtle that would tell it to choose another turtle (from the set stored in the class variable) to follow. It would have to be done in a two-step manner like this because the turtles are instantiated sequentially and the first turtle would have nobody to follow.

A simpler technique to have one kind of turtle (say a single follower) know about another kind of turtle (say, a single followee) is to instantiate the followee first and then pass the followee instance as an argument to the __init__ method of the follower. The follower would then have access to the followee and could ask it questions, like "Where are you? I need to make some decisions based on whether I see you or not". This may (cough, cough) or may not (cough cough) be useful (cough, cough) in your project described below.

One of the nice features of our design is that in addition to the three methods you have already seen from the Turtle base class (__init__, getnextstate, and setstate), you can override the fourth method, getshape. This allows you to have the Turtles draw themselves any way you wish! You could even have a random component, so that each turtle instance had a different, unique shape that could be based roughly on some default shape.

Time keeps on slipping...into the future

The simulation doesn't know about absolute time, and abstractly, our Turtles don't really need to know about it either. The only thing the Turtles assume is that getnextstate is called at regular intervals, which it is. So, from the point of view of the simulation, you can imagine that every clock "tick" is one second, or one day, or one year, whichever is easiest for the problem you'd like to simulate.

The Challenge : Cat and Mouse

Phew! That was quite a bit of setup. What are you supposed to do? Glad you asked!

Cat and Mouse figure
Figure 7. The Cat and Mouse problem

The scene is an urban park; a cat watches a mouse run around the base of a statue of the actors from Monty Python. Over the course of a minute, the somewhat witless mouse moves one meter counterclockwise around the statue’s base, which is circular and two meters in diameter. Every minute, the cat pursues the mouse as follows: If the cat can see the mouse, the cat moves one meter toward the statue. If the cat can’t see the mouse, the cat circles 1.25 meters counterclockwise around the statue.

The cat plans eventually to get close enough to the mouse to make it a juicy lunch. The mouse by accident, however, may manage to keep completely out of sight of the cat, since both the cat and the mouse are moving counter-clockwise.

Problem

Author three classes, Cat, Mouse, and Statue (in files Cat.py, Mouse.py and Statue.py) that simulate this situation. These classes should be subclasses of Turtle. The Statue should be a fixed object that looks like a circle, pretty easy. The mouse just runs around in a circle, also pretty easy. The Cat is the only one that's a little bit harder...it has to make decisions and calculate visibility of the mouse.

Our simulation is based in Pixels, but the problem is given with real-life sizes (in m). You should decide an appropriate scaling factor (e.g., 1m = 100 pixels) and stick with it for all of your classes. Don't hardcode the scaling factor in multiple places -- set your code up so that you can change one constant and everything else will change sizes correctly.

You should write a driver program catmouse.py that, like simple.py, sets everything up and calls the main driver loop.

Hints

Here are some general tips that may help you on your journey:

Testing

Test each function and method in your program with enough different inputs to show that it works. When testing a method, print out the input, the expected result, and the actual result.

It would probably be helpful for debugging purposes to have a debug flag available that, when true, dumped the position and heading of all characters involved (cat and mouse) at each time step.

Miscellaneous requirements

You should test the methods of each Class in isolation, using appropriate test data, to see if they work independently before calling them from a driver function. Tutors may ask to see the results of these tests. Your test data should include the following values:

cat radius cat angle mouse angle
1.0 35.0° 396.0°
8.1 0.0° 45.0°
8.1 150.0° 240.0°
4.0 0.0° -57.0°

...plus whatever other values are necessary to ensure that all statements in your program have been executed at least once. Be sure to check that the output makes sense for these tests, since the output is what most tutors will check first. Students are sometimes embarrassed to have a tutor point out that their programs have the cat moving deeper and deeper inside the statue, or moving away from the mouse instead of approaching it.

Extra for Experts

We've opened Pandora's box by providing a really nice Artificial Life simulation environment. Here are some things you can simulate:

Checklist

These are the requirements to meet for project completion: