Go语言生命游戏 GameofLife GOL

目录

• CSA Coursework: Game of Life
  • Task Overview
    • Introduction
    • Skeleton Code
  • Stage 1 - Parallel Implementation
    • Step 1
    • Step 2
    • Step 3
    • Step 4
    • Step 5
    • Success Criteria
  • effect drawing

CSA Coursework: Game of Life

This is the Computer Systems A summative coursework. The coursework is worth 80% of the unit mark. It is to be completed in your programming pairs. You must report any change to your pairing to the unit director before starting your assignment. It runs over 4 weeks (5 weeks including the reading week) and the deadline for submitting all your work is Friday 3rd December 13:00.

Talk to each other regularly and make sure you manage your team well. Let us know about issues before they grow to affect your team’s performance. It is important to carefully manage your time for this assignment. Do not spend hours trying to debug on your own; use pair programming, seek help from our teaching assistants during scheduled labs and ask questions on Teams.

Do not plagiarise. Both team members should understand all code developed in detail.

Task Overview

Introduction

The British mathematician John Horton Conway devised a cellular automaton named ‘The Game of Life’. The game resides on a 2-valued 2D matrix, i.e. a binary image, where the cells can either be ‘alive’ (pixel value 255 - white) or ‘dead’ (pixel value 0 - black). The game evolution is determined by its initial state and requires no further input. Every cell interacts with its eight neighbour pixels: cells that are horizontally, vertically, or diagonally adjacent. At each matrix update in time the following transitions may occur to create the next evolution of the domain:

• any live cell with fewer than two live neighbours dies
• any live cell with two or three live neighbours is unaffected
• any live cell with more than three live neighbours dies
• any dead cell with exactly three live neighbours becomes alive

Consider the image to be on a closed domain (pixels on the top row are connected to pixels at the bottom row, pixels on the right are connected to pixels on the left and vice versa). A user can only interact with the Game of Life by creating an initial configuration and observing how it evolves. Note that evolving such complex, deterministic systems is an important application of scientific computing, often making use of parallel architectures and concurrent programs running on large computing farms.

Your task is to design and implement programs which simulate the Game of Life on an image matrix.

Skeleton Code

To help you along, you are given a simple skeleton project. The skeleton includes tests and an SDL-based visualiser. All parts of the skeleton are commented. All the code has been written in Go. You will not be required to write any C code. If you have any questions about the skeleton please ask a TA for help.

You must not modify any of the files ending in _test.go. We will be using these tests to judge the correctness of your implementation.

The skeleton code uses SDL. This is a basic graphics library which you already used in Imperative Programming unit. To install the library follow the following instructions:

• Linux Lab Machines - SDL should already be installed and working.
• Personal Ubuntu PCs - sudo apt install libsdl2-dev
• MacOS - brew install sdl2 or use the official .dmg installer.
• Other - Consult the official documentation or see our experimental instructions for running natively on Windows

Stage 1 - Parallel Implementation

In this stage, you are required to write code to evolve Game of Life using multiple worker goroutines on a single machine. Below are some suggested steps to help you get started. You are not required to follow them. Your implementation will be marked against the success criteria outlined below.

Step 1

Implement the Game of Life logic as it was described in the task introduction. We suggest starting with a single-threaded implementation that will serve as a starting point in subsequent steps. Your Game of Life should evolve for the number of turns specified in gol.Params.Turns. Your Game of Life should evolve the correct image specified by gol.Params.ImageWidth and gol.Params.ImageHeight.

The skeleton code starts three goroutines. The diagram below shows how they should interact with each other. Note that not all channels linking IO and the Distributor have been initialised for you. You will need to make them and add them to the distributorChannels and ioChannels structs. These structs are created in gol/gol.go.

Step1

You are not able to call methods directly on the IO goroutine. To use the IO, you will need to utilise channel communication. For reading in the initial PGM image, you will need the command, filename and input channels. Look at the file gol/io.go for details. The functions io.readPgmImage and startIo are particularly important in this step.

Your Game of Life code will interact with the user or the unit tests using the events channel. All events are defined in the file gol/event.go. In this step, you will only be working with the unit test TestGol. Therefore, you only need to send the FinalTurnComplete event.

Test your serial, single-threaded code using go test -v -run=TestGol/-1$. All the tests ran should pass.

Step 2

Step2

Parallelise your Game of Life so that it uses worker threads to calculate the new state of the board. You should implement a distributor that tasks different worker threads to operate on different parts of the image in parallel. The number of worker threads you should create is specified in gol.Params.Threads.

Note: You are free to design your system as you see fit, however, we encourage you to primarily use channels

Test your code using go test -v -run=TestGol. You can use tracing to verify the correct number of workers was used this time.

Step 3

Step3

The lab sheets included the use of a timer. Now using a ticker, report the number of cells that are still alive every 2 seconds. To report the count use the AliveCellsCount event.

Test your code using go test -v -run=TestAlive.

Step 4

Step4

Implement logic to output the state of the board after all turns have completed as a PGM image.

Test your code using go test -v -run=TestPgm. Finally, run go test -v and make sure all tests are passing.

Step 5

Step5

Implement logic to visualise the state of the game using SDL. You will need to use CellFlipped and TurnComplete events to achieve this. Look at sdl/loop.go for details. Don’t forget to send a CellFlipped event for all initially alive cells before processing any turns.

Also, implement the following control rules. Note that the goroutine running SDL provides you with a channel containing the relevant keypresses.

• If s is pressed, generate a PGM file with the current state of the board.
• If q is pressed, generate a PGM file with the current state of the board and then terminate the program. Your program should not continue to execute all turns set in gol.Params.Turns.
• If p is pressed, pause the processing and print the current turn that is being processed. If p is pressed again resume the processing and print "Continuing". It is not necessary for q and s to work while the execution is paused.

Test the visualisation and control rules by running go run .

Success Criteria

• Pass all test cases under TestGol, TestAlive and TestPgm.
• Use the correct number of workers as requested in gol.Params.
• Display the live progress of the game using SDL.
• Ensure that all keyboard control rules work correctly.
• Use benchmarks to measure the performance of your parallel program.
• The implementation must scale well with the number of worker threads.
• The implementation must be free of deadlocks and race conditions.

effect drawing

gol