Assignment 2 Assignment 2 from chaos comes order In 1928 David Hilbert proposed the Entscheidungsproblem. The Entscheidungsproblem asks for an algorithm which can answer “yes” or “no” to any first-order statement of logic. This seemingly esoteric mathematical question was pivotal in the conception of the computer on which you are reading this. It prompted Alonzo Church and then Alan Turing to formalise the notion of an algorithm, this led to the creation of Computer Science. Computer Science would then contribute back to maths a new branch of investigation, Chaos Theory. Chaos theory can only be fully demonstrated in the context of millions of computations. This was not practical before Computer Science and thus mathematicians in this field rely entirely on Computer Science. This “circle of academic life” is interesting indeed, but how does it affect us in COMP229? Langton’s Ant Langton’s Ant is a extremely simple agent which lives on a grid of squares which are either black or white. It lives according to the following rules: If it is on a black square it turns right, swaps the colour of the square it is on, and moves forwards one square. If it is on a white square it turns left, swaps the colour of the square it is on, and moves forwards one square. The fascinating thing about Langton’s Ant is that these simple rules create a pattern of black and white squares which is both completely chaotic and ordered! Langton’s Ant begins by moving around all over the place, creating a seemingly random pattern (which is not random at all, because it is always the same given the same starting conditions), but then amazingly starts building a “highway”. The highway is an infinitely repeating pattern. So there is first chaos, then order. Without computers, it is not practical to do enough calculations to get from the chaos to the order. If the ant is put on a finite grid it moves between periods of chaos and periods of order until the whole screen is (seemingly) random. Below is an implementation of Langton’s Ant where reaching one edge causes it to move to the opposite edge. If you are stuck staring staring at this, fascinated by either the chaos/order paradox or the emergence of complex behaviour from such simple rules, you are probably a Computer Scientist deep down. An interesting note is that there is one aspect in which Langton’s Ant is not chaotic at all. In Chaos theory, a chaotic system is extremely sensitive to its starting conditions. One of the emergent behaviours of Langton’s Ant is that no matter what the pattern of black and white is on the grid at the start, you will always get a highway eventually. Next is a specification summary for the assignment and below that are detailed instructions explaining the specification and giving details to help you write your solution. This assignment is quite easy if you have the game of life working already, so focus on getting that working (which will get you 15 marks) and then start on the changes for this assignment. Specification This is a summary only, see below for full details. (25 marks) Achieve a working cellular automaton (game of life) (10 marks) Add an Ant class and document it appropriately with JavaDoc (20 marks) All code is documented appropriately with JavaDoc (30 marks) The Ant behaves correctly (10 marks) When the ant reaches the edge of the screen it starts again on the opposite side (5 marks) The location of the ant is shown on the display (5 marks) The ant is animated. (5 marks) Instead of starting with an all white board, randomly generate a sequence of black and whites squares. Detailed Instructions Achieve a working cellular automaton (game of life) If you complete the gameoflife, with which you may get as much help as you like, you will get these marks. The grid of your automata must be 200 by 200 and each grid must be 4 pixels in size. Anything which displays a grid of cells where there is some animation happening on the cells will get you partial marks. Your final solution must have either a working game of life or a working Langton’s ant. Thus you don’t need to keep the game of life functionality if enough of the other functionality works. Add an Ant class and document it appropriately with JavaDoc The description above of Langton’s Ant is not actually a description of a Cellular Automaton in that the value at any cell is not defined in terms of the cells around it. Instead the rules are defined in terms of some ant. However, this system can be restated as a cellular automaton in various ways. The simplest to explain, but hardest to code, is to treat all 10 possible cell states (combinations of colour and ant direction) as separate “colours” on the board and to define cellular automaton rules which are equivalent to the ant rules. However, the simplest to conceive and to program is to create an ant object (from an Ant class) and query it to find out its location and direction when deciding whether a cell is black or white in the next generation. The following class diagram shows the Ant class which has been used in the Langton’s Ant program above and which you should use in your implementation. pRow and pCol are fields storing the ant’s location. env is a reference to the board on which the ant is sitting (it needs to know the colour of the square it is sitting on). dir is a variable which stores the direction the ant is facing (north, south, east or west). goingTo is a function which returns true if the next move of the ant is to move to the cell at row, col. isAt is a function which returns true if the ant’s current position is row, col. step() is a function which moves the and from it’s current location to its next location, updating the fields pRow, pCol and dir. In the class diagram we have made dir an enum but you may implement it any way you like. To get the marks for this section you don’t need the Ant class to be functional. Your marker will generate the JavaDoc for your project in Eclipse and as long as the documentation for this class is appropriate, you will get the marks. All code is documented appropriately with JavaDoc There will be many more classes in your cellular automaton than just Ant. These must all be correctly documented with JavaDoc so that when the marker generates the JavaDoc for your project using Eclipse they will have correct and linked documentation for the whole project. The Ant behaves correctly Implement the code in the Ant class so that the ant behaves according to the rules above. Using the Ant class, the implementation of the cellular automaton can be broken down into the following steps: Implement goingTo, isAt and step according to the rules for the ant In the cellular automata’s step function, loop through every cell in the grid and if the ant is going to be in this cell, change that cell’s state to have an ant if the ant is at this location, change the cell’s state to not have an ant and swap its colour. else the cell has the same state as it did in the last generation. Following such an algorithm requires each cell in the automata to have four states white without ant white with ant black without ant black with ant It is helpful to write functions which convert between black/white and ant/no-ant. Your ant should begin on a fully white grid at position 100,100. You get the marks if when we run the application we can see the distinctive “pattern” of Langton’s Ant appearing. It must get to the point of generating a “highway”. The location of the ant is shown on the display In the above example the ant is indicated by a red square. To get the marks your application must do the same. The direction of the ant does not need to be represented. The Ant is animated Instead of indicating the position of the ant with a red square, show a (tiny) image of an ant on the screen and ensure he is facing the right direction based on his state. Instead of starting with an all white board, randomly generate a sequence of black and whites squares. Using the Java random number generator, the initial state of the board is random.y allocated black squares. The simplest way to do this is to loop over every square and generate a random number between 0 and 1. If that number is less than 0.5, the square is black. Else the square is white. Mark modifiers If any of the following statements is true of your code, you will lose 5 marks (for each): nonsensical architecture single-letter variable names for anything but iteration variables program crashes during testing (it will be re-run but you will have a penalty). If any of the following statements is true of your code, you will lose 15 marks (for each): Not including a reference to code you have found elsewhere (except course texts/readings). Double-check your submission because if it does not compile, you will receive zero marks. Submission Instructions You must submit a zipped Eclipse project containing all the files needed to compile and run your program in Eclipse. Your submitted files must have your student number as it’s name and it must be a .zip file (not a tar file or a rar file, or any other type of archive, zip only.) To test if your submission will act this way, try importing it into a clean version of Eclipse on the lab computers before you submit it. by Matt Roberts
