In this project you will implement a simplifled version of John Horton Conway’s Game of Life.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Introduction

In this project you will implement a simplifled version of John Horton Conway’s Game of Life. The Game of Life is a particular model of cellular automaton, which is a method of modeling certain computations and interac- tions. Cellular automata theory is outside the scope of this class, but we can still explore this model.

The Game of Life models an infinite grid of cells, in which every cell is either alive or dead. A simple and deterministic set of rules is used to step through generations of these cells by determining whether, from one generation to the next, a particular cell lives on, dies, or creates life. We will simplify this model by placing it on a finite grid, but otherwise following the rules of the Game of Life.

Conway’s Game of Life is a well-studied model, as it exhibits some interesting properties. In fact, it has been proven that the Game of Life is computationally Turing complete, meaning that any computation that can be modeled by a digital computer can be performed by developing the correct starting position in the Game of Life and iterating until the desired result is computed as a pattern of cells.

This assignment will give you practice dealing with C arrays and references to arrays, including multi- dimensional arrays. It will give you practice in separating repeated computations out into functions. It will introduce the concept of modifying a program’s data model to simplify computation.

Like many real-world problems, this assignment will be mostly either entirely correct or entirely wrong. There will be a limited opportunity to get partial credit by following the instructions for output format closely even if your game is not capable of correct deterministic operation, but because errors in early generations will lead to rapid degeneration in later generations, correct operation is critical for signiflcant credit.

This document is long, but there is a reason for that. Please read it carefully and in its entirety before starting your assignment!

You will have two weeks to complete this project.

 

In Memoriam

John Conway passed away in April of 2020 of complications from COVID-19. The Game of Life, while possibly his most well known creation, is far from his only contribution to mathematics or computation.

The following Life input is attributed to Randall Munroe, author of the XKCD web comic. Following the rules in this document, it transforms into a “glider” that departs the disintegrating body and flies off to the upper right. In our implementation, it becomes a “block” still life (you can flnd these terms deflned in the resources linked later in this document), but in a complete implementation of Life it travels forever, upward and to the right, for an inflnite distance. You can flnd it as the input flle inputs/conway.life in the given code.

 

Rest in peace, John Horton Conway, 1937–2020.

 

1 Getting Started

You should read this entire handout and all of the given code before you get started. You should have received a GitHub Classroom invitation for this project. Follow it and check out the resulting repository.

 

It is probably best to read a good description of the Game of Life as your flrst step. I recommend the Wikipedia Article as a good starting point.

Some other good resources include:

• ConwayLife.com, a community for people exploring the Game of Life and its properties

• The LifeWiki, which contains an enormous amount of interesting and helpful information

 

2 Requirements

You are required to implement the rules of Conway’s Game of Life, with the change that all cells not displayed in the required viewport are always considered dead.

Your program must compute the rules of the Game of Life on a grid that is 80 cells wide by 24 cells high, assuming that all cells outside of this grid are dead. These constants are deflned in the given flle life.h as GRIDX anad GRIDY, respectively.

The rules of Life are simple, and applied to every cell in the grid in the exact same fashion. Life proceeds in generations, where the state of the cells in generation G entirely determines the state of the cells in generation G + 1. The state of each cell in generation G + 1 is determined by the state of its eight neighboring cells in generation G; speciflcally, the number of those cells that are alive or dead. The neighbors of a cell are the cells immediately to its left, right, and on the four diagonals between those cells. The rules for a cell c are as follows:

• If c is alive and has fewer than 2 live neighbors, it dies.

• If c is alive and has more than 3 live neighbors, it dies.

• If c is alive and has exactly 2 or 3 live neighbors, it remains alive.

• If c is dead and has exactly 3 live neighbors, it becomes alive.

The neighbors of the cell marked in the center of this grid are the cells marked in gray:

X

Your implementation will use the character 'X' to represent a live cell, and the space character ' ' to rep- resent a dead cell. There are two constants deflned in the given code, LIVE and DEAD, for this purpose.

Your implementation must accept two command line arguments, a fllename and a generation number. The fllename is a flle containing a starting state to be passed to the given function parse_life() (documented else- where in this handout), which will produce a grid with the initial state of the game, and the generation number is the generation which your program should output. Generation 0 is the starting state of the game as parsed by parse_life().

Upon reaching the stated generation, your program must output the state of the grid, using exactly the format described here. Any difference in format, including extra or missing whitespace, will result in reduced credit on this assignment. The grid should be output as follows:

• Every row of the GRIDY rows in the grid must be output as a single line of text ending in a newline.

• Every cell of the GRIDX cells in a row of the grid must be output as a single character, either an ASCII space for a dead cell or an ASCII X for a live cell.

Your output will therefore be exactly 24 lines of exactly 80 characters each. Any deviation from this output is incorrect. In particular, extra whitespace at the beginnings or ends of lines, for example, will look like extra dead cells.

Any invocation with fewer than one argument or more than two arguments should print an error message and exit (e.g., return from main()) with a non-zero exit status, with one exception: you may accept extra argu- ments beginning with a dash (-) character to enable different behaviors in your program for your own use in testing.

 

3 Given Code

You are given a signiflcant quantity of code, but it all essentially boils down to three things:

 

• Reading starting positions from flles on disk

• Clearing the terminal

• Constants

 

There are extensive comments in the given code to help you understand what you have been given.

You can flnd a parser for starting positions expressed in three common formats in src/parser.c. You do not need to read and understand this flle, but you may flnd it helpful for your understanding of C and your development as a programmer to read through it. It solves real problems in practical ways. You do need to understand how to use the function parse_life(), which has a comment block describing its usage. Simply speaking, it takes a fllename as an argument (such as would be passed to your program as argv[1]) and returns a 24 row by 80 column matrix of char cells that are either LIVE or DEAD, as appropriate.

There is also a function, clearterm(), that clears the terminal screen. You can use this along with your output code and the function usleep() to produce animations for testing. (See Section 4.2 for more information.) This function takes no arguments and returns no value.

Several constants are deflned for you, as well. They are;

 

• GRIDY: The number of rows in your grid of cells

• GRIDX: The number of columns in your grid of cells

• LIVE: The “live” cell character, 'X'

• DEAD: The “dead” cell character, ' '

 

All of the given functions and constants are deflned in the flle src/life.h. This flle is already included in

src/main.c, where you should place your main function and begin your implementation.

You should not need to change any of the given code, although you may do so if you like. I do not recommend this.

You may create as many source flles as you need in the source directory, but you must add their fllenames to the SOURCEFILES variable in the Makeflle or they will not be correctly submitted to Autograder.

 

4 Testing

Due to the nature of this program, debugging and testing can be tricky; in particular, errors from generation to generation can be difficult to isolate without voluminous output. I recommend several techniques for tackling testing and debugging in this assignment:

 

Compute generational changes on paper or in an image editor. It can be difficult to determine whether a particular evolution is correct or not just by looking. In my implementation, I drew and computed a number of Life states by hand and compared them to my program’s output.

In general, if you try to do this project without jotting down indices, calculations, portions of the grid, etc. on paper, you will probably waste a lot of time looking for trivial one-off errors, computations that are accidentally rotated in the matrix, and the like. Don’t be afraid to write things down!

 

Output internal state to files or standard error — or just alongside the normal output. We have not talked much about output to anything but the normal terminal output, but there are two separate output streams to the terminal, standard output and standard error, that enable you to separate normal program output from errors and debugging. You can print to standard error using fprintf(stderr, format, ...), which takes a format string like printf() but outputs it slightly differently. We will cover the details another time, but in particular it will allow you to output debugging information without breaking the checks performed by make test.

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of