"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"
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,
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
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 four buttons are straightforward:
- step - Move forward one step in the simulation. What this means from a code point of view is that it:
- Looks at all the turtles in the simulation (in this case, just the one)
- Asks each of the turtles to get their next state, whatever that may be, with a call that looks like
new_state = turtle.getnextstate()
- Asks each of the turtles to set their state to that next state they just returned with:
turtle.setstate(new_state). Note: you may be wondering why we do this in two phases. It's simple -- if we didn't, then in some cases, the order in which we updated turtles would affect the simulation. This is because we want to think of all the turtles as being updated in parallel, but in reality we have to sequentially update them. Thus, by asking all the turtles what they intend to do next in the first pass, remembering it, and then changing them all in a second pass, we effectively get the parallel behavior we wanted.
- run - Go into a loop, effectively calling step over and over.
- stop - Stop running. If the simulation wasn't running, this button has no effect
- quit - Quit out of the Turtle Arena simulation.
Running our first program,
So what happened when we clicked run with our first turtle program,
simple.py? (drum roll please, hold on to your seats)
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:
- a position (required). This is a Vector, telling the system where the center of the turtle is to be placed -- here it's the center of the screen at (200,200) -- note that x increases to the right and y increases downward, which is common when drawing things on the screen. This might take a while to get used to.
- a heading (required). This is measured in degrees, with North (up) being 0, and values increasing clockwise. Thus, East (right) assighed to 90, South (down) is 180, and West (left) is 270.
- an outline. This is the color of the outline border around our object. Since we didn't specify anything, it took the default, which was black.
- a fill. This is the color of the interior of the Turtle. Again, nothing was specified, so it took the default, which was white.
- a width. This is the width of the outline border, whose default is 1 pixel.
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
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,
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
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
class WalkingTurtle(Turtle):line says that
WalkingTurtleis going to derive its behavior from the base class
Turtle. What follows are the things that make a
WalkingTurtleunique -- 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
Colorwe 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
WalkingTurtle and we have to pass in a value for its additional argument,
speed. Let's give it a speed of 1 for now:
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 (
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!
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.
Author three classes, Cat, Mouse, and Statue (in files
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.
Here are some general tips that may help you on your journey:
- After downloading and importing the Arena, Vector, Turtle, WalkingTurtle, and Color packages, type
help(package_name), as in
help(Vector)to see its documentation.
- A number of the methods you are to write involve trigonometry. Given below are some formulas. Derivations for all the formulas appear in the old CS 9A study guide, available for examination at the Self-Paced Center or online.
- The cat sees the mouse if
(cat radius) * cos (cat angle mouse angle)
is at least 1.0.
- When the cat circles distance d around the statue, its radius does not change, and the change in its angle can be calculated from the relationship
d = angle * (radius of arc)
- The cat catches the mouse when it (the cat) moves past the mouse while at the base of the statue, i.e. when the cat radius is 1.0 and the mouse angle lies between the old cat angle and the new cat angle. An angle B is between angles A and C in the following circumstances:
cos (B A) > cos (C A), and
cos (C B) > cos (C A).
The difference C A is assumed to be less than 180°, or π radians.
- Note that the cat cannot move inside the statue’s base; hence if the cat is, say, at radius 1.7 and sees the mouse, it can move in only 0.7 meters, up to the base of the statue.
- Remember that angles a, a + 2π, a + 4π, ... are all equal.
- The cat sees the mouse if
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.
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|
...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.
We've opened Pandora's box by providing a really nice Artificial Life simulation environment. Here are some things you can simulate:
- Flocking. You could start to approach some of the Boids flocking motion by Craig Reynolds
- Traffic Simulations. Can you predict how a given change (e.g., addition and/or removal of a lane for construction purposes) will affect a commute? . Set up a world with food for the prey scattered about, predators and prey. You'll probably need conditions that will lead to the birth and death of prey and predators, and the spontaneous creation of new food (for the prey).. Some of the most intersting simulations are those that have realistic Physics attached to them.
These are the requirements to meet for project completion:
- Correctly working code:
Statue.py, and the driver
Statueclasses must be subclasses of
- Use of functions — your program must be broken down into one or more functions — it cannot be one big long script.
- Each function has a docstring that summarizes its purpose and provides a description of its inputs and outputs.
- Sufficient testing, with output sufficient to verify test correctness:
- tests on specified values for cat and mouse positions;
- evidence of independent tests of all methods in each of the three Classes you'll author;
- tests sufficient to exercise all statements in the all the methods in all the Classes you'll author.
- Adherence to CS9H style standards:
- variable and function names that reflect their use;
- informative comments at the head of each function;