• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • Devaka Cooray
Saloon Keepers:
  • Ganesh Patekar
  • Tim Moores
  • Carey Brown
  • Stephan van Hulst
  • salvin francis
Bartenders:
  • Ron McLeod
  • Frits Walraven
  • Pete Letkeman

Conway's Game of Life in Java  RSS feed

 
Greenhorn
Posts: 22
1
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The Game of Life is played on an infinite two-dimensional grid of square cells. Since it’s hard to have infinite objects living in a computer, we’ll settle for an 200 (wide) x 60 (high) grid. It is not really a game, but rather a simulation that progresses with time which is considered to be discrete. At time = 0, the user inputs an initial configuration of empty and “live” cells. This configuration should be placed in the middle of the grid to minimize the kinds of incorrect behaviors you might find at the edge of the grid.. At each successive generation t = 1, t = 2, t = 3, etc. the configuration changes, some live cells dying, and some empty cells coming to life, the changes governed by how many occupied neighbors a given cell has. Each cell has eight neighbors, namely the cells NW, N, NE, E, SE, S, SW and W of the given cell. The state of each cell is noted and the number of neighbors is calculated at a given time t, and then the cell’s state at time t + 1 is computed according to the following rules:

(a) If the cell is unoccupied and has exactly 3 occupied neighboring cells, the state changes to occupied, otherwise it remains unoccupied
(b) If the cell is occupied and has fewer than 2 or more than 3 occupied neighbors, the state changes to empty, otherwise it remains occupied.

It is important to note that all changes from time = t to time = t + 1 are considered to occur simultaneously, so that, for instance, if a cell is going to die at the next time step, it still counts as an occupied cell when computing any of its neighbors’ state changes.

Write a program to run the simulation of the Game of Life! Specifically, prompt the user to enter a “lifeform” as well as an option to run the simulation

a) Forever (Use ‘f’)
b) For some number of generations that the user specifies (e.g., 100) (use ‘n 100’)
c) Stopping after each generation and waiting for the user to press Enter (use ‘n’)

The program should print out each generation in the smallest bounding box possible (because 200 x 60 is rather hard to follow). To avoid “falling off the edge” the boundary of the box should be clamped to empty cells.
Input will be performed by keyboard. Notice that in order to center the initial configuration, you will need to determine the number of lines entered and the maximum width of a given line

How would I accomplish this?
 
Victoria Li
Greenhorn
Posts: 22
1
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, a two-dimensional array must be used.
 
author & internet detective
Marshal
Posts: 38687
677
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Victoria,
CodeRanch is Not a Code Mill While we are happy to answer specific questions, nobody is going to write your project for you. So what more specific question do you have?
 
Victoria Li
Greenhorn
Posts: 22
1
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Jeanne Boyarsky wrote:So what more specific question do you have?



I don't know exactly how to begin. How would I be able to get a user input for the empty and filled spaces in a 200x60 two-dimensional array?
 
Saloon Keeper
Posts: 5027
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Victoria Li wrote:I don't know exactly how to begin. How would I be able to get a user input for the empty and filled spaces in a 200x60 two-dimensional array?


Seems like entering (up to) 200x60 cells would be extremely tedious and error prone. You could instead read a file with the cell configuration. Perhaps something like:
You could have an option to fill in the cells with random booleans. The specs seem to leave it up to you.
 
Victoria Li
Greenhorn
Posts: 22
1
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:

Victoria Li wrote:I don't know exactly how to begin. How would I be able to get a user input for the empty and filled spaces in a 200x60 two-dimensional array?


Seems like entering (up to) 200x60 cells would be extremely tedious and error prone. You could instead read a file with the cell configuration. Perhaps something like:
You could have an option to fill in the cells with random booleans. The specs seem to leave it up to you.



That would be a better idea, but I'm required to begin with a 200x60 and have a user input the empty/filled spots.
 
Rancher
Posts: 3276
33
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

I'm required to begin with a 200x60


That's rather large.  I'd suggest you start with a much smaller grid while working out the logic, say 30X20.  A smaller grid will be easier for testing.
When the code is working for the smaller grid, increase its size for further testing.
 
Marshal
Posts: 6150
418
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I find you instructions to be written in much more complicated way than they actually are. For some reason they talk about two different ideas. Live/Dead, then all of a sudden about occupied, unoccupied and then at some point about empty. Not sure if that's even correct. At least confusing. Also (b) part consists of 3 rules but they decided to merge them into one.

I suggest to read in Wikipedia about the Conway's Game of Life. There are really 4 rules explained in 4 clear sentences.
 
Carey Brown
Saloon Keeper
Posts: 5027
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Victoria Li wrote:

Carey Brown wrote:

Victoria Li wrote:I don't know exactly how to begin. How would I be able to get a user input for the empty and filled spaces in a 200x60 two-dimensional array?


Seems like entering (up to) 200x60 cells would be extremely tedious and error prone. You could instead read a file with the cell configuration. Perhaps something like:
You could have an option to fill in the cells with random booleans. The specs seem to leave it up to you.



That would be a better idea, but I'm required to begin with a 200x60 and have a user input the empty/filled spots.


The way I read your instructions is that your array should be 200x60 and that if the user enters a smaller grid that the user's grid should be centered in the 200x60 grid.
 
Master Rancher
Posts: 3679
40
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
^This.
With the text-based Game Of Life the idea was to enter a "creature", represented much as in your earlier post above.
So you would enter a multiline set of spaces and x's (or dots and x's as above).
That gets put in the middle of the board and the game then runs.

But, to be honest, I'd leave the user input to last, and start with a hard code creature.

ETA: Actually "creature" is incorrect, as it's really an arrangement of single celled things...sort of.
 
Carey Brown
Saloon Keeper
Posts: 5027
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
^This

I agree. Leave the user input for last.

When I created Life years ago I found that if you randomly populate the grid that once the game is set in motion it will start to reduce the live cells until it reaches a sustainable number of live cells. From there you often get "emitters" and "flyers" mixed in among the live cells. So, I'd vote for filling in with random cells to start with. Also, reduce the grid down to a manageable 40x40 grid to start with.
 
lowercase baba
Bartender
Posts: 12628
50
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"leave the input for last" actually has a lot of sub-text as well.  That means that what you write now, with the hard-coded starting position, should be written in such a way that it doesn't matter how you get the inputYou should basically write your classes/methods so that they take some kind of starting position argument. 

That way, you can write the "get the input" to be a gui, to read a flat-file, to pull from a database, to listen on a socket...whatever.  Those would then all build the starting position parameter to look the same, so you could use any to get the input...

In other words, try and separate what can be separate.
 
Saloon Keeper
Posts: 1921
55
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
While an initial idea comes to mind of creating a multidimensional array.
I have a vague idea about having a map of 'live' Cells. Each Cell can have a simple Row,Column coordinates. Your game engine has to ensure that no 2 cells 'occupy' the same block (i.e. have the same cell coordinates) by setting the key of the Map to a unique value (maybe a string of row:col). A cell that dies should be removed from your Map and a cell thats born should be added to your Map.
You can easily 'query' the cell above/below/left/right/diagonal, etc.. from this Map.
 
Carey Brown
Saloon Keeper
Posts: 5027
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Salvin, your idea is interesting and would be an efficient way to represent a sparse matrix and killing off live cells would be fairly easy. Where I think your approach runs into difficulty is in generating new life where you must visit each cell to determine if it should be changed to a live cell. This would be trivial in a 2D array (array-of-arrays) but be much more difficult with your approach.
 
salvin francis
Saloon Keeper
Posts: 1921
55
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Each game has it's own challenges.

Here's my abstract thinking so far:

 
salvin francis
Saloon Keeper
Posts: 1921
55
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just realized that "Generation" is a bad name since it may mean the verb "to generate" or the noun "Generation". Maybe I could think of some better name
 
Norm Radder
Rancher
Posts: 3276
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Looks like everyone has written some version(s) of this program.  I used it as a means to learn a new language on a minicomputer back in the mid-70s. 

I wonder if the OP will ever get a chance to post with all the traffic this thread is getting.
 
salvin francis
Saloon Keeper
Posts: 1921
55
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:...Where I think your approach runs into difficulty is in generating new life where you must visit each cell to determine if it should be changed to a live cell. This would be trivial in a 2D array (array-of-arrays) but be much more difficult with your approach.


I see what you mean. But here too I have a different approach in mind. I think that instead of checking all cells on the 'board' to see they are surrounded by 3 live neighbors one can do the following:
  • Get a list of all live cells
  • Loop and populate a list of adjacent 'dead' cells to the live ones (maybe a new method is needed in my interface "getAdjacentDeadCellsFor")
  • Loop through this deal cells list and check if any of them need to be born and add them



  •  
    salvin francis
    Saloon Keeper
    Posts: 1921
    55
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It uses the logic that a cell can be born only in the vicinity of live cells and not any other location on the board.
     
    salvin francis
    Saloon Keeper
    Posts: 1921
    55
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    One thing that I am unable to understand about this game is that is there a sequence to the Rules application ?
    Specifically, I am looking at the Blinker (period 2) period oscillator in wiki.

    If this was the original state :

    Rule#1 says to kill (Any live cell with fewer than two live neighbors dies as if caused by underpopulation.)
    It should turn to:

    but wiki follows the Rule#4 first and then Rule#1 making it :

     
    salvin francis
    Saloon Keeper
    Posts: 1921
    55
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Or is it based on scanning the whole board and noting down items to be created, destroyed and then doing it 'all at once' ?
     
    Liutauras Vilda
    Marshal
    Posts: 6150
    418
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    It doesnt do one by one. It defines first what states going to be in the next generation for each cell with a given current setup and all get updated at once. Some cells become live, some die.
     
    Liutauras Vilda
    Marshal
    Posts: 6150
    418
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    salvin francis wrote:
    If this was the original state :

    Rule#1 says to kill (Any live cell with fewer than two live neighbors dies as if caused by underpopulation.)
    It should turn to:

    but wiki follows the Rule#4 first and then Rule#1 making it :


    That’s correct, read the rules I linked in wikipedia, it says that cell which has some number of live neighbours, itself becomes live in the next generation.

    OP’s requirements are somewhat miswritten either by OP or by teacher. Original description is most comprehensive desription.
     
    Liutauras Vilda
    Marshal
    Posts: 6150
    418
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    salvin francis wrote:Or is it based on scanning the whole board and noting down items to be created, destroyed and then doing it 'all at once' ?


    Nothing gets destroyed, nor created - these are somewhat part of implementation thinking approach.

    Cells either become live, or remain live, or die - that is it. New terminology which fluctuates from original just makes all confusing.
     
    Liutauras Vilda
    Marshal
    Posts: 6150
    418
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    salvin francis wrote:Just realized that "Generation" is a bad name


    Since it is a talk about the cells, “generation” comes from the biology context, to me it makes perfect sense. But once again, I think you got mislead by the poor OP’s posted description.
     
    Master Rancher
    Posts: 2930
    102
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Liutauras Vilda wrote:(...)
    That’s correct


    No it is not. The vertical bar goes directly into the horizontal bar, and vice versa. For each cell find out the rule to apply.

    But read Norms last line: let's give OP a chance to tell if we helped her so far.
     
    Liutauras Vilda
    Marshal
    Posts: 6150
    418
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:

    Liutauras Vilda wrote:(...)
    That’s correct


    No it is not. The vertical bar goes directly into the horizontal bar, and vice versa. For each cell find out the rule to apply.


    This is exactly what I am saying.

    Middle remain live because always have 2 live neighbours, in vertical and horizontal bars.

    In vertical case one on the left and one on the right have by 3 live neighbours, so become live, while top and bottom bar cells die, which makes horizontal bar. Then again middle has two live, so remain as live, while top and bottom cells have by three live neighbour cells, so become live, while side cells die, so again becomes vertical.

     
    Ranch Hand
    Posts: 439
    Chrome Linux VI Editor
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    First thing you need to decide is how to handle borders.  Will the top/bottom and left/right wrap, or are the borders considered dead cells?

    User input.  You can implement a simple Run Length Encoding (RLE) parser, see http://www.conwaylife.com/wiki/Run_Length_Encoded ; This lets you have a few simple patterns in files and you can choose the pattern from the command line.  Your file ends up something like:


    You'll want 2 arrays.    One is the current generation, the other the next generation.  The code is something like:
    [code]
        Set every cell of next generation to dead
        For every cell of current generation decide if it should live or spawn a live cell.  If yes set that cell in next generation to live
        Display the next generation
        Swap arrays, so current generation is now next generation and next generation is now current.
        Repeat.
    [code]
     
    Liutauras Vilda
    Marshal
    Posts: 6150
    418
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Jim Venolia wrote:You'll want 2 arrays.    One is the current generation, the other the next generation.


    Probably that could be a way to do this, but I wouldn't be fascinated about it.

    Couldn't you calculate cells provisional state for the next generation without fiddling with 2 arrays? And when the time comes just build cells of such states?

    Not saying that would be more correct, just trying to bring some thought process presumably to come up  with a better way of doing. 
     
    Jim Venolia
    Ranch Hand
    Posts: 439
    Chrome Linux VI Editor
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Liutauras Vilda wrote:Couldn't you calculate cells provisional state for the next generation without fiddling with 2 arrays? And when the time comes just build cells of such states?



    Not sure I follow.  Are you suggesting that a cell's state could be DEAD, ALIVE, FUTURE_DEAD, FUTURE_ALIVE?  Seems like more work.  Or are you suggesting making a list as cells change, when done processing the board go through the list and update the board?  That would work, and may even be faster.

    Last time I implemented Life I kept a list of cells that might change next generation, then in the next generation perused that list instead of visiting every cell.  Works because 90-99% of your board isn't going to change generation to generation.
     
    salvin francis
    Saloon Keeper
    Posts: 1921
    55
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Jim Venolia wrote:...Works because 90-99% of your board isn't going to change generation to generation.



    Well, its not always about making it work. While your approach is correct, Liutauras rightly pointed out that you don't need 2 arrays to represent your data. Your data can be a single array.
    All you need to do is to figure out the elements to delete or elements to add and update your data structure.

    I don't know why you would create a new data structure to just update your current one.
     
    Creator of Enthuware JWS+ V6
    Bartender
    Posts: 3148
    276
    Android Chrome Eclipse IDE
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Congratulations Victoria Li,

    Your question has made it to our Journal.

    Have a Cow!
     
    Saloon Keeper
    Posts: 9413
    181
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    So, I got sucked into this as well.

    I wrote a bunch of abstract classes that people can use to implement the Game of Life with.

    Sources

    Documentation

    You can implement your own version like this:
     
    Piet Souris
    Master Rancher
    Posts: 2930
    102
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    A simple classification is to write, for instance, Life 23-3, where the first two digits describe how many living neighbors a living cell must have in order to survive, and the digits after the dash how many living neighbors a dead cell must have to come to live. Now, there is nothing against expanding this to the 3d case, with a limited classification. What classification number represents the universe?   
     
    salvin francis
    Saloon Keeper
    Posts: 1921
    55
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Just wanted to share : http://www.salvin.in/GameOfLife/
    Basic, rudimentary implementation, the algorithm is same as the what I mentioned in previous posts using a single Hashmap.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 9413
    181
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I really enjoy how it looks Salvin. I especially like that the grid wraps around. I hadn't considered that in my design.
     
    Liutauras Vilda
    Marshal
    Posts: 6150
    418
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Both of you very well done. I'll sneak around to learn from your codes if you don't mind
     
    salvin francis
    Saloon Keeper
    Posts: 1921
    55
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you very much for the pie Tim Cooke. Thank you to all for the cows !
     
    salvin francis
    Saloon Keeper
    Posts: 1921
    55
    Eclipse IDE Google Web Toolkit Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:.... I especially like that the grid wraps around. I hadn't considered that in my design.


    OP gave me that idea actually. I got this idea from here:

    Victoria Li wrote: "The Game of Life is played on an infinite two-dimensional grid of square cells"


    This inspired me to wrap-around. Honestly, I have not yet completed the UI design changes, the alignment looks bad for now. I will add a "Load Scene" option to load predefined templates such as Spaceships (light, large, glider), Gosper's glider gun, Still life, Oscillators, etc..
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!