**Project 1: grid** The Game of Life and Image Processing **Reed CSCI 121 Fall 2022**   *3 rule checkpoint due 11:59pm on 9/29* *all 8 rules due 9am on 10/6* This first project has you inventing a family of different *cellular automata*. A cellular automata simulation is one that is applied to a two-dimensional grid of *cells*, where each cell stores an integer value, the cell's *state*. With each tick of the simulation's clock, the grid of cells update their state value by applying a simple rule. The rule specifies how it should calculate its next state from its previous state. This calculation is a *local* one. A cell changes according to its own state and the state of its immediate neighbor cells in the grid. Despite this simplicity, the grid's entire state can evolve in very interesting ways over time. You can, for example, devise calculation rules that perform image and shape analysis of the grid's initial state pattern. (##) Set Up Download the project's source code as a ZIP package using the link below: • [**Project 1** package](project1.zip) Have it unpack as a folder named `project1`, say, within your `Desktop` folder. In that project folder, you will see a number of `.py` source files for the Python program that you will be working with. To run the program, bring up terminal console and type the commands ~~~ none cd Desktop/project1 python3 life.py ~~~ If everything is set-up correctly with Python, the program will bring up a window that shows a grid of cells. On some installations or on some systems, you will get an error, something like the following  In these situations, Python is complaining that you are missing a needed Python module called `tkinter`. This module helps us create a window, draw shapes in that window, and allow the user to click on that window. To fix this situation for your Python set-up, you can enter the console command: ~~~ none pip3 install tkinter ~~~ Having done this, the command `python3 life.py` should be able to open a window and show the program's grid of cells. In addition to the displayed grid of cells, there is a color bar shown at the top. The program is prepared to execute the rules of the mathematician John Conway's cellular automata, one he called "The Game of Life". If you select one of the colors in the color bar, you can then paint that color onto the cells of the grid. Having done that painting, you can run the Game of life simulation by hitting `[SPACE]` a few times. This will change the pattern of colored cells, and how that grid changes is described just below. In any case, congratuations! You have created life. Read on. (#) Conway's Game of Life  The Game of Life is not actually a game at all, not in the usual sense. It is at most a game played by one person, there's no strategy, and the rules don't offer a player any choices like a normal game would. Rather, the Game of Life is a simulation of an artificial world, the world of the grid, governed by a very simple mathematical rule. An execution of the Game of Life consists of setting up the initial state of the world and then applying the rule to determine the next state of the world (the next "generation"). By successively applying this rule to the world, computing its state from one generation to the next, some interesting behavior arises. In the Game of Life, the world is a grid of cells like you see in the Python program's display. Each cell has a state associated with it. In the original Game of Life, the state of a cell could either be "living" or "dead". In this version, the state of a cell is an integer ranging from 0 to 100. Feel free to paint on the grid with the mouse using the currently selected color. White is 100. Violet through red is 99 through 1. We say that any such cell, one with a state value from 1 to 100, is "living". Cells that are black have the state value of 0. We say that these cells are "dead". Once you've set up the initial state of the world, painting cells as living, you can then run a step of Conway's game, changing the grid's cells' state. Hit the *[SPACE]* bar on the keyboard once. Some live cells stay alive and others die. Some dead cells come alive. Hit the space bar again to see the next generation of cells. And again. The rule for how the grid changes is deterministic. The next generation's pattern of living and dead cells is entirely determined by the prior generation's pattern, The calculation for determining which cells live, and which cells die, is simple. With each step a cell counts the number of living cells in the eight cells immediately surrounding it. In the case where a cell is alive, it remains alive in the next generation if it has two or three living neighbors. Otherwise it dies. If instead a cell is dead, it will be come alive with a step if it has 3 living neighbors. Otherwise it remains dead. Try some simple patterns out to test these rules. A good one to try is a row of three live cells surrounded by dead cells. This is a "blinker." It cycles between two states---a horizontal strip of three, and a vertical strip of three. Another simple one is a 2x2 square called a pod. There are also gliders, spinners, clocks, loaves, hives, spaceships, ... There has been tremendous effort in studying Conway's Game of Life, and a number of rich discoveries have been made. The [Wikipedia article](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) for it serves as a decent starting point, should you want to learn more about it, and it is a good introduction to cellular automata in general. (#) The Python Code The code for the program is made up of three parts. There is `life.py`, which runs the main program, but it is pretty minimal. It relies almost entirely on `Grid.py`, which describes the program's display of, and the user's possible interaction with, the grid of cells. This is a fairly large Python file that you won't need to understand to complete this assignment (though do feel free to look at it). Instead, you will be extending the code in the file `rules.py`. This contains a description of grid rules that can be used to run the program. For example, it contains the definition of a function `conway` that exactly describes Conway's cell rule. Take a moment to look at this file, find the `conway` function, and then see how it implements the cellular behavior. Each time that you press the space bar, this function gets executed once for each cell in the world. Hopefully, you've noticed a few things when inspecting this code. First off, `conway` is a function whose sole responsibility is to return an integer value that represents the next state of the cell it's working with at that moment. In order to compute the cell's next state, it has access to the current state of the cell (the parameter `cntr`) and the current state of that cell's eight immediate neighbors (the parameter `nbrs`). That second parameter is an object that consists of those eight state values. They are accessible with `nbrs.N`, `nbrs.NE`, `nbrs.E`, and so on. With these values and some additional calculations and logic, the value of the next state of a cell is computed and returned. (#) Image Processing  Instead of simulating life, it's possible to come up with all sorts of rules for computing the states of cells based on their previous states. One of the more useful application areas is image processing. In image processing, you take the digital version of a photo and manipulate it, either to enhance it's quality, mess with it, analyze it, etc. Many of the techniques for modifying an image can be performed by local pixel rules, where you compute the tone of a pixel based on the tone values of it and its neighboring pixels). Blurring and sharpening an image are two classic examples of this. To play with this feature in the program, quit the simulation demo by pressing the `q` key. We can instead run a grid simulation within the python interpreter. To do so, type the following: ~~~ none >>> from Grid import Grid >>> from rules import * >>> Grid(negative,pattern='images/reed-square.pgm') ~~~ The program runs with a finer grid whose cells are loaded with the pixels of a greyscale image of Eliot Hall. In this mode, black has the value 0, white has the value 255, and greys have in-between values. This also sets up the `negative` rule for the grid's cells, rather than the `conway` rule. This rule makes the picture appear as its negative's image. It is a very simple rule. With one tap of the space bar, the new value of a pixel 255 minus its prior value. You can find this rule as the function `negative` in `rules.py`. Another good rule to try is `blur`. This computes a weighted average of each cell's four compass-point neighbors `nbrs.N`, `nbrs.E`, `nbrs.S`, and `nbrs.W`. Hit 'q' to end the `negative` simulation and then, still within Python, type ~~~ none >>> Grid(blur,pattern='images/reed.pgm') ~~~ This loads a larger, rectangular image of Eliot Hall. With the `blur` rule each cell computes a weighted average of its four compass-point neighbors. The next state of the cell is just the average of itself and the average of its four neighbors. The effect is a smoothing of the details of the image, giving them softer transitions from light to dark. After a few steps, we get a blurred image, as if the camera used was not in focus. (#) Making New Rules You can add your own cell rules to the program. Just create a new function definition to `rules.py`, mimicking my examples. A rule is a function that takes the center cell value `cntr` and the 8 neighboring cell values as an object `nbrs`. Using these parameters on the color grid it returns an integer from 0 to 100. The `Grid` and other support programs can call this function to compute that rule's behavior on the grid. If it is instead acting on the greys of the sample images, then it should return an integer from 0 to 255. You can run the grid program on the image, specify your new image rule, and then apply its effect. The goal of this assignment is for you to write the code for **eight** functions like `conway` and `blur` There is a menu of suggestions at the end of this assignment description that specify what those rules should be. The menu of possible rules you can construct is fairly rich. It is surprising what can be done with just a little bit of clever coding. (#) The Assignment In the file `rules.py`, devise a series of cellular automata and image processing rules. You are to write eight rules, six from the required list below, and the remaining two of your choosing. You should do the required six first, and quickly, so that you gain experience with how the cellular automata rules work. Then make your two "programmer's choice" behaviors directed and interesting. I'll give you some suggestions in lecture and in lab for what other rules are possible. In a new file named `demo.py` devise a demonstration of your eight rules similar to my demonstration code in `life.py`. Your description should give us a brief sense of what rule we are seeing, and how to set up and run your demonstration, if need be. We describe making demos further below. Beyond the coding above, you should have ample and useful comments in your `rules.py` file that describe each function definition at an appropriate level of detail. Same goes for each of the `Grid` calls in `demo.py`. You will be graded on the quality and correctness of your code, the intricacy of your rules, and on the clarity of your descriptions and comments. (#) Menu of Required Rules Below we give three categories of prescribed rules. You are to implement two rules from each category. And then there is a fourth "Programmer's Choice" category where you have the option of inventing your own rules to make into Python code that runs on the grid. You are to implement two of these in addition to the six prescribed ones. This should lead you to writing eight different rules. (##) **Life Rules.** *Pick two grid simulation rules and implement them.* Implement two of the life-like behaviors below. In some cases, it's more natural to consider a cell as having only four neighbors, to the `N`, `E`, `S`, and `W`, rather than the full eight. 1. Have the color of the cell represent its age. Perhaps have it die at 100. 2. Have live cells be white, and have dead cells leave a color trace that "decays" from violet to red, then finally to black. The decay happens with each successive step of the simulation. The trace should not affect the white cells' life simulation. 3. Have the grid instead simulate a *sandpile automata*. In a sandpile, the state of a cell gives the height of a "pile of sand grains" sitting on that cell. With each step, a cell "fires" if it has four or more grains of sand on it. When it fires, it gives one grain of sand to each of its four compass point neighbors---one to the north, one to the east, one to the south, and one to the west. Its own pile drops by four grains as a result. For option #3 just above, [Dave Perkinson's](https://people.reed.edu/~davidp/) sandpile pages cover a number of aspects of this kind of system, and the [mathematics](https://people.reed.edu/~davidp/divisors_and_sandpiles/) that relates to its study. He has a [web simulation](https://people.reed.edu/~davidp/grant/) that you can run. When it loads click on the *Go* button just right of the `n Grains Each Cell` line and you'll see the simulation's behavior. A good demo of this involves placing a ton of grains of sands in the center cell and watching that tall pile topple and spread to the other cells. Note that our above description of sandpile behavior does not quite line up with how the grid rules are devised. In the description a cell fires by adding grains to its neighbors. In our rule system, however, a cell's rule only has control over its own cell, and not over the neighboring cells that it reasons about. This means that the sandpile rule function, in our simulation, will have to look at its four neighbors to see whether their grain heights will lead them to fire. It then determines its own height based on their firing. (##) **Imaging.** *Pick two image processing rules and implement them.* 1. Increase or decrease the contrast of an image. Like the negative rule, this does not examine the neighboring pixels. Instead, a cell goes darker in a step when its brightness is below middle grey. It goes lighter in a step when its brightness is above middle grey. 2. Sharpen the image with each step. This is similar to blur, surprisingly. In a blur, a cell takes on a value closer to the average of its neighbors. In a sharpening, a cell takes on a value that differentiates it from the average of its neighbors. This has the global effect of bringing out details, since differences between neighboring pixels get amplified. 3. Find edges in an image (places where there is a transition from dark to light). Here, in one step, cells should, say, turn white if they are at such a transition. They should turn black if not. Alternatively, they could be bright grey if they are at a major transition, and draker grey if they are at a minor transition. (##) **Shapes.** *Pick two shape processing rules and implement them.* 1. With the grid in color mode, starting with a pattern where the cells are mostly black, but with white cells forming a boundary of a region and a single cell of a color somewhere in the middle of that region. With simulation steps, have a rule that leads the color to fill the whole interior of that region, but not leak out. 2. In a grid where the cells are mostly black, but with some forming a pattern (or shape) in white. In one step, this rule should make a shadow of the image of white pixels, "underneath" them, in another color, to their SE. 3. In a grid that is mostly black, except with a blob of pixels that are white somewhere in the middle, have a rule that, after a few steps, ends up drawing a colored rectangle whose width and height is that of the white blob, with that white blob sitting inside. (##) **Programmer's choice.** *Devise two more rules.* These can be of your own choosing. Ideally, these should be nontrivial and interesting. They could come from the lists above, or be of some other design. Include a clear description of what each does, or at least what you intended each to do. (#) Making a Demo Having written the eight rules, you must also construct a demonstration of them inside a file named `demo.py`. To see what this demo code should look like, please examine the provided `life.py`. Your demo file should be a script that runs each of the eight rules, one by one, to demonstrate each. This coding is similar to the interactions above. After the `import` section of the code, you'll make eight different calls to `Grid`. This will be something like: ~~~ python Grid(sandpile,'1. This runs a sanpile simulation.', pattern='patterns/sandpile10x10.pat') Grid(aging,'2. This runs an "aging" version of Conway.', pattern='patterns/glider.pat', generations=64) Grid(blur,'3. This blurs an image.', pattern='images/reed.pgm') ... Grid(maze,'8. This generates a maze from the white dot.', pattern='dot.pat') ~~~ These lines each specify their rule of their demo, give a description, and give a starting pattern. On our end, we'll run your demo to see your work and we'll use your description to understand what we're seeing. Your descriptions can give us instructions for how to set things up and details of what we are about to see. We'll be running this demo while inspecting your rules' code. You can create your own pattern files, similar to our `patterns/rpenatmino.pat` and other files. If you look at those samples in the `patterns` folder, you'll find that they are just text files that can be edited by the same editor you use to edit Python programs. They each start with similar top lines: ~~~ none 16 16 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ~~~ The first line gives the number of columns (the width of the pattern) and the number of rows (the height of the pattern). The second line gives the range of color values which, in the case of this example, is 0 to 100. The remaining lines give the contents of each row of the pattern. In this case there are 15 rows each with 16 values from 0 to 100. To help you use richer patterns for your demos, we've included a **"Save pattern..."** feature in the simulation. If you hit the `s` key, click on the console window, and then enter a pattern file name within the console, the simulation will save the currently displayed cell pattern as a text file that can then by loaded by a demo. The simulation user can also paint cells while `Grid` runs in demo mode. This allows your demo to instruct the user how to set up the demo by painting. Since the demo doesn't display the color selection palette, a user can instead type the digits of a cell value, followed by `"="`, to choose a particular value for painting. You can use earlier demo rules to set up a pattern that later rule demos can load. If you include a `save_as` parameter in an earlier call to `Grid`, then the cell pattern of the grid will be saved to that file's name when the user hits `"q"`. For example, here is a demo that uses a `maze` rule to set up a maze pattern that can be used as the initial conditions for a subsequent demo of `robot`. ~~~ python Grid(maze, 'This builds a maze from a single white square.', pattern='patterns/dot.pat', save_as='patterns/maze.pat') Grid(robot, 'Place a robot cell of 40 in the maze. It runs around.', pattern='patterns/maze.pat') ~~~ For image demonstrations, it is okay to just use the two image files provided, for example, `images/reed-square.pgm`. It is also possible to invent your own images. Ther are in *portable grey map* or *PGM* format. This isn't a very used format--- web images are usually *JPG* or *GIF* format--- but it is an easy format to work with when writing programs. Below gives the start of the square image of Eliot Hall: ~~~ P2 #. 128 128 255 17 18 19 20 18 ... ~~~ The first two lines should always be there. The next line gives the dimensions the same as we you need for `.pat` files. The next line gives the value of pure white. And then the subsequent lines give the value of each pixel. If you like, you can convert your own images to PGM format. A program that can do this for you is called [GIMP](https://www.gimp.org/) produced by the **Gnu** free software foundation group. (#) What to Hand In The two files that you will be editing for this project are `rules.py` and `demo.py`. Some of you might also have created pattern and image files in the folders `patterns` and `images` folders to support your demo. I'd like you to **submit the entire project folder** as a *compressed ZIP file* onto Gradescope. To do this, you need to right click on your `project1` folder. On Windows, you can also click and hold; on the Mac you can hit the `[control]` key while clicking. In both systems, this clicking should bring up a menu item that allows you to "compress" your project folder. * [Instructions for compressing on Windows](https://support.microsoft.com/en-us/windows/zip-and-unzip-files-8d28fa72-f2f9-712f-67df-f80cf89fd4e5) * [Instructions for compressing on a Mac](https://support.apple.com/guide/mac-help/zip-and-unzip-files-and-folders-on-mac-mchlp2528/mac) Having done this, a compressed `project1.ZIP` file or `project1.zip` file will get created in the same folder that contains `project1`. Upload this ZIP file onto Gradescope. It will unpack into all the files for us to inspect. This will also allow us to download and run your demo. Each rule's function definition in `rules.py` should have a tasteful amount of comments explaining the code that makes up the rule. You will be graded on these (brief) explanations of your rule's code and logic. You will be graded on your description of your two programmer's choice rules. You will also be graded on the quality (the "style") of your code. The clearer the code, the better. Your `demo.py` should contain a runnable demo, with at least one demo (a call of `Grid`) for each of your eight rules. Each demo should have a short, readable description displayed during the demo. You should include extra information about what's being demonstrated within a code comment near the `Grid` call in `demo.py`.