1 INTRODUCTIONNick Parlante, a Lecturer at Stanford University, invented a pedagogical game entitled "Darwin’s World". The original specification (for Pascal) was published and presented at SIGCSE in 1999. Many variations have been published more recently. http://nifty.stanford.edu/darwin/ http://users.dickinson.edu/~braught/NSFIntegrating/course/labs/darwin/handout.html In Darwin’s world the user creates robot-like graphical creatures with behavior defined by a simple programming language. These creatures migrate around a small two-dimensional grid, each according to its simple program created by the user. The GUI application that controls and displays the location of these creatures must interpret the program instructions supplied in a simple text file for each creature type in real-time and display the movement and behavior of these creatures. Since some creatures may "infect" another creature in an adjacent grid location, converting the infected creature into the same type as the creature administering the infection, the population of the various creature types changes over time although the total number of creatures remains constant. The application tracks and displays the population dynamics as the simulation evolves. New creature types may be created by supplying a text file that contains the "program" that the application interprets. This necessitates changes to the GUI that displays the dynamics of the simulation. This application has become popular among computer science educators because the application is fun to observe, fun for many students to create and provides a rich assortment of concepts that are useful in computer science and software development. This application is being presented in a more advanced programming course that features the effective use of the C# programming language and the .NET framework. As a quick example of how to "program" a creature (we call this creature Trap and its file is "Trap.txt") consider the instructions given below: What does this user supplied program mean? The first line of code is line 0. Each creature has a defined direction of movement that is either north, east, south or west. An "enemy" is any creature whose type is different than the given creature’s type. The first instruction (on line 0) stipulates that if the Trap creature is facing an enemy in the cell location one away from it in the direction that the Trap creature is pointing then transfer control to the instruction in line 3, the "infect" instruction. This "infect" instruction causes the enemy creature to become a Trap creature. Its color, and symbol change (for display purposes) but most importantly it acquires the program given in the "Trap.txt" file so that its future behavior is that of a Trap creature. If the instruction on line 0 is false (the adjacent cell is empty, a boundary or another Trap creature), then line 1 is executed. This line causes the Trap creature to rotate left by 90 degrees (e.g. if it was originally pointed north it is now pointed west). The last line of "code" in this simple program is denoted by a dot. So, the "program" for the Trap creature causes the Trap creature to remain in its initial grid location either rotating to the left with each move or infecting an adjacent creature if it is an enemy. A more complex creature, the Rover, is governed by the following program: The ifwall statement (on line 1) directs program execution to line 5 which contains the instruction ifrandom. This instruction directs control to line 8 with 50 percent probability (if it returns true) or the next line (line 6 containing the left instruction). So with equal chance the rover rotates either left or right if it encounters either a wall or another Rover creature in the adjacent cell that it is pointing to. If the adjacent cell is empty it performs the hop command (it vacates its current position and moves to the adjacent cell position). Like the Trap, the Rover is capable of infecting an enemy. But because it is mobile (always moves in the same direction until it encounters a wall or another Rover), its infection range extends potentially over the entire world (the entire grid). The simplest creature type is Food. Its program is given as: Food creatures cannot move or infect other creatures. They are essential fixed targets that rotate to the left and can be infected by other creatures. A more complex, created by the author, is Android. Its program is:
It starts by rotating either to the left or right by 90 degrees. Then its behavior is similar to Rover. So instead of moving in a straight line like the Rover creature, its motion is jagged. Like the Rover and Trap creatures, it too can infect enemy creatures in adjacent grid locations. Another complex creature, created by the author is the Hopper. Its program is: It is somewhat of a hybrid between an Android and a Rover with some capability shared by neither. The Hopper creature, like the Rover, first determines whether it can infect an enemy in the direction that it is facing. If not, it rotates either to the left or to the right if an enemy is to the left or right. Then it hops in the direction it is facing. The final creature, also created by the author, is the ChangeDirectionRover. Its program is: See whether you can figure out by reverse engineering the program what the behavior of the ChangeDirectionRover does (if the name of this creature does not already explain its behavior. The specifications for the GUI simulation that we are to construct are given below. 2 SPECIFICATIONS
A screen shot of a game that has just been initialized is shown next. A screen shot of this game in progress after 16 move cycles is shown below (each game displays different emergent population dynamics – that makes the game fun to observe):
It is noted that for this run of the simulation, after only 16 move cycles, the population of Hopper creatures is indicated as one.There is no Hopper creature shown when this screen snapshot was taken. That is because population updates are done only at the end of a move cycle but creature updates are done as soon as a creature moves. So upon the completion of move cycle 16, the population of Hopper creatures will be zero. 3 Design and Implementation Three enum types, OpCode, Direction and CreatureType, are defined to support the implementation. These are presented below. (Using statements are omitted throughout to save space but are included in the actual implementation). Next a class Instruction that encapsulates each line of the user’s program code is presented. An instruction object encapsulates an op code and line number. The next design decision concerns the use of a few global entities that are acessible throughout the application domain. These are defined in class Global. A Dictionary, actions, that asssociates each OpCode with some action, defined as a delegate type TakeAction, is defined. So the "data" that is associated with each OpCode key is in fact a method that represents an instance of the TakeAction delegate type. In other words we are associating concrete actions with each OpCode key in the dictionary. The TakeAction delegate type is defined as: The game model is defined as a two-dimensional array of type Creature, yet to be defined. The class Creature is implemented next. It is tempting to create a hierarchy of concrete classes that are descendents of an abstract Creature class. This design defines only one concrete Creature class that contains a list of instructions that defines its behavior. The basis of this decision is that creatures differ in their cosmetic representation (their symbol, color and most importantly instruction set). These attributes can best be modeled using a whole-part relationship rather than an inheritance relationship. Class Creature is given next. Each creature is modeled as containing a List containing base-type Instruction. The BuildInstructions method parses each line of the file supplied by the user and constructs this list. The Move command takes the game model class World (yet to be defined) as a parameter. A variable action is obtained from the global Dictionary called actions. The action is invoked using: The concrete method that is executed is defined in the World class and stored in the globally available actions. The command FireDisplay is invoked on the world object passed to the creature from the World model class. This is how each creature object notifes the GUI (yet to be defined) about its movement. The Move command in class Creature is our interpreter. It moves from one instruction to another and associates each instruction with a stored action command in the global dictionary table. In the sequel article, "Darwin’s World Simulation in C#: The Model/View Classes", to be published in the March/April, 2010 issue of JOT, the details of event handling and link the World class to the WorldUI class will be presented and discussed. About the author
Richard Wiener: "Darwin’s World Simulation in C#: An Interpreter", in Journal of Object Technology, vol. 9, no. 1, January - February 2009, pp 57-63 http://www.jot.fm/issues/issue_2010_01/column6/ |
||||||||||
