Cafun: Extending the Game of Life

As promised in the last entry this time around we are going to dissect a Cafun simulation file that I created. This file extends Conway's Game of Life by adding some color to the cells. It also borrows from Edward Rietman's Exploring the Geometry of Nature. Rietman included BASIC programs in his book that looked at how a Life game develops when it begins with a certain random population densities. So before we begin the discussion, here is the file in its entirety, with line numbers:

1. <simulation name="Life_Extended" author="John Conway adpated by Jack">
2. <description>
3. <section>This is a simple implementation of the famous Conway's
4. Game of Life, extended to add color to longer lived cells. Including
5. probability starters from Rietman's Exploiring the Geometry of Nature
6. Paint some "living" cells on a "dead" background and
7. enjoy!</section>
8. <section caption="Description">This cellular automaton is guided by the
9. following rules: A dead cell becomes alive when there are exactly three living
10. cells in its neighborhood. A living cell dies if there are less than two or more
11. than three cells in its neighborhood which are alive. This version of Conway's
12. Game of Life extends the original one by marking what rules were applied at
13. certain locations in the universe. When a living cell dies because there are
14. less than two living cells in its neighborhood it is marked blue, if it dies
15. because there are more than three cells in its neighorhood which are alive it is
16. marked green. You can also determine the lifetime of living cells since their
17. color changes to red after some time. The cells will change color from White
18. to Yellow to Green to Blue to Gray as they "age".</section>
19. </description>
20. <abstract-cell-type id="living" />
21. <cell-type id="Start10" color="90 90 90">
22.     <mutation cell-type="Alive" probability="0.10">
23.         <condition cell-type="Start10"  />
24.     </mutation>
25.     <mutation cell-type="Dead" probability="0.90">
26.         <condition cell-type="Start10"  />
27.     </mutation>  
28. </cell-type>
29. <cell-type id="Start15" color="85 85 85">
30.     <mutation cell-type="Alive" probability="0.15">
31.         <condition cell-type="Start15"  />
32.     </mutation>
33.     <mutation cell-type="Dead" probability="0.85">
34.         <condition cell-type="Start15"  />
35.     </mutation>  
36. </cell-type>
37. <cell-type id="Start20" color="80 80 80">
38.     <mutation cell-type="Alive" probability="0.20">
39.         <condition cell-type="Start20"  />
40.     </mutation>
41.     <mutation cell-type="Dead" probability="0.80">
42.         <condition cell-type="Start20"  />
43.     </mutation>  
44. </cell-type>
45. <cell-type id="Start25" color="75 75 75">
46.     <mutation cell-type="Alive" probability="0.25">
47.         <condition cell-type="Start25"  />
48.     </mutation>
49.     <mutation cell-type="Dead" probability="0.75">
50.         <condition cell-type="Start25"  />
51.     </mutation>  
52. </cell-type>
53. <cell-type id="Start50" color="50 50 50">
54.     <mutation cell-type="Alive" probability="0.50">
55.         <condition cell-type="Start50"  />
56.     </mutation>
57.     <mutation cell-type="Dead" probability="0.50">
58.         <condition cell-type="Start50"  />
59.     </mutation>  
60. </cell-type>
61. <cell-type id="Dead" color="0 0 0" active="false">
62.     <mutation cell-type="Alive">
63.         <condition cell-type="living" min="3" max="3"/>
64.     </mutation>
65. </cell-type>
66. <cell-type id="Alive" color="255 255 255">
67.     <implementation cell-type="living" />
68.     <mutation cell-type="Dead">
69.         <condition cell-type="living" max="1"/>
70.     </mutation>
71.     <mutation cell-type="Dead">
72.         <condition cell-type="living" min="4"/>
73.     </mutation>
74.     <mutation cell-type="Young">
75.         <condition cell-type="living" min="2" max="3" />
76.     </mutation>
77. </cell-type>
78. <cell-type id="Young" color="255 255 0">
79.     <implementation cell-type="living" />
80.     <mutation cell-type="Dead">
81.         <condition cell-type="living" max="1"/>
82.     </mutation>
83.     <mutation cell-type="Dead">
84.         <condition cell-type="living" min="4"/>
85.     </mutation>
86.     <mutation cell-type="Adult">
87.         <condition cell-type="living" min="2" max="3" />
88.     </mutation>
89. </cell-type>
90. <cell-type id="Adult" color="0 255 0">
91.     <implementation cell-type="living" />
92.     <mutation cell-type="Dead">
93.         <condition cell-type="living" max="1"/>
94.     </mutation>
95.     <mutation cell-type="Dead">
96.         <condition cell-type="living" min="4"/>
97.     </mutation>
98.     <mutation cell-type="Mature">
99.         <condition cell-type="living" min="2" max="3" />
100.     </mutation>
101. </cell-type>
102. <cell-type id="Mature" color="0 64 255">
103.     <implementation cell-type="living" />
104.     <mutation cell-type="Dead">
105.         <condition cell-type="living" max="1"/>
106.     </mutation>
107.     <mutation cell-type="Dead">
108.         <condition cell-type="living" min="4"/>
109.     </mutation>
110.     <mutation cell-type="Old">
111.         <condition cell-type="living" min="2" max="3" />
112.     </mutation>
113. </cell-type>
114. <cell-type id="Old" color="192 192 192">
115.     <implementation cell-type="living" />
116.     <mutation cell-type="Dead">
117.         <condition cell-type="living" max="1"/>
118.     </mutation>
119.     <mutation cell-type="Dead">
120.         <condition cell-type="living" min="4"/>
121.     </mutation>
122. </cell-type>
123. </simulation>

The file is an xml file and the <simulation> tag set is the root of xml structure. Lines 2-19 provide the description that shows in the left pane of the main Cafun window. It can be left out but it helps make sure you know what this simulation is about.

Line 20 is an example of one of the things that makes Cafun a powerful cellular automaton engine. The abstract-cell-type allows many actual cell-types (we'll talk about those below) to behave as a single type. In this case we will have several variants of "living" cells and we want them all to contribute to whether a cell lives or dies in the next generation.

The remainder of the file defines the various cell-types and the rules that control them. The repetitive nature of some of the definitions is required so we can have the each generation progress to the next type. One thing to be aware of, Cafun determines a cell-type by it's color. So don't make two types the same color. The program will define them as the first cell-type with that color definition. I'll describe one example of the three distinct cell-types we have in the file, and then you're on your own.

Line 61-65: Cell-type Dead
The Dead cell type is the background type. In most runs of the simulation the bulk of the cells will be dead. Dead cells will change to Alive cells if they are surrounded by exactly 3 living cells. We'll look at the details of the cell-type elements in the next section on the Alive Cell type.

Lines 66-77 Cell-type Alive
The cell-type definition for the Alive cells is repeated below with explanatory notes.

<cell-type id="Alive" color="255 255 255">
This tag defines the cell-type. The id attribute is how the type will be referred to in the simulation definition. The color is how it will be shown on screen. Reminder, this is how Cafun identifies the type. If you created another cell-type with the same color (R:255 G:255 B:255 or white) it would be identified as Alive.

    <implementation cell-type="living" />
This tag shows that this cell-type implements the abstract cell-type "living" and any mutations defined to it.

    <mutation cell-type="Dead">
        <condition cell-type="living" max="1"/>
    </mutation>
The three tags above are a mutation definition. These are the rules that the cell follows. This first mutation and the one below could be moved the "living" abstract cell-type but having them in each cell-type definition allows for modifying the rules for some types of living cells compared to others.  The cell-type in the mutation element is what the cell under consideration would become if the conditions are met. In this case the cell will become a Dead cell id it is a living cell with a maximum of 1 neighbor. Since there is no minimum number it is implied that have zero neighbors would also satisfy this rule. So the cell-type in the condition indicates what type of cells in the eight cell neighborhood contribute the the count to satisfy this rule.

    <mutation cell-type="Dead">
        <condition cell-type="living" min="4"/>
    </mutation>
This mutation is the same as the first but for all count values 4 and higher.

    <mutation cell-type="Young">
        <condition cell-type="living" min="2" max="3" />
    </mutation>
This is the "continues to live rule" from the game of life. But in this case we are going to transform the cell into the next "generation" of living cell. This allows us to use color to see where the activity is in the simulation. In this case the cell will become a "Young" cell (color: yellow) if it survives. The progression is Alive(white), Young(yellow), Adult(green), Mature(blue), Old(gray). Stable GoL configurations will eventually turn gray. Oscillators will most often have a gray part and a white part. Gliders are mostly white but some of the cells survive a couple of generations to turn yellow and green.
</cell-type> - This is the closing cell-type tag.

You can define new cell-types with different mutations using this basic pattern. If you find an article that describes a cellular automaton that you wish to try, just code the rules that they give you as mutations.

Line 29-36: A Rietman style probabilistic starter
This particular starter is the 15% starter that allows you to randomly fill the CA world with 15% live cells. There are starters for 10%, 15%, 20%, 25% and 50%. Simply fill with one of these cell types to get your random start. You could also use a large brush and put down areas of each and  see what happens. The piece that provides the randomness is in the mutation element:
<mutation cell-type="Alive" probability="0.15">
The probability attribute indicates what the chance is that this mutation will trigger. In this case it is set to 0.15 or 15%. So there is a 15% chance that the cell will change to an Alive cell in the next generation. There is a matching mutation that has an 85% chance to trigger and it would turn the cell to a Dead cell.

So there you have it. Extensions to Conway's Game of Life that make it a little more colorful and easier to randomly seed your starting world. One addition I've considered that would create a distinct change from the Game of Life and add a new dynamic to the simulation is to give the Old cells a chance, say 50%, to convert to a Start50 cell. This would mean that all Old cells, those that had lived at least 5 generations would have a 50 percent chance to be changed into a cell that had a 50 percent chance to die. This would potentially cause certain stable constructs to whither away as one or more cells die off. You are encouraged to try to make that change yourself.

That's it for now. Next time we return to Object Oriented Programming.

More Playing, Less Programming

In this entry we will explore the wonderful world of the Cellular Automaton (CA). Our entry into this world will be provided by the program Cafun. Cafun is written in Java and will run on any system that has a current Java Runtime Environment (JRE). I have run it on Linux and Windows. The screen shots you will see later in the entry are from the Windows environment. I encourage you to download and run the program, exploring as many of the samples that they provide before going further. I'll wait for you.

One of the classic CAs that is included with Cafun is Conway's Game of Life, we will focus on Life as the basis for one of our custom rule sets.

What is a Cellular Automaton?
As someone whose connection with mathematics is as a "recreational mathematician" I will provide my own understanding for what a CA is. For more complete and precise explanations you look to Wiki-pedia and to this introductory article.

A Cellular Automaton is a "discrete state system". What does that mean? It means that the CA system is made up of discrete units (cells) and it tracks the what state the cell is in over time. The state that the cell is in is governed by two components, it's current state and the states of its neighbors. The great John Von Neumann invented the CA concept and used a neighborhood consisting of the four cells that are directly above, below, left and right of the cell being checked. More often the neighborhood used is the Moore neighborhood named for Edward F Moore. This neighborhood consists of the eight cells that surround the current cell. This is what Conway used for his Game of Life (GoL). It is also the default neighborhood for Cafun . GoL was made famous by the late Martin Gardner in and article in Scientific American in October of 1970.

The second part of building a CA are the rules. The "Life rules" set out by Conway are very simple:

1. Cells have two states, on and off
2. If a cell is on and it is surrounded by 2 or 3 other on cells it will remain on
3. If a cell is off and is surrounded by exactly 3 other on cells it will turn on
4. In all other cases a cell that is on will turn off and a cell that is off will stay off.

These very simple rules were originally modeled on a Go board (19x19 grid) with Go stones and on graph paper. Programs that implement the GoL rules have been popular as exercises in computer programming for a long time.

Conway's Game of Life
Let's examine the GoL rules in Cafun . Load up CAFun and open the Simulation "Conway's Game of Life" from the "Classic" folder of included simulations. Do NOT open the default universe when prompted. We're going to look at one of the classic examples of taking a simple pattern and watching it turn into something more complex. Zoom the view to 800% of normal (400% might work if you are using a lower resolution screen). Draw a small + in the middle of the field. (see screenshot)

Using the step (single green arrow) control step through 6 "generations".  You should end up with 4 lines of 3 cells each arranged like a square missing it's corners. From this stage onward you will alternate between this pattern and the pattern you get when you press the step button once more. The lines rotate 90 degrees. The single line is called a "blinker", this pattern of lines is known as "traffic lights". It is one of the many "meta-stable" structures that GoL creates.  To see an actual stable structure arise use the Fill tool and fill the screen with Dead cells. Use the pencil tool and create a pattern of four cells that looks like the L shaped piece in Tetris. (A 3 cell line with one cell off the end to one side. It doesn't matter where you place the one cell.) Click the single step button 4 times. The resulting shape is a hexagon that is stable. All of the Alive cells have 2 neighbors so they don't die. You can continue to put in simple shapes and see what happens. If you just want to create a random pattern select the paint brush tool. Right click on the field and select Stroke Size - 10 Cells and Stroke Intensity - Low. You may want to Zoom out before you do this. Make some strokes on the screen. Then press the "Go" button (the double arrow) and watch what happens. If you leave it on normal speed it will move pretty fast. There is a Simulation Speed setting on the Utilities menu. You may want to set that to "Slow Motion" to get a better view.

Wireworld
Another of the CAs in the Classic folder of Cafun is Wireworld. The link takes you to Karl Scherer's definitive site on this CA that was created by Brian Silverman and featured in Scientific American by A. K. Dewdney in January 1990.

Wireworld has 4 cell types. Here are the types and their transition rules:

• Background: Background cells never change
• Wire: Wire cells will change into Electron Head cells when adjacent to 1 or 2 Electron Heads.
• Electron Head: An Electron Head always turns into an Electron Tail
• Electron Tail: An Electron Tail always turns into Wire

Cafun has a simulation file for Wireworld in the file named "Dewdney's Wire World". But before we can use it we need to correct an error in the rules. Using your favorite text editor (Notepad works in Windows) open the file "Dewdney's Wire World.xml" that is found in the simulations/classic directory in the Cafun directory. (Note: If you are using Notepad on Windows make sure to switch the open dialog to All Files from Text Files.) Look for the section that looks like this:

<cell-type color="192 192 192" id="Wire">
  <mutation cell-type="Electron-Head" priority="top">
    <condition cell-type="Electron-Head" min="1" max="1" />
  </mutation>
</cell-type>

This allows us to look at how Cafun defines its simulations. Cafun takes an object oriented approach to Cellular Automata. Each cell is an instance of a cell type. The rules are defined as mutations that can be considered methods of the type. For now we simply want to change the condition element so that the property max is equal to 2. So  change the condition line to look like this:

  <condition cell-type="Electron-Head" min="1" max="2" />

Save the file and return to CAFun. 

From the simulation menu select "Open Simulation" and select "Dewdney's Wire World". Again ignore the default universe. If you are continuing the same session from our experiments with GoL then you'll want to fill the field with Background cells.

Zoom back to 800% and use the pencil tool (make sure you have stroke size set to 1 and stroke intensity is set to high) to draw out the pattern in the next screenshot:

The loop at the left end of the wire serves as a pulse generator. To lengthen the distance between the pulses increase the size of the loop by adding wire cells to the parallel lines. For now simply run the simulation forward clicking the step control 4 or 5 times. You'll see the red and blue "pulse" split when it reaches the wire with new heads going down the wire and around the loop. This is what allows the loop to continue to pump out new pulses.

The interesting thing about Wireworld is that it provides the ability to model all kinds of electronic devices.  The Scherer site has a wealth of examples. We'll look at a simple example next. One of the simplest electronic components is the diode. We can simulate a diode in Wireworld with the pattern shown in the next screenshot:

In the middle of the wire add two wire cells above and below the line of the main wire. This creates a 3x2 rectangle. In the middle row of the rectangle make the right cell background creating what looks like a C in the middle of the wire. If you run the simulation you will see that the pulses with pass through this pattern.

Change the state of the cells in the middle row making the left cell background and the right cell wire. This has the effect of turning the diode around. Run the simulation again and you will see that the pulses that come up to the diode stop at the diode. This pattern blocks the pulses because the far end of the wire is connected to a side that will always have 3 electron heads if it has any and that does not create a new head on the wire. I encourage you to experiment with creating some of the other patterns that Scherer has on his site to play with Wireworld.

Next time

I have an extended version of the GoL rules that adds some color and a way to start with a random population that I will publish in then next entry and make available for download via Google Docs. The randomization idea comes from some BASIC programs in the book Exploring the Geometry of Nature by Edward Rietman. We'll use this file to explore the various aspects of a Cafun simulation file.

Come to the June 8th TCPC general meeting where Alice and Cafun will be part of the Software Showcase.

The language of Objects

I promised you last time that I would go over some of the terminology associated with object oriented programming (OOP) this time around. So let's do it using Alice. Start up Alice and create a new world using the Space template. Click the Add Objects button and scroll until you find the Space category and select it. Here is our first term associate with OOP, class. At the top of each entry in gallery it reads "Class something or other". Select Class LunarLander and add one to your scene.

Class and Instance - Making Objects
All OOP environments establish a class hierarchy. At the top, or root, of this hierarchy is usually a class called object. The object class isn't usually used to create actual objects, or instances, it is often called a meta-class. A meta-class is a class that is used to define other classes. OOP takes much of its structural ideas from how we deal with things in the real world. I'll use a real world example that I've used in the past when teaching programming courses.

For this thought experiment I want you to imagine that you have several writing instruments in front of you: a #2 pencil, a blue ball point pen, a red ball point pen and a black felt tip marker. Our object hierarchy will look something like this:

Object
  |---->WritingInstrument
               |---------->Pencil
               |---------->Pen
                            |---->BallPoint
                            |---->FeltTip


The classes don't create anything in our program, or in the case of Alice, in our scene. The class is a template, a definition of what an object might be. Two other terms you need to know, superclass and subclass. When we look at the hierarchy, WritingInstrument is a subclass of Object and the superclass of pen and pencil. With the exception of the root class all classes are a subclass of some other class. All classes except those at the bottom of the hierarchy are also superclasses of the classes below them. Each class can be used to create multiple instances or objects in our program or scene. Let's do that now. Return to your Space scene and add two astronauts to the scene with the LunarLander. When you return to the main Alice screen you'll see that the Object tree in the window looks something like this:

You'll notice that we have two separate objects, astronaut and astronaut2, these are instances of the astronaut class.

Properties and Methods - Defining an instance
One of the things that a class defines are properties of an object. Properties are those things that describe and define an object. They are often defined at the highest level in the hierarchy where they are appropriate. Going back to our writing instrument example the properties of color and tip would be defined at the WritingInstrument level. All WritingInstruments would have these two properties. A property such as InkType would be defined at the level of Pen. We can see from this that BallPoint and FeltTip probably wouldn't be separate classes. Both are members of the pen class but with a different value for the tip property.

Methods define how an object behaves. Continuing with the writing instruments the most important method would be the write method. This is the process of how the object writes on a paper or some other surface. This method would be defined at the level of the superclass WritingInstrument, but with no function. The pen class would redefine, or overload, the method with something like, "Applies ink to paper". A pencil on the other hand would have it's write method be, "Leaves trail of graphite on paper."  In Alice any actions we define are called methods.

Two other terms often associated with OOP are encapsulation and polymorphism. Encapsulation is the idea that the object is self contained. It carries all of the information within its definition to exist within the program. When properly constructed an object can exist in multiple programs without need of anything from the containing program to define itself. We've already discussed the concept of polymorphism. It's the idea that subclasses can redefine a property or method with more specificity than the superclass. For example pencils may define tip as have one of the following values: sharpened, mechanical, replaceable. A pen would have a tip that might be: ball point, felt, nylon or nib. (That last one is for the fountain pen users in the group.) So each has a tip property but it is defined specific to the subclasses needs.

Alright enough of the language lessons, let's get our astronauts doing something. First things first let's identify our astronauts. In the object tree right click astronaut and select rename. Change the object's name to Neil. Repeat the process for astronaut2 naming it Buzz. Click on the + next to Buzz and open the list of objects that make up Buzz. Find the helmet object and open that up. Select the visor object and open that. In the space below the object tree select the Properties tab. For color set the visor color to red. Repeat that process for Neil setting his visor color to blue. Now we can tell the astronauts apart.

Add the following to your My First Method:

1. Drag a Do Together box into the window.
2. Drag 2 Do In Order boxes into the Do Together box
3. In the first Do In Order box add the following:
1. Click on Neil, select the Methods tab and drag a Neil Turn method into the box. Have him turn 0.25 turn right.
2. Drag the Wait option and set it below the turn option. Set the wait value to 1 second
3. Drag a Neil Move method and set the distance to Other, 2 meters.
4. In the second Do In Order box add the following:
1. Click on Buzz and select the methods tab. Drag the Buzz Move method and set the values to Up 0.5 meters
2. Add a 0.25 second wait
3. Add Buzz Move down 0.5 meters
4. Add Buzz Move up 1.0 meters
5. Add a 0.5 second wait
6. Add Buzz Move down 1.0 meters
5. Below the Do Together box add a Do In Order box.
6. Add the following to the Do in Order box:
1. Using Buzz add: Buzz turn to face lunarlander.ladder
2. Add Buzz Move To lunarlander.frontleg
3. Add Buzz Move To lunarlander.ladder
4. Click the Properties tab and drag the Opacity property to the Do In Order box and set the opacity to 0 (invisible)
5. Add a 1.0 second Wait
6. Using Neil add: Neil Turn to face lunarlander.ladder
7. Add Neil Move To lunarlander.frontleg
8. Add Neil Move To lunarlander.ladder
9. Click Properties tab and drag the Opacity property to the Do In Order and set the opacity to 0.

Save your world and play the scene. Congratulations on your first moon walk.

Alice and the world of OOP

In this post we'll introduce Alice, described on the web site as:

Alice is an innovative 3D programming environment that makes it easy to create an animation for telling a story, playing an interactive game, or a video to share on the web. Alice is a teaching tool for introductory computing. It uses 3D graphics and a drag-and-drop interface to facilitate a more engaging, less frustrating first programming experience.

The splash screen for the software describes as a free gift from Carnegie Mellon. We'll be using version 2.2 for Windows in these examples.


In this entry we'll build a simple Alice world with one object and a few instructions. Download and install Alice 2.2 from the alice.org website.

Playing in the Sand
When you start Alice you will presented with an initial dialog box that is positioned on the tutorial tab. I encourage you to do the tutorials, but for now click on the Template tab. Select the Sand template and click Open. I want you to think about what you are doing and play with the software. As such I will not be including any screen captures with this exercise. Whatever you get is "correct".

The main Alice window is divided into several parts. In the top center is a small preview window of the world. In the lower right is a small green button labeled Add Objects. Click that button to open the object gallery. You will see that Alice provides a wealth of objects to play with. Scroll the object groups list until you find the Sports category. Click on the Sports category and then select Beach Ball from the list of available objects. Click the Add Instance to World button. Then click the Done button in the gallery. You should now be back at the main window with a beach ball sitting on your sand.

Let's make our beach ball do something and then we'll talk terminology and what the different areas of the main window indicate. We'll be working in the section of the screen labeled world.my first method. We won't worry about the parameter and variable sections right now. We're going to add some actions where it currently says Do Nothing. At the bottom of this section you will see several process control instructions. Click on the Do In Order instruction and drag it in place of the Do Nothing instruction.

In the upper left of the screen you will see a list of all the objects in your world. Click on the beachBall object. This will change the contents of the lower left pane in the window. It now displays things related the beach ball. Make sure that the Methods tab is selected. (This should be the default.)  The first instruction listed in the methods area is beachBall move. Click on the method and drag it into the window where the Do Nothing indicator is below the Do In Order instruction. You will then be prompted to select a direction and an amount. Select up and 5 meters to have your instruction added to the method. Save your world using the option from the File menu. Then click the Play button in the upper left. The Alice World window will open and you will see your beach ball rise into the air and out of view. Congratulations you've built your first Alice world! Let's add some additional instructions to make it a little more satisfying.

What goes up...
Let's add an instruction that brings the ball back down to the sand. Drag another copy of the beachBall move method into our world method pain. This time reverse the instructions and have it move down 5 meters. Save your world and then Play it. Better the ball goes up and then comes back down.

Let's enhance the process with a little sound. In the method list find the beachBall play sound method. Drag it below the second beachBall move. Select thud1 as the sound to play. Save and play your world. Not great but at least there some audio. We'll add one more sound that will require us to modify the program a little bit. Grab the Do Together instruction from below the main method code. Drag it up above the first beachBall move instructions and drop. Drag and move the first beachBall move instruction into the Do Together instruction. Then drag a new beachBall play sound instruction into the Do Together grouping. Select the whoosh1 sound to play. Save your world then click Play.

Much more satisfying as the ball makes a sound as it flies up and another as it lands. Experiment with this world and also the tutorial worlds. Next time we'll explore the terminology of Object Oriented Programming and how that applies to Alice.

Moving Beepers

As promised in the previous post here is a world and some code for moving beepers.

First the world definition:
robot 2 2 N 0
wall 2 2 W 8
wall 2 9 N 8
wall 9 2 E 8
wall 2 2 S 8
wall 6 2 W 3
wall 6 7 W 3
beepers 5 9 1

If you saved the "two rooms" world file this is the same thing with a couple of changes. First off the last number on the robot line is now 0. This indicates that Guido starts off with no beepers in his beeper bag. The other change is the addition of the beepers line at the end.

Now for some code. Since we don't have an indicator of when to stop, like the bag full of beepers in the previous post, we need to do a counted loop. I made some changes in approach to allow counting the corners that the robot hits. The code looks like this:

define turnright:
    do 3:
        turnleft

do 8:
    while front_is_clear:
        if left_is_clear:
            while left_is_clear:
                turnleft
                move
        else:
            move
    turnright
    if any_beepers_in_beeper_bag:
        if not_next_to_a_beeper:
            putbeeper
    else:
        if next_to_a_beeper:
            pickbeeper   
turnoff

The main thing here is that we are looking for corners so the while loop is controlled by the front_is_clear condition.

Changes to try: Put the do 8 loop inside of another loop, for example make a do 4 loop. Then indent all of the rest of the code in by 4 spaces at the beginning of the line. Change the number beepers at the point indicated to 4. Run the program and GvR should do 4 laps and place one beeper in each corner of the "second" room.

That's it for now. Next time we'll switch gears to Alice for a little while.

Beep, Beep!

There is a feature of GvR that we haven't yet explored, beepers. In this first look at beepers we will simply have GvR place some beepers on the map. But we'll also build on what we've learned so far as we do it.

Two rooms, No View

To start with we'll need a map for our program. Two things you'll notice about the following map code that is different than what we've had before. First the last number in the robot line is not zero. This indicates the number of beepers in GvR's beeper bag. We'll start with 8, because there will be eight corners on this map. The second change is the addition of a number at the end of the wall statements in the map file. These numbers indicate the length of the wall, up or to the right, from the starting position, up for NS walls, right for EW walls. Enter the following into the world editor and save it as tworooms.wld

robot 2 2 N 8
wall 2 2 W 8
wall 2 9 N 8
wall 9 2 E 8
wall 2 2 S 8
wall 6 2 W 3
wall 6 7 W 3

Once the code is entered and saved, click the reload button. You should have something that looks like this:

 

The plan is to have GvR place a beeper in each corner of the room. One of the sample programs provided on the GvR site shows how to have the robot hug a wall on its right as it moves around. We'll do something similar but hug the wall on the left. When we hit a corner we'll need to turn right so we'll include our turnright definition in this program. So let's break down the steps:

1. Place a beeper in the corner that we are starting in.

2. Move forward along the wall until we hit the corner

3. Place a beeper in the corner

4. Turn right

5. Repeat steps 2-4 for each of the remaining corners on the map.

Seems simple enough. We'll make use of some of the conditions that GvR can test. These are listed on the Language Reference tab of the GvR interface. To start with we'll need the left_is_blocked and front_is_clear conditions.

Let's get started. First thing we do is define the turnright command.

define turnright:
    do 3:
        turnleft

The first step in our list of steps is easy. You place a beeper by using the putbeeper command.

Following the left wall is done by making sure that the left side is always blocked, using the left_is_blocked condition. The next thing we need to know is whether we can move forward. To move forward the front must be clear. So we check front_is_clear and move if it is. If the front is not clear then we are in a corner. So place a beeper and turn right. Here's the code for that.

while left_is_blocked:

    if front_is_clear:

        move

    else:

        putbeeper

        turnright

We've seen the while command in our first exercise. It will loop will that condition is true. The if command is what we call a flow control statement in programming. It will allow us to do a group (or block) of commands based on the results of the conditional test. In this case we check if the front is clear, if it is we move. If it's not then the else clause is executed. In this case we put a beeper and turn right.  Seems simple enough.

Don't for get to include the turnoff command at the end of your program.

Once you've got your code in, save it then click Reload and Execute.

Did the program do what we wanted? Not really, did it. There's one piece missing from our initial analysis and from this code. What do we have the robot do when it reaches the opening in the wall? If we want to follow a wall on the left then when we reach an opening we know we can move to the left. So while there is no wall on our left we turn left and move forward. Use the following code:

while left_is_clear:

    turnleft

    move

Place this code before the turnoff command and save your program. Then Reload and Execute to see what happens. Better? GvR should have made it around the wall and be ready to follow the left hand wall again. How do you start him up again? Since we know we'll hit the opening twice we could try putting everything inside a do 2: loop. Give that a try and see  what happens. We're getting close. GvR stops after making back into the first room. But he still has one beeper to place to finish the task. You could up the loop to 3, but I'll tell you that an error would be generated when we attempt to place a beeper with none in the bag. What follows is my final version of this program that will place beepers in every corner and shutdown the robot when it returns to its starting place. There's a repeat of the check on beepers when we hit the corner. Again if we attempt to place a beeper and there is none the program will error. Also this shows that the end of the program, the turnoff command, isn't always at the end of the code.

define turnright:
    do 3:
        turnleft

putbeeper

while any_beepers_in_beeper_bag:
    while left_is_blocked:
        if front_is_clear:
            move
        elif any_beepers_in_beeper_bag:
            putbeeper
            turnright
        else:
            turnoff
    while left_is_clear:
        turnleft
        move

That's it for now. Here's something to try on your own. Right a program that looks for beepers in the corners of the room and if it finds one moves it to the next unoccupied corner. You can place beepers on the map in a world file using the beeper instruction. It includes the coordinates and the number of beepers. You might want to play with the GvR world builder to learn the syntax.

I'll post a version of this program in about a week so you can check your code against mine. 

GvR:Teaching your robot new tricks

We will look at the same topic here that is addressed in Tutorial 5 of the GvR lessons. If you've worked through the lessons this will be review. If not you may want to look at that after you've read this.

As we saw in the previous post on GvR the robot is limited to moving forward and turning left. This may seem like an artificial limitation but I'll give you an example of a simple robot, built with Lego Mindstorms that had the same limitations. The mind storms kit came with two motors. If you wanted a mobile robot that did more than move you had to accomplish the movement with one motor. Working from plans published online and in some Mindstorms books I had, I built a robot that was similar in function to GvR. One motor was used to move the robot and the right (or left) wheel was setup with a "ratchet gear". Basically a piece was used to keep the gear from moving backward. So when the motor ran backward the ratcheted wheel couldn't turn. The result was the robot moved forward and turned when the motor ran backward. Turning a particular direction was a the result of running the motor backward for a certain amount of time.

While GvR has a limited number of commands it does have a define command. The define command allows you to create new commands for GvR by stringing together combinations of the basic commands and those that you have defined. We will define a few new commands, including the one in Tutorial 5, and then put some of them to work.

First things first we will create a simple world file that places GvR in center of the bottom row of the map. (Note: this assumes the default window when you start GvR.) Enter the following into the world editor and save it as bottomcenter.wld:

robot 5 1 N 0

The next thing  we'll do is define the turnright command as done in tutorial 5.

define turnright:
    turnleft
    turnleft
    turnleft

Enter this into the code window. If you were to click the Execute button at this point you would get an out of instructions error with no apparent action. The system behaves the same as when there is no code in the Code Window. So let's have the robot move in a zig zag pattern. We'll incorporate the looping that we did in the last entry and have the robot move ahead a few spaces on the map. Add the following below the define statement in the code window:

do 2:
    turnleft
    move
    turnright
    move

do 2:
    turnright
    move
    turnleft
    move
turnoff

Click the reload button and then the Execute button and watch what happens. The end result is the robot 4 spaces up from where it started.facing north. Let's add another command. Add the following below the last turnleft in the definition of turnright and above the first do 2: in the command group.


define turnaround:
    turnleft
    turnleft

This command will turn the robot around so it can reverse direction. You may want to save the program at this time. Give a name you'll remember. If we Reload and Execute now nothing will have changed. We have defined the new command but we haven't used it. So add the following lines before the turnoff command:

turnaround
do 4:
    move
turnaround

Save your file again (use a different name if you want to preserve the previous program). Click Reload and the click Execute. Hopefully GvR ends up where he started. Remember that if the robot is moving to fast you can select "Set Speed" from the Setup menu and slow it down. If you want to examine what it does step by step use the Step button instead of the Execute button.

We'll define one more new command that will include one of our other new commands, to show that once you define a new command you can use it anywhere you use a built in command. Then we'll add it into our program just to make sure it works.

The new define looks like this:

define backup:
    turnaround
    move
    turnaround

It should be added to the code window after the turnaround define before the movement commands. It is important that it come after the definition of turnaround or it will generate an error.

Once you've done that add the following before the first turnaround command in the existing code.

move

backup

Save the program, Reload and Execute. 

Your final program will look like this:

define turnright:
    turnleft
    turnleft
    turnleft

define turnaround:
    turnleft
    turnleft

define backup:
    turnaround
    move
    turnaround

do 2:
    turnleft
    move
    turnright
    move

do 2:
    turnright
    move
    turnleft
    move

move
backup

turnaround
do 4:
    move
turnaround

turnoff

You might want to save a copy of the program that includes only the defines. This can be useful for adding those defines to other programs. Remember that once you close GvR or reload with a different program, those defined commands will be forgotten.

Experiment with your new commands and maybe add some more. More next time.