Langton's Ant (Luca, Defne)
What is the problem?
We want to implement a version of Langton's Ant, a two-dimensional universal Turing machine. The description is the following:
The "world" is a grid, and each square can either be black or white. The ant starts from the centre of the grid, and moves according to these rules (taken from Wikipedia):
- At a white square, turn 90° clockwise, flip the colour of the square, move forward one unit
- At a black square, turn 90° counter-clockwise, flip the colour of the square, move forward one unit
Langton's Ant is particularly interesting because through these simple rules of interaction complicated patterns emerge. Initially the pattern and the ants movement appears random, but after around 10,000 steps the ant begins to construct a pattern. The pattern is a repeating "highway" that will continue until the ant reaches the edge of the grid. Langton's ant is a form of cellular automata where order emerges from chaos.
What is the something extra?
We used the Gloss library to visualize the simulation.
The user of the application can change the initial configuration of the world, specifically:
- User can initialize how many steps the ant takes per second -- in other words the speed of the ant.
- User can set the colors of the grid.
- The # of steps is displayed.
What did we learn from doing this?
Functional coding is very suitable when implementing Langton's Ant or other examples of cellular automata. Given that the state of the grid and the ant depends on their current and previous state, Haskell's immutable data structures ensure that changes to the state do not have any unexpected side affects. Haskell ensures that each iteration of Langton's Ant is a distinct and predictable operation. We found that creating abstractions and expressive functions for Langton's Ant as was quite intuitive as the core concept of the game revolves around a small set of very simple interactions. However, we found that some functions that are trivial to write in other languages were much more difficult to implement in Haskell. In particular, updating the grid which we abstracted as a 2D matrix of cells proved to be quite difficult because data structures are not mutable. We also used the Gloss library to render the simulation. Learning the library took awhile, and we ran into some obstacles when we tried combining different GUI libraries, which didn't work due to some technical reasons. However, this obstacle allowed us to realize that there are simpler and more practical ways of achieving the result we wanted. Finally, after looking at some other examples it was pretty straightforward to render Langton's Ant.
Work division (TBD)
How was the workload divided? Who did what? (This can be in a private communication to the TA if you do not want it to be public).