Problem with Game of Life program

Code:

#include <iostream> #include <cstdlib> #include <Windows.h> char grid[25][25]; void turnOn(int x, int y); void turnOff(int x, int y); bool lhmt3(int x, int y); bool lh2o3(int x, int y); bool lhlt2(int x, int y); bool dhe3(int x, int y); int gridCheck(int x, int y); void printGrid(); void initGrid(); void Game(); int main(){ initGrid(); turnOn(10,15); turnOn(10,16); turnOn(9,15); turnOn(11,15); turnOn(10,14); printGrid(); Game(); } // Activate cell void turnOn(int x, int y){ grid[x][y] = '0'; } // Kill cell void turnOff(int x, int y){ grid[x][y] = '-'; } // Check whether living cell has more than three neighbours bool lhmt3(int x, int y){ if(gridCheck(x, y) > 3){ return true; } else { return false; } } // Check whether living cell has two or three neighbours bool lh2o3(int x, int y){ if(gridCheck(x, y) == 2 or gridCheck(x, y) == 3){ return true; } else { return false; } } // Check whether living cell has less than two neighbours bool lhlt2(int x, int y){ if(gridCheck(x, y) < 2){ return true; } else { return false; } } // Check whether dead cell has exactly three neighbours bool dhe3(int x, int y){ if(gridCheck(x, y) == 3){ return true; } else { return false; } } // Scan adjacent cells for life int gridCheck(int x, int y){ int count = 0; if(grid[x-1][y]=='0') ++count; if(grid[x-1][y-1]=='0') ++count; if(grid[x][y-1]=='0') ++count; if(grid[x+1][y-1]=='0') ++count; if(grid[x+1][y]=='0') ++count; if(grid[x+1][y+1]=='0') ++count; if(grid[x][y+1]=='0') ++count; if(grid[x-1][y+1]=='0') ++count; return count; } void printGrid(){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ std::cout << grid[x][y] << " "; } std::cout << std::endl; } } void initGrid(){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ grid[x][y] = '-'; } } } void Game(){ while (true){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ if((grid[x][y] == '0') and (lhmt3(x, y) == true)){ std::cout << lhmt3(x,y); turnOff(x, y); } if((grid[x][y] == '0') and (lh2o3(x, y) == true)){ } if((grid[x][y] == '0') and (lhlt2(x, y) == true)){ turnOff(x, y); } if((grid[x][y] == '-') and (dhe3(x, y) == true)){ std::cout << "i am dead"; turnOn(x, y); } } } system("PAUSE"); system("CLS"); printGrid(); } }

This doesn't do what it's supposed to. In a functional Life program what should happen is the middle cell dies and the corner cells are activated. Perhaps there's something wrong with my conditionals but they look pretty good to me and I can't figure out what's wrong. If someone could read through it I'd appreciate it.

P.S. The system("PAUSE") and cout statements in Game() are there only for debugging reasons.

EDIT: Some sample output:

Code:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 - - - - - - - - - - - - - - - - - - - - - - - 0 0 0 - - - - - - - - - - - - - - - - - - - - - - - 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - i am dead11Press any key to continue . . .

The 1s are the result of the lhmt3() function in Game(), and the "i am dead" is the result of the dhe3() function. Obviously these numbers are incorrect. There should only be one "true" and it should output "i am dead" four times.

Code:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 - - - - - - - - - - - - - - - - - - - - - - - - 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Press any key to continue . . .

And it doesn't work.

I do not what game of life is.And i am sorry that i can not understand what you mean the problem is.I mean i can not see what you want to achieve,so you can explain me a little bit(if you wish and if you see that you get no answers,because other members may understand) :)

Sorry. The Game of Life is a non-interactive "game" that is "played" on a grid with any number of cells (in my program it's 25x25). Each cell can either be "dead" or "alive" and the game has four rules to determine what cells live and die. I'm just going to copy paste from Wikipedia because it explains it very well:

Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

So I have specific functions to test these conditions and then I either activate or deactivate the cells depending on the result of the conditionals. Check my comments, they should tell you what I'm trying to do with the functions. My program doesn't work however because I am not getting to expected result, which is a square in the 2nd cycle.

You need to use another grid (2 dimensional array) to calculate the next generation of cells. With only one grid, the next generation is calculated from a mixture of the current generation and the next generation.

I think that the problem is not in your code that in something you got wrong by the rules of the game or by examining the output. :)

Mind that the cell with coordinates 9,14 is going to regenerate(because it has 3 neighbours ).So i would say that the output is correct.The cells that alive after the first round are the 9,14 and the 10,14.That is correct i would say,isn't it? :)

Quote:

Originally Posted by christop

You need to use another grid (2 dimensional array) to calculate the next generation of cells. With only one grid, the next generation is calculated from a mixture of the current generation and the next generation.

The answer i gave ex-Mortis considers that you were aware of what christop said and calculates the output with the mixture he said :)

> if(grid[x-1][y]=='0') ++count;
Beware of array overruns (and underruns).
You start with x and y at 0.

Quote:

Originally Posted by std10093

I think that the problem is not in your code that in something you got wrong by the rules of the game or by examining the output. :)

Mind that the cell with coordinates 9,14 is going to regenerate(because it has 3 neighbours ).So i would say that the output is correct.The cells that alive after the first round are the 9,14 and the 10,14.That is correct i would say,isn't it? :)

Nope. See for yourself.

Quote:

Originally Posted by christop

You need to use another grid (2 dimensional array) to calculate the next generation of cells. With only one grid, the next generation is calculated from a mixture of the current generation and the next generation.

Can you elaborate? I don't really understand.

Quote:

Originally Posted by Salem

> if(grid[x-1][y]=='0') ++count;
Beware of array overruns (and underruns).
You start with x and y at 0.

Hadn't considered it. At the moment I'm only testing the middle of the board so it isn't a problem, but I'll fix it.

What I mean is that as you generate the next generation in each cycle, you're partially overwriting the current generation, which affects the results of the next generation.

For example, if a cell dies, it is no longer counted as a living neighbor for several other cells surrounding it when it should still be counted, and if a new cell is born it is then counted as a living neighbor when it shouldn't be.

By using two arrays, you read cells from the "current" generation array and write cells to the "next" generation array.

Quote:

Originally Posted by ex-mortis

Can you elaborate? I don't really understand.

If you make the changes in the same grid then the changed positions will be used in some of the decisions.
Instead, leave the original grid alone and use another grid to create the new state.
Then either copy it back to the original grid or use a buffer-switching technique.

Quote:

Originally Posted by oogabooga

If you make the changes in the same grid then the changed positions will be used in some of the decisions.
Instead, leave the original grid alone and use another grid to create the new state.
Then either copy it back to the original grid or use a buffer-switching technique.

Quote:

Originally Posted by christop

What I mean is that as you generate the next generation in each cycle, you're partially overwriting the current generation, which affects the results of the next generation.

For example, if a cell dies, it is no longer counted as a living neighbor for several other cells surrounding it when it should still be counted, and if a new cell is born it is then counted as a living neighbor when it shouldn't be.

By using two arrays, you read cells from the "current" generation array and write cells to the "next" generation array.

Makes sense now that I think about it. Thanks for the tips, I'll get to work.

Quote Originally Posted by Salem View Post
> if(grid[x-1][y]=='0') ++count;
> Beware of array overruns (and underruns).
> You start with x and y at 0.
> Hadn't considered it. At the moment I'm only testing the middle of the board so it isn't a problem, but I'll fix it.

> for(int x=0;x<25;++x)
> for(int y=0;y<25;++y)
You might only have something interesting in the middle of the board, but you are still checking ALL of it.

Your program is screwed on the very first iteration of your loop.

Oh, and people who ignore buffer overruns "until later" make me :mad:

Quote:

Originally Posted by Salem

Quote Originally Posted by Salem View Post
> if(grid[x-1][y]=='0') ++count;
> Beware of array overruns (and underruns).
> You start with x and y at 0.
> Hadn't considered it. At the moment I'm only testing the middle of the board so it isn't a problem, but I'll fix it.

> for(int x=0;x<25;++x)
> for(int y=0;y<25;++y)
You might only have something interesting in the middle of the board, but you are still checking ALL of it.

Your program is screwed on the very first iteration of your loop.

Oh, and people who ignore buffer overruns "until later" make me :mad:

Sorry, that's not what I was trying to say. I simply commented erroneously that it wasn't a problem but that I was going to fix it. Is this adequate enough?

Code:

// Scan adjacent cells for life int gridCheck(int x, int y){ int count = 0; //To avoid array underrun if(x>=1){ if(grid[x-1][y]=='0') ++count; } if (x>=1 and y<24) if(grid[x-1][y+1]=='0') ++count; } if (y>=1){ if(grid[x][y-1]=='0') ++count; } if (x<24 and y>=1){ if(grid[x+1][y-1]=='0') ++count; } if (x>=1 and y>=1){ if(grid[x-1][y-1]=='0') ++count; } if (x<24){ if(grid[x+1][y]=='0') ++count; } if (x<24 and y<24){ if(grid[x+1][y+1]=='0') ++count; } if (y<24){ if(grid[x][y+1]=='0') ++count; } return count; }

Here's my updated source code:

Code:

#include <iostream> #include <cstdlib> #include <Windows.h> char grid[25][25]; char nextGrid[25][25]; void turnOn(int x, int y); void turnOff(int x, int y); bool lhmt3(int x, int y); bool lh2o3(int x, int y); bool lhlt2(int x, int y); bool dhe3(int x, int y); int gridCheck(int x, int y); void printGrid(); void initGrid(); void initNextGrid(); void arrayCopy(); void Game(); int main(){ initGrid(); initNextGrid(); turnOn(10,15); turnOn(10,16); turnOn(9,15); turnOn(11,15); turnOn(10,14); Game(); } // Activate cell void turnOn(int x, int y){ grid[x][y] = '0'; } // Activate next gen cell void turnOnNext(int x, int y){ nextGrid[x][y] = '0'; } // Kill cell void turnOff(int x, int y){ grid[x][y] = '-'; } // Kill next gen cell void turnOffNext(int x, int y){ nextGrid[x][y] = '-'; } // Check whether living cell has more than three neighbours bool lhmt3(int x, int y){ if(gridCheck(x, y) > 3){ return true; } else { return false; } } // Check whether living cell has two or three neighbours bool lh2o3(int x, int y){ if(gridCheck(x, y) == 2 or gridCheck(x, y) == 3){ return true; } else { return false; } } // Check whether living cell has less than two neighbours bool lhlt2(int x, int y){ if(gridCheck(x, y) < 2){ return true; } else { return false; } } // Check whether dead cell has exactly three neighbours bool dhe3(int x, int y){ if(gridCheck(x, y) == 3){ return true; } else { return false; } } // Scan adjacent cells for life int gridCheck(int x, int y){ int count = 0; //To avoid array underrun if(x>=1){ if(grid[x-1][y]=='0') ++count; if(grid[x-1][y+1]=='0') ++count; } if (y>=1){ if(grid[x][y-1]=='0') ++count; if(grid[x+1][y-1]=='0') ++count; } if (x>=1 and y>=1){ if(grid[x-1][y-1]=='0') ++count; } if(grid[x+1][y]=='0') ++count; if(grid[x+1][y+1]=='0') ++count; if(grid[x][y+1]=='0') ++count; return count; } void printGrid(){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ std::cout << grid[x][y] << " "; } std::cout << std::endl; } } void initGrid(){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ grid[x][y] = '-'; } } } void initNextGrid(){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ nextGrid[x][y] = '-'; } } } void arrayCopy(){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ grid[x][y] = nextGrid[x][y]; } } } void Game(){ printGrid(); while (true){ for(int x=0;x<25;++x){ for(int y=0;y<25;++y){ if((grid[x][y] == '0') and (lhmt3(x, y) == true)){ std::cout << lhmt3(x,y); turnOffNext(x, y); } if((grid[x][y] == '0') and (lh2o3(x, y) == true)){ } if((grid[x][y] == '0') and (lhlt2(x, y) == true)){ turnOffNext(x, y); } if((grid[x][y] == '-') and (dhe3(x, y) == true)){ std::cout << "i am dead"; turnOnNext(x, y); } } } arrayCopy(); system("PAUSE"); system("CLS"); printGrid(); } }

Right now it "works" in the sense that in the first generation all of the conditionals return the correct values and the 2nd generation of cells is printed correctly. But for some reason the if statements do not run at all (or all return false) and there is no 3rd generation. From what I can tell it should copy the 2nd generation values to the first generation and run another check on all of the cells. I think maybe the sequence is somehow screwed up but I cannot spot the error.

You're still not checking for array overrun.
You should call initNextGrid() after arrayCopy().
Kurt

Quote:

Originally Posted by ZuK

You're still not checking for array overrun.
You should call initNextGrid() after arrayCopy().
Kurt

1. I'm not? What is the proper way to check for an overrun then?

2. I already tried it, it doesn't work. The error is definitely in the conditionals because they return false or don't run at all instead of returning true like they should.

Change all the 25's in your program to SIZE and put this after your includes:
const int SIZE = 25;

Don't make your grids global. Define them in main and pass them to your functions. Then you'll only need one "initGrid" function, for instance.

Code:

#include <cstring> // for memset() and memcpy() const int SIZE = 25; typedef char GRID[SIZE][SIZE]; int main() { Grid grid, nextGrid; initGrid(grid); initGrid(nextGrid); // actually, you shouldn't do this here! (see below) ... void initGrid(Grid g) { memset(g, '-', SIZE * SIZE); } void copyGrid(Grid dest, Grid src) { memcpy(dest, src, SIZE * SIZE); }

You don't need to check if a living cell has less than 2 neighbors or more than 3 neighbors because these checks are simply the opposite of checking if it is 2 or 3, i.e., if a living cell does not have 2 or 3 neighbors it dies.

Actually, you shouldn't have these checks in functions. In particular, it's not very smart to be calling gridCheck multiple times when it could just be called once.

And gridCheck is not properly guarding against array overrun. You have to check for every x or y that you add or subtract 1 to/from.

Code:

if (x > 0 && grid[x-1][y] == '0') ++count; if (x < SIZE-1 && grid[x+1][y] == '0') ++count; if ( y > 0 && grid[x] [y-1] == '0') ++count; if ( y < SIZE-1 && grid[x] [y+1] == '0') ++count; if (x > 0 && y > 0 && grid[x-1][y-1] == '0') ++count; if (x > 0 && y < SIZE-1 && grid[x-1][y+1] == '0') ++count; if (x < SIZE-1 && y > 0 && grid[x+1][y-1] == '0') ++count; if (x < SIZE-1 && y < SIZE-1 && grid[x+1][y+1] == '0') ++count;

In Game you need to clear nextGrid every time (just after while(true) ). That will start it off in the state "all cells dead". So you just need to turn on the live cells. I.e., write to nextGrid all living cells that are still living and all dead cells that have just come to life.

EDIT: To the admins: what's wrong with the code blocks? It seems to be double-blocking the code and it is not (for me at least) properly copy/pastable.

Quote:

Originally Posted by oogabooga

EDIT: To the admins: what's wrong with the code blocks? It seems to be double-blocking the code and it is not (for me at least) properly copy/pastable.

I did have that problem with a recent version of firefox too. Had to restart the browser.
Working with firefox 7 now and don't see that problem any more. ( but it's another OS too )
Kurt

Quote:

Originally Posted by oogabooga

post

Excellent suggestions, my program is considerably more efficient. Although I tried at first to pass in the arrays as function parameters I couldn't get it to work. Never thought of using a typedef.

But now the program doesn't do anything. I for the most part copied your code and shoehorned it into my program so it's my own fault but I had to edit every single function so I don't really understand what's wrong. Here's the edited main.cpp:

Code:

#include <iostream> #include <cstdlib> #include <cstring> #include <Windows.h> const int s = 25; typedef char GRID[s][s]; void turnOn(GRID g, int x, int y); void turnOff(GRID g, int x, int y); bool lh2o3(GRID g, int x, int y); bool dhe3(GRID g, int x, int y); int gridCheck(GRID g, int x, int y); void printGrid(GRID g); void initGrid(GRID g); void copyGrid(GRID dest, GRID src); int main(){ GRID grid, nextGrid; initGrid(grid); turnOn(grid, 10,15); turnOn(grid, 10,16); turnOn(grid, 9,15); turnOn(grid, 11,15); turnOn(grid, 10,14); //Game while (true){ printGrid(grid); initGrid(nextGrid); for(int x=0;x<s;++x){ for(int y=0;y<s;++y){ if((grid[x][y] == '0') and (lh2o3(grid, x, y) == true)){ turnOn(nextGrid, x, y); } else if((grid[x][y] == '-') and (dhe3(grid, x, y) == true)){ turnOn(nextGrid, x, y); } else { turnOff(nextGrid, x, y); } } } copyGrid(nextGrid, grid); system("PAUSE"); system("CLS"); } } // Activate cell void turnOn(GRID g, int x, int y){ g[x][y] = '0'; } // Kill cell void turnOff(GRID g, int x, int y){ g[x][y] = '-'; } // Check whether living cell has two or three neighbours bool lh2o3(GRID g, int x, int y){ if(gridCheck(g, x, y) == 2 or gridCheck(g, x, y) == 3){ return true; } else { return false; } } // Check whether dead cell has exactly three neighbours bool dhe3(GRID g, int x, int y){ if(gridCheck(g, x, y) == 3){ return true; } else { return false; } } // Scan adjacent cells for life int gridCheck(GRID g, int x, int y){ int count = 0; //To avoid array underrun and overrun if (x > 0 && g[x-1][y] == '0') ++count; if (x < s-1 && g[x+1][y] == '0') ++count; if ( y > 0 && g[x] [y-1] == '0') ++count; if ( y < s-1 && g[x] [y+1] == '0') ++count; if (x > 0 && y > 0 && g[x-1][y-1] == '0') ++count; if (x > 0 && y < s-1 && g[x-1][y+1] == '0') ++count; if (x < s-1 && y > 0 && g[x+1][y-1] == '0') ++count; if (x < s-1 && y < s-1 && g[x+1][y+1] == '0') ++count; return count; } void printGrid(GRID g){ for(int x=0;x<s;++x){ for(int y=0;y<s;++y){ std::cout << g[x][y] << " "; } std::cout << std::endl; } } void initGrid(GRID g) { memset(g, '-', s * s); } void copyGrid(GRID dest, GRID src) { memcpy(dest, src, s * s); }

Your copyGrid() call is the wrong way round. You want to copy nextGrid into grid.
Kurt

You could simplify all the checking by doing
for ( i = 1 ; i < s-1 ; i++ )

Make your outer for loops miss the first and last rows, and first and last columns.

Or do the tests just once inside the function
if ( x < 1 || x > s-1 || y < 1 || y > s-1 ) return 0;

Alternatively you could put a border around the grid, making it (SIZE+2)*(SIZE+2) elements in size. The edges would be initialized with an otherwise-unused value (e.g., ascii-nul). Then your loops would be like for (x = 1; x <= SIZE x++) and you wouldn't need any tests at all.

Quote:

Originally Posted by ZuK

Your copyGrid() call is the wrong way round. You want to copy nextGrid into grid.
Kurt

Well that's embarrassing. My original copy function was "copy this to this" whereas this one is "copy to this from this". It works perfectly now, though I have a lot more work to do (UI-wise). Thanks so much for all the help everyone.

EDIT:
@Salem and oogabooga: Good ideas, I'll implement them.

Quote:

But now the program doesn't do anything.

I have not looked at your code but be aware that simple implementations of game of life ie with random seed cells may well lead to 'nothing' happening - you might see your starting config, and then a blank screen.. = extinction. when you start to see familiar oscilators and static cell arrangements from your seed cells you know you have nailed it

While you are at it, use std::array instead of C arrays.

Quote:

Originally Posted by rogster001

I have not looked at your code but be aware that simple implementations of game of life ie with random seed cells may well lead to 'nothing' happening - you might see your starting config, and then a blank screen.. = extinction. when you start to see familiar oscilators and static cell arrangements from your seed cells you know you have nailed it

Yeah, I know. I was only testing initial configurations for sequences I am familiar with. I have the simplelife iPhone app and I also checked a web-based Game of Life and when I said nothing was happening I meant there was no evolution when there should have been.

Quote:

Originally Posted by Elysia

While you are at it, use std::array instead of C arrays.

Never heard of it, but I'll check it out. I presume std::arrays are safer to use than C-style arrays.