2

I've seen this post and want to do something similar, but not exactly the same.

I am implementing a little game of life game and using numpy arrays for representing the states of the game. So I need to check, how many alive neighbors a cell has. I already got a function for getting a window of neighbors given a coordinate and row count and column count for the window size that I want to have.

So usually my windows will be of 3x3 size like this:

T = True
F = False
[[T,T,T],
 [F,T,T],
 [F,F,F]]  # some random truth values

In this representation True stands for a cell being alive. Now I wrote some code iterating over all cells of the state, counting the True values and so on using a double for loop, but I think there is probably a better numpy solution.

What I'd do in the naive approach:

  1. iterate over all cells of the state (not only the window) (I'd like to formulate some code to to be executed if a cell meets a criteria or another (being alive and surviving or being dead and coming alive))
  2. get the window (wrapping or not wrapping) (function for that I already have)
  3. check if the current cell is alive (could just do a lookup in the state's numpy array)
  4. if it is alive start with an alive neighbors count of -1 otherwise start with 0
  5. count all True values of the window (np.sum) and add it to the alive neighbors count (which is -1 if the cell itself was alive, so that I only count neighbors but not the cell itself)
  6. depending on whether the count of alive neighbors is in certain ranges (configurable), write in another (new) state's array True values. (I'd start out with an array, which I created using: np.full((height, width), False, dtype=bool))
  7. go on with that new array, keeping the old one in a list for history or logging purposes

Basically:

if cell meets criteria:
    write True at the cell's position in a new array

However meeting the criteria depends on multiple rows, because the state's numpy array is a 2D array. That's why I think the linked post is close but not exactly what I need.

How can I do this in an efficient numpy-y way, avoiding unnecessary looping?

Clarification

I am searching for the best way of implementing this in python using numpy and scipy, which aims to be very readable and has good performance.

Community
  • 1
  • 1
Zelphir Kaltstahl
  • 5,722
  • 10
  • 57
  • 86
  • 1
    Write a version that does all the iterations explicitly, but clearly. And give us a test case to use with it. Then we can help streamline it, most likely starting with the inner most loop, where you do the `sum`. – hpaulj Apr 19 '16 at 02:16
  • You could probably do this easily with `scipy.ndimage.filters` with a window size of 3. Treating True as 1 and False as 0, a `generic_filter` might work, with `function=lambda a: 1 if a.sum() - a[4] > 4 else 0`. But it's tough to say without explicit input/output examples. – wflynny Apr 19 '16 at 02:20

1 Answers1

2

Perhaps I did not understand all you are trying to do, but what is stopping you from simply using the numpy.sum function?

Example - Let the state be:

import numpy as np
state = np.random.randint(1, 10, (9,9))

Here I am using {0, 1} as values for the state, where 1 means "alive". Then you can just slice around the cell being investigated, e.g. [2,3]

s = state[1:3,2:5]
if s[1,1]:
   val = -1
else
   val = 0
val += s.sum()

If you put this in a for loop and pay attention to border cases, clamping or wrapping as appropriate, it should do what you describe.

If you are looking for a short elegant implementation, it can be done very efficiently with Python and Numpy.

Cyb3rFly3r
  • 1,321
  • 7
  • 12
  • Sounds good so far. I only would like to avoid that loop looping over all cells and each iteration slicing etc. - If this is somehow possible. That link :D I should've searched for something like a solution before I started ... I'll check it and see if I can adopt the code. – Zelphir Kaltstahl Apr 19 '16 at 02:04
  • 1
    The loop is implicit in the problem: you have to sum the value of the neighbors in the end. Even the very elegant code in the link is using a generator expression with a nested loop, which has to be executed one way or the other. – Cyb3rFly3r Apr 19 '16 at 02:10
  • Cybr..., you are treating `s` like a nested list, not an array. – hpaulj Apr 19 '16 at 02:11
  • @hpaulj True! Got my syntax mixed up (been programming too much in C :), thank you and fixed. – Cyb3rFly3r Apr 19 '16 at 02:14
  • I was thinking you'd also want to do some boolean masking, but you are only testing one item in `s`. So that `if` is ok ( `val = -1 if s[1,1] else 0` is minor alternative). – hpaulj Apr 19 '16 at 02:20
  • So much could be done to make it better.. if you write a full example, I will vote you up! – Cyb3rFly3r Apr 19 '16 at 02:21
  • It states: _"Note that neither of these are extremely performant: they involve creating several temporary arrays, and will not work well for large problems with many time steps."_ Is there a faster way using numpy and scipy than the convolve2d function? – Zelphir Kaltstahl Apr 19 '16 at 11:34
  • @Zelphir Not that I am aware of. If you are really looking for performance for *game of life* you need to go to a compiled language and probably implement HashLife. – Cyb3rFly3r Apr 19 '16 at 13:10
  • @Cyb3rFly3r I think I don't need super performance, but I'd like to do it in a way, that no one could say _"You could have done that in an easier, more readable way, which is more performant!"_ I still don't understand why convolve2d does exactly what I want. I know convolve operation from image processing, but it was used to determin things given precisely the position of other pixels, not only the count of those, so I am not sure why it still works. – Zelphir Kaltstahl Apr 19 '16 at 13:57
  • @Cyb3rFly3r I finally understood what that code on the website is doing completely. Thanks for sharing that link, I feel confident in that solution now. – Zelphir Kaltstahl Apr 20 '16 at 01:50