Not logged inGosu Forums
Forum back to libgosu.org Help Search Register Login
Up Topic Gosu / Gosu Exchange / Ruby game of life with Gosu - update action not working
- - By ofcan Date 2013-03-15 00:43
I am creating Game of Life in Ruby using Gosu. My code is here on Stack Overflow. Right now, when I run 'ruby gosu.rb' it opens the window with proper dimensions and prepopulated World as it should.

But as soon as I uncomment '@game.tick!' in gosu file update action, upon running 'ruby gosu.rb' I get the black screen with no prepopulated World wich I cannot close. Why is that and how to fix this?

You can find github repo with rest of the code here. Any help is awesome.
Parent - - By jlnr (dev) Date 2013-03-15 05:02
It doesn't stop. You're just not patient enough :P

You have made that algorithm O(n^2) because you go over each cell, and then iterate over every live cell again to determine the number of live neighbours. So you are performing roughly 4800*2400 = 11 million iteration steps in total. If you change these two lines you can see your progress:

world.cells.each_with_index do |cell, index|
      puts "#{index} out of #{world.cells.size}"


The easiest optimisation is to remember the count of live neighbours instead of calculating it four times:

      # Use this variable in the if branches for "Rule 1" to "Rule 4"
      count = world.live_neighbours_around_cell(cell).count


With this optimisation, every step still takes a few seconds, but it's good to see that everything basically works. The real optimisation is not to have a loop in live_cells but to directly index the @cell_board array. That way your whole algorithm runs in O(n) complexity and should be real-time.

BTW - for visualisations like yours, it is usually nice to override Gosu::Window's needs_cursor? method to return true, this will stop the cursor from being hidden. The default value (false) is only really good for (some) games and I regret it. =/
Parent - - By ofcan Date 2013-03-15 09:15
Thank you very much! I made the window smaller and stored this neighbour_count into variable and now runs within reasonable amount of time :)

I am just wondering, can you please show exactly what you mean by this > "The real optimisation is not to have a loop in live_cells but to directly index the @cell_board array. That way your whole algorithm runs in O(n) complexity and should be real-time." How to implement that?
Parent - - By jlnr (dev) Date 2013-03-15 22:43
Instead of this... (the live_cells.each call is the problem - also, the comment is wrong :) ):
  def live_neighbours_around_cell(cell)
    live_neighbours = []
    live_cells.each do |live_cell|
      # Neighbour to the North
      if live_cell.x == cell.x - 1 && live_cell.y == cell.y
        live_neighbours << live_cell
      end
      ...


Do something like this:

def live_neighbours_around_cell(cell)
  live_neighbours = []
  # Neighbour to the North
  if cell.y > 0
    candidate = self.cell_board[cell.x, cell.y - 1]
    live_neighbours << candidate if candidate.alive
  end
  ...


This gets rid of the inner nested loop.

Another minor optimisation would be to return the count of neighbours from this method instead of constructing an array. Fixnums are easier on the garbage collector than Arrays.

BTW - with the modulo operator (%), you can easily implement wraparound at the board's edges in live_neighbours_around_cell.
Parent - By ofcan Date 2013-03-16 16:35
Thank you so much! I updated it and it works perfectly. :)
Parent - - By ofcan Date 2013-03-30 20:22
btw, I've made 17 videos of me making this game of life using TDD and Gosu. :) Maybe I can post it somewhere it can help someone? Here they are > http://svenduplic.com/2013/03/25/conways-game-of-life-in-ruby.html
Parent - - By jlnr (dev) Date 2013-03-31 02:19
Awesome. I've made a note to add it to the front page! Minor nitpick: On a browser without Flash (Safari to be exact), I just see empty areas where the videos are supposed to be :)
Parent - By ofcan Date 2013-03-31 23:54
Thanks man! :) Ah, thats jekyll and markdown and me messing things up. No worries, will get to the bottom of it :)
Up Topic Gosu / Gosu Exchange / Ruby game of life with Gosu - update action not working

Powered by mwForum 2.29.7 © 1999-2015 Markus Wichitill