• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Conway's Game of Life in Java

 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The real difficulty is writing an algorithm that finds the final state of the system in a reasonable amount of time. The final state is the first generation where the game starts to repeat itself.
 
Bartender
Posts: 2911
150
Google Web Toolkit Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I haven't really researched that. But I have a simple idea.

First, we can create a "State" object which stores the full board. Next, one can write an algorithm to generate a "hash" of the current state. This can be based on any logic. Eg hashcode of string containing all cells with row, col values separated by a delimiter.
Now, all we have to do is to generate a list of states and advance the game further. For every new state, a search can be made on all previous states. Here's where our hash comes in handy, to filter out all states matching our hash to make our search faster. They may or may not be the same since collisions are expected. The better the hash algorithm, the faster our search gets.

My logic is a "brute force" one there could be better ways.
 
salvin francis
Bartender
Posts: 2911
150
Google Web Toolkit Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:The final state is the first generation where the game starts to repeat itself.


What's the final state if the game contains a single glider?
The game will never repeat itself to the previous state.
 
Ranch Hand
Posts: 574
VI Editor Chrome Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Might be quicker to make a list of cells that change each generation.  When that list is empty you've got a steady state system.  If you save 2-4 lists from prior generations and compare the current changelist to prior changelists you can detect systems that repeat every 2-3-...-whatever cycles.
 
salvin francis
Bartender
Posts: 2911
150
Google Web Toolkit Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jim Venolia wrote:Might be quicker to make a list of cells that change each generation.  When that list is empty you've got a steady state system.  If you save 2-4 lists from prior generations and compare the current changelist to prior changelists you can detect systems that repeat every 2-3-...-whatever cycles.


Your system will work for a Blinker or a Pentadecathlon since after n generations, they are back to where we started from.

Now, lets say we have a simple Blinker and a Lightweight spaceship or a Glider besides it such that they don't interfere. The Blinker will stay at its location and continuously blink till infinity and the Glider will continuously traverse across the direction we point it to till infinity. The "change" will always be unique since the glider is moving infinitely and the blinker oscillates infinitely. It will never have a final state.
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That may hold for an unlimited playing field, but every finite NxM field has a cycle of at most 2^(NxM). Three interesting extra rules that I made (well, such were the hopes) is that living cells can die of old age, dead cells may spring to live due to quantum fluctuations, and the classification 23-3 may fluctuate from time to time to something else and back again. Another idea I once had was trying to combine a GoL field with that of the path of a particle as we know from the days when fractals were very popular. Lack of hardware and intelligence were due to the fact that it remained a vague idea.

The main problem with GoL is however that staring at the consequences soon becomes boring, no matter what rules. Bringing in some colors only helps temporaryly.
reply
    Bookmark Topic Watch Topic
  • New Topic