/* The Game of Life by dsheffie and qtedq (Summer 2008) When I first learned MIPS assembly, the assignment was to program the Game of Life in MIPS using the SPIM simulator. I thought it would be interesting to see how dcc compares to my hand-coded version. It is also a reasonably useful sanity check as it can execute a reasonably large amount of code without requiring much user intervention My hand-coded version has 542 lines of assembly. Using DCC, the program has 3595 lines of assembly! The game rules....from Brown Univ CS31 Life handout: The game starts of with an arbitrary initial population ( dictated by whether a particular cell contains an organism or not). Occupied cells are referred to as “alive”, whereas unoccupied cells are “dead”. From this initial population the next generation of organisms is obtained by applying the following rules: 1. The neighbors of a cell are the 8 cells that immediately surround it vertically, horizontally and diagonally. 2. If a cell is alive and has 2 or 3 live neighbors, it will remain alive in the next generation. 3. If a cell is alive and has fewer than 2 live neighbors, it will die of loneliness. 4. If a cell is alive and has 4 or more live neighbors, it will die of over- crowding 5. If a cell is dead and has exactly 3 live neighbors, a new organism will be born in that cell. Otherwise, it remains dead in the next generation. 6. All births and deaths take place at exactly the same time, so that all the cells’ neighbors are counted simultaneously (based on the current generation) before the next generation is produced. It is possible for a new cell to be born based on counting a neighbor in the current generation that will be dead in the next generation. */ /* This random module (and comment) is copied * from the Minesweeper program. The rest is mine. */ class rndModule { int seed; void Init(int seedVal) { seed = seedVal; } int Random() { seed = (15625 * (seed % 10000) + 22221) % 65536; return seed; } int RndInt(int max) { return (Random() % max); } } /* An element in the Game of Life * Can either be life or dead. */ class cell { bool state; void Init( bool state) { this.state = state; } bool GetState() { return this.state; } void SetState(bool state) { this.state = state; } } /* Synthesize smart 2d-arrays to * detect OOB moves */ class column { int length; cell [] arr; cell GetY(int y) { return arr[y]; } void SetY(int y, cell c) { arr[y] = c; } /* Allocate memory and initialize * cells to false */ void Init(int length) { int y; arr = NewArray(length, cell); this.length = length; for(y = 0; y < length; y = y + 1) { arr[y] = New(cell); arr[y].Init(false); } } } /* The synthesized matrix class */ class matrix { int x_dim; int y_dim; column [] col; void Init(int x_dim, int y_dim) { int x; int y; this.y_dim = y_dim; this.x_dim = x_dim; col = NewArray(x_dim, column); for(x = 0; x < x_dim; x = x + 1) { col[x] = New(column); col[x].Init(y_dim); } } void Set(int x, int y, bool state) { column mcol; cell mcell; /* Handling out-of-bound accesses * in Get and Set is easier than * dealing with a bunch of conditionals * in a loop */ if(x < 0 ) return; if(x >= this.x_dim) return; if(y < 0 ) return; if(y >= this.y_dim) return; mcol = col[x]; mcell = mcol.GetY(y); mcell.SetState(state); } bool Get(int x, int y) { column mcol; cell mcell; /* Handling out-of-bound accesses * in Get and Set is easier than * dealing with a bunch of conditionals * in a loop */ if(x < 0 ) return false; if(x >= this.x_dim) return false; if(y < 0 ) return false; if(y >= this.y_dim) return false; mcol = col[x]; mcell = mcol.GetY(y); return mcell.GetState(); } } /* The Game of Life */ class life { /* Reference to current matrix holding * the live cells */ matrix current; /* Two matrices used to track the current * life states */ matrix m0; matrix m1; rndModule rnd; /* The board dimensions */ int x_dim; int y_dim; void Init(int x_dim, int y_dim) { int x; int y; x = 0; y = 0; this.x_dim = x_dim; this.y_dim = y_dim; this.m0 = New(matrix); this.m1 = New(matrix); current = m0; m0.Init(x_dim, y_dim); m1.Init(x_dim, y_dim); /* Clear memory */ for(y = 0; y < this.y_dim; y = y + 1) { for(x = 0; x < this.x_dim; x = x + 1) { m0.Set(x,y,false); m1.Set(x,y,false); } } } /* Used to set initial game state */ bool SetInit(int x, int y, bool state) { /* Detect OOB */ if(x < 0) return false; if(y < 0) return false; if(x >= this.x_dim) return false; if(y >= this.y_dim) return false; /* Set cell */ current.Set(x,y,state); return true; } void PrintMatrix() { int x; int y; int s; for(y = 0; y < this.y_dim; y = y + 1) { for(x = 0; x < this.x_dim; x = x + 1) { /* Print 0/1 instead of true and false * because true and false have different * string lengths, and it looks funny */ if(current.Get(x,y)) { s = 1; } else { s = 0; } Print("| ", s , " "); if(x == (this.x_dim - 1)) { Print("|\n"); } } } } /* The actual simulation command */ void DoLife() { int x; int y; int i; int j; matrix n; /* The reference current keeps track * of the matrix holding the current * game state */ if(current == m0) { n = m1; } else { n = m0; } /* Iterate over the entire matrix */ for(y = 0; y < this.y_dim; y = y + 1) { for(x = 0; x < this.x_dim; x = x + 1) { int neigh_count; bool my_state; neigh_count = 0; my_state = current.Get(x,y); /* Loop around cells 8 nearest neighbors */ for(j = (y - 1); j < (y + 2); j = j + 1) { for(i = (x - 1); i < (x + 2); i = i + 1) { /* Can't count ourself */ bool skip; skip = (x == i) && (y == j); /* Increment neighbor count if * the cells are alive */ if((!skip) && current.Get(i,j)) { neigh_count = neigh_count + 1; } } } /* If the current cell is alive in this generation */ if(my_state) { /* Live cells stay alive if they have * two or three neighbors; otherwise, * the die */ if((neigh_count == 2) || (neigh_count == 3)) { n.Set(x,y,true); } else { n.Set(x,y,false); } } /* If the current cell is dead in this generation */ else { /* The cell can only be "born" if * it has three neighbors */ if(neigh_count == 3) { n.Set(x,y,true); } /* Otherwise, it remains dead */ else { n.Set(x,y,false); } } } } /* Update matrix reference to point the newest * matrix state */ current = n; } /* Run the life simulation for * certain number of generations */ void runLife(int gen) { int i; int iter; i = 0; if(gen < 0) { iter = 0; } else { iter = gen; } Print("Initial generation\n"); this.PrintMatrix(); while(i < iter) { this.DoLife(); Print("New generation = ", i, "\n"); this.PrintMatrix(); i = i + 1; } } void playLife() { int x; int y; int gen; int use_rand; x = 0; y = 0; gen = 0; use_rand = 0; Print("The Game of Life using (Brown Univ) CS31 Rules\n"); /* Get X game board dimension */ Print("Enter X dimension for game board\n"); while(x <= 0) { x = ReadInteger(); if(x <= 0) { Print("Invalid x dimension, try again\n"); } } /* Get Y game board dimension */ Print("Enter Y dimension for game board\n"); while(y <= 0) { y = ReadInteger(); if(y <= 0) { Print("Invalid y dimension, try again\n"); } } /* Initialize board */ this.Init(x,y); x = 0; y = 0; Print("Would you like to use a random starting state?\n"); Print("Type 0 for no, anything else for yes\n"); use_rand = ReadInteger(); if(use_rand != 0) { Print("Please enter an random seed\n"); x = ReadInteger(); this.rnd = New(rndModule); this.rnd.Init(x); /* Only generate as many random variables * as can fit on the board */ gen = this.rnd.RndInt(this.x_dim * this.y_dim); while(gen > 0) { x = this.rnd.RndInt(x_dim); y = this.rnd.RndInt(y_dim); this.SetInit(x,y,true); gen = gen - 1; } } else { Print("Input initial live cell\n"); while( (x != -1) && (y != -1)) { Print("Enter x\n"); x = ReadInteger(); Print("Enter y\n"); y = ReadInteger(); if(!((x == -1) && (y == -1))) { if(!this.SetInit(x,y,true)) { Print("x = ",x, " and y = ", y, "are bad coords\n"); Print("Try again\n"); } else { Print("Entering x = ",x, ", y = ", y, "\n"); } } } } Print("How many generations would like you run?\n"); gen = ReadInteger(); this.runLife(gen); } } void main() { life l; l = New(life); l.playLife(); }