This week's book giveaway is in the Spring forum.
We're giving away four copies of Spring in Action (5th edition) and have Craig Walls on-line!
See this thread for details.
Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • 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
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Conway's Game of Life in Java  RSS feed

 
Bartender
Posts: 9493
184
  • Mark post as helpful
  • send pies
  • 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: 1973
57
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • 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: 1973
57
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • 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: 443
Chrome Linux VI Editor
  • Mark post as helpful
  • send pies
  • 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: 1973
57
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • 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.
 
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • 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.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!