Course:CPSC312-2018-Conways-Darwinian-Nightmare
Conway’s Darwinian Nightmare
Authors: Al Smith, Tristan MacKinlay, Rob Willoughby
What is the problem?
We propose to implement a simple graphical multiplayer game in a purely functional programming paradigm, using Haskell. The following synopsis assumes some familiarity with Conway's Game Of Life, upon which the game is based.
What is the something extra?
The basic logic of Conway's cellular automaton will remain intact, but there is an added competitive aspect: each player will initially deploy a limited number of cells (identified by colour or some other graphical element). The game will then run for a fixed number of iterations in a modified version of the classic Game Of Life rules. After this, if a player's cells have not been completely eliminated, they will have an opportunity to deploy reinforcements and try to survive another set of game iterations. The iterations stage may become longer as the game goes on, requiring greater foresight and planning to survive. The winner is the last primitive civilization standing. If time permits, we would like to include optional AI opponents.
The purpose of this project is to investigate the feasibility of a real-time, graphical, multiplayer game implemented entirely in Haskell, using simultaneous, persistent IO and somewhat sophisticated graphics.
What did we learn from doing this?
Overall, this turned out to be more difficult that we expected. We decided to implement the algorithm using our own data structure, a Quad Tree, rather than the usual grid made up of arrays. This was with an eye to potentially implementing the Hashlife algorithm which is an optimized version of the standard Conway's Game of Life algorithm. It uses hashing and memoization to significantly speed up the process of evolving the next generation (more details can be found here: An Algorithm for Compressing Space and Time). This idea ran into trouble however given that hash-consing and memoization generally requires some notion of pointer equality. We were able to find a reference to this in "Stretching the storage manager: weak pointers and stable names in Haskell" by Simon Peyton Jones, Simon Marlow, and Conal Elliott; however, given the scope of the course and the project we decided to not implement that. Instead, we just described the Life universe using a Quad Tree representation, designed a function to create a basic board for quick testing purposes and then created a UI interface to interact with the game. We ran into some issues handling recursive calls down the Quad Tree and how to define a base case without getting into an infinite loop due to some incorrect assumptions about how lazy evaluation would handle that. While functional programming excelled at handling the specific manipulations required to determing the next generation, it was not as well suited for the update step afterwards. That is because of immutable objects in Haskell. We needed to recreate the entire universe for each and every generation rather than simply updating the appropriate fields in a universe object as one might do in Java. This operation seemed to be more expensive than it had to be; a more optimized version of the game might try to combine an object-oriented approach with a functional one. Overall, we all definitely feel more comfortable with Haskell specifically and functional programming overall even if it may not have yielded the optimal approach for Conway's Game of Life.
Links to code etc
https://github.com/wolf-tickets/conways-fight-for-survival
Alternate implementation where the grid is represented as a String.