Darwin
From CS315
Written by Mussie Araya
Contents |
Darwin
Introduction
Darwin is a program that simulates Darwin's World. It is the current project #4 in CS 315 which is an algorithms and data structure class taught by Dr. Downing at University of Texas.
Darwin's world
Darwin's World is a two dimensional grid named after Charles Darwin. Each square in the grid can contain at most one creature. Each creature belongs to a specie and has a direction and contains a program counter. In Darwin's World there is a set of instructions defined for each specie. Each creature is given a turn by Darwin in a sequential manner. Upon reaching its turn each creature executes a list of instruction specifies by its program counter.
Instructions
In Darwin's World there are possible nine instructions defined for a specie. There are classified as two types of instructions. The classifications are action instruction and control instructions. There are three control instructions and six action instructions. Upon a turn of execution determined by Darwin, each creature can execute one action instruction during a turn. Each instruction is executed in the order given. For an instance for the below instruction given by a program counter to the specified creature
- hop
- go 0
- if_empty 4
- left
- right
the creature begins executing instruction #1.
Here is a list of instruction.
| Type of Instruction | Instruction | Description of Instruction |
|---|---|---|
| Action | hop | if the space ahead is empty, move forward, otherwise, do nothing |
| Action | Left | turn to face left |
| Action | Right | turn to face right |
| Action | Infect | if the space ahead contains a creature of a different species,
change that creature to be of your species, otherwise, do nothing resets the program counter, but leaves the direction unchanged. |
| Action | if_empty n | If the space ahead is empty, go to line n, otherwise, go to the next line. |
| Action | if_wall n | If the space ahead is a wall, go to line n, otherwise, go to the next line. |
| Control | if_random n | Create java.util.Random(0).
If java.util.Random.nextBoolean() returns true, go to line n. |
| Control | if_enemy n | If the space ahead contains a creature of a different species,
go to line n, otherwise, go to the next line. |
| Control | go n | go to line n |
Input
There is no input for this program.
Output
Darwin will write its output to System.out. The output contains a grid which represents Darwin's world. The location of each creature will be notes by the species name. In the output, a number of moves will be displayed and the number of moves is determined by the programmer of the interface.
Anatomy Of Program
In the program Darwin, the Darwin is represented by a class. Darwin's world is an object of this class. All creatures are represented by a class and each creature is an object of this class. The three different properties of a creature such as the species it belongs, the direction it has and its program counter that store the instructions to be executed are all objects of the classes Species, Direction and Operation respectively. Each creature is placed in Darwin by an application class called Application. The design and implementation of a large part of the API has been left to the writers of the program.
Design Of Program
Is designing the grid that makes up Darwin's World, there are two common approaches in which the grid can be represented. One common approach is to make the grid a grid of creatures. The second a rather more complicated way is to represent the grid as a matrix of numbers where in each point in the grid, a number or an index of a creature is stored. If this approached is taken it is required for each creature to keep track of its position. Then in the application class a Darwin object is created with its specified dimension. At specified locations a un specied creature with a given direction and species it belongs to and its location on the grid is created. Darwin simulates a number of turns specified by application interface. During each move, Darwin traverses the grid and if a creature is located, the current instruction is obtained from the creature class. If the current instruction turns out to be a control structure, control is transfered in the instruction list until an action instruction is obtained. Then each action instruction is executed by a call to the corresponding method that is designed to perform the execution. At the end of each move the current content of the grid is displayed. The design of the program can be summarized as a program of three classes. The class Darwin consists of a grid and elements of creatures and implements the execution of the instruction. The class creatures consists of a species,and a direction as its elements plus a program counter. Each specie consists of a name and a set of instructions as its elements. The Darwin class directly communicates with the creature class and the creature class communicates directly with the specie class.
Testing and Verification
The program which simulates Darwin's World is tested and verified by Brandon Streiff. This current project and all project for CS 315 are tested and verified by Brandon Streiff. However in this simulation a very large portion of the API will be designed and defined by the programmer therefore the validity of the program will be verified by the nature of the output.
