Stack overflow when trying to increase the size of a functioning "Game of Life"-patch

SignalsInNoise

Hi folks! I've been getting to know Pd and having a ton of fun doing it, but I've run into a pickle that is turning the fun more towards frustration
As my first project, I decided to build a musical version of Conway's Game of Life, and I even got a small version of it working, but trying to make the game a bit larger has stalled on a weird issue that I just can't seem to solve.

Basically, my "game" is made up of cells, which are abstractions that are identical in every way, except they take as a creation argument a number, which determines both the order in which the cells are processed, and their position in the game grid. When the game grid is loaded up, a bang goes to cell number 1, which reads its own creation argument and calculates based on that, and the number of rows and columns in the grid, which cells are its neighbors. It then sends a bang to cell 2, which does the same and sends a bang to cell 3 etc.
"Playing" the game works similarly, with cell 1 first calculating how many neighbors it has alive, and then telling cell 2 to do the same etc. Once the last cell is reached, a new bang is sent to cell 1 telling it to set its new state, and this instruction is again passed forward to cell 2 etc.

This all works fine in a 5-by-5 grid. In fact, I've even been able to "play" some music using this smaller version (and it sounds pretty fantastic as well!). However, if I increase the number of rows and columns to 10, I get a "stack overflow" error when I load the grid up. Specifically, I've located the problem to cell number 56: it still has all its neighbors set up properly, but cell number 57 no longer does, implying that somehow cell 56 fails to send 57 the instruction to set up. This is quite strange considering that there is nothing different about cell number 56 compared to the previous cells, which have all worked fine.
I've checked that the creation arguments are correct, and the neighbors get set up correctly (though even if they didn't, the setup shouldn't cause a stack overflow). I can't think of an issue with the order of operations either, as the setup is handled cell-by-cell.

All ideas on what could be causing this would be be greatly appreciated! If anyone wants to dig deeper, here is a zip with the cell-abstraction and two versions of the grid-patch: one with 25 cells (this works), and another with 100 cells (this doesn't): game_of_life.zip
(I've taken out all the code having to with actually playing music with that thing so it's easier to understand, so it's just the visual part of the game, but it works standalone.)

oid

@SignalsInNoise Your problem suggests something which is shared by all the cells, quick glance and all I see is nrows/ncols, these [value]s are all being written too by all the cells, 56 is probably were all those cells writing too them overflows the stack, this is why we normally use $0 here and since you want to use it in expression appending the dollar zero will simplify things since you will not need to make it a symbol and feed it into an inlet, so nrows$0 and ncols$0. I only took a quick looks, so someone may come and correct me.

SignalsInNoise

All of the cells access nrows and ncols, in the expressions where the indices of the neighbors are computed, but shouldn't change them. The state of each cell, which is also stored as a variable, is also accessed by all of it's neighbors, but not every other cell (and this only happens once the game starts, not on setup). Otherwise there shouldn't be things shared across the cells.

So is it possible that a cell is still accessing ncols / nrows when it passes the bang forward to the next cell cell to start its setup, and somehow the order is mixed up there? I don't really know what Pd does in the background when accessing a variable, but I guess that could happen if the expressions only start fetching the variable and the cell-patch progresses in the background.

Thanks for the helpful comment, will have to look into $0 more!

bocanegra

@SignalsInNoise said:

All of the cells access nrows and ncols, in the expressions where the indices of the neighbors are computed, but shouldn't change them. The state of each cell, which is also stored as a variable, is also accessed by all of it's neighbors, but not every other cell (and this only happens once the game starts, not on setup). Otherwise there shouldn't be things shared across the cells.

As far as I understand the patch ncols and nrows are global constants. As such $0 should not be needed and would screw up the cell mechanics... BUT they are somehow set by the cells (I can't seem to figure out how???) and this could indeed stir up some trouble

So is it possible that a cell is still accessing ncols / nrows when it passes the bang forward to the next cell cell to start its setup, and somehow the order is mixed up there?

I think this is most likely

I don't really know what Pd does in the background when accessing a variable, but I guess that could happen if the expressions only start fetching the variable and the cell-patch progresses in the background.

Again I am having trouble digesting what happens in what order inside the cells. You are using triggers everywhere but creation order of objects play into what gets processed first as well. In order to make things more transparent for yourself, I'd have the globals (ncols,nrows) defined only in the main patch and perhaps an external clock triggering each operation.

Also I seem to recall other shots at game of life being posted in this forum, so maybe have a look at how other people have tackled it?

bocanegra

Just saw the ncols and nrows are indeed set in the main patch (my screen resolution is too small to notice). So at least half of what I wrote is nonsense

Inserting [print] objects lets you see what happens when. Try this: cell.pd - I only put two [print] objects to get told by pd when each cell gets and sends a setup bang. Oddly cell 1 seems to be the last to both send and receive anything - in other words, it looks like PD is processing everything backwards... We know this can't be the case since cell 1 is the first to receive a setup bang, but nonetheless, it's the last to get printed.

However, if you probe the [v ncols] object with a [print], you will see that it gets banged before any setup bangs are sent. Inserting an [f ] buffer before the [select 0 1] like this should ameliorate this:

And it does indeed - somewhat.... Stack overflow now occurs at cell 64 rather than 56

It would seem I have localized the problem but not come up with a viable solution... YET....

oid

I find doing some cleaning to help sort problems out, so I cleaned up the patched and moved all the setup stuff into it's own abstraction. Stack overflow no longer happens on setup for the 100 cell, but we get a stack overflow in cell.pd on the [f $1} for storing the number. 25 cell version seems to work, but I only could do a quick check of things. I am out of time for the day so it is off to other to sort it out. Files in the zip have the same name and no containing folder, so careful where you unpack.
life.zip

Edit: did some clean up which I forgot.

Edit2: on some thinking, you have each cell banging the next, this can cause problems and is likely the cause of the overflow, replace this with an [until] triggered by nrows x ncols as I did in the setup abstraction, this will probably fix things, or at least the current stack overflow.

bocanegra

@oid your idea is brilliant (keep setup in a separate abstraction) but the game is buggy now.

My ideas have been to replace all the [expr] objects with puritan vanilla sub patches, increase block size, keep init stuff out of the cells, and tighter control with what gets done when.

Block size turned out to be irrelevant. First attempt at rewriting one expr block as a subpatch of logic failed, inserting a controlled buffer just before the whole cascade of expr objects was a small success

I think you are right about the "chain reaction" of bang to next cell causing the overflow but at this point I am going with my gut feeling

oid

@bocanegra how did it become buggy? My guess would be it is something in cell.pd, deleted something I should not have in that bit of afterthought cleaning. Will check later if someone does not find the issue.

Ultimately each cell only needs to be a single bit memory, everything else can be moved out. So a toggle with its sends and receives properly set will do nicely and make it simple to dynamically patch the field. But we need to leave some room for @SignalsInNoise to learn, cant just hand him a perfect completed patch.

Each cell banging the next is just rolling your own loop, which can be useful but has issues since creation order starts playing a roll. We have [until] for looping, it is more efficient, gives a more readable patch and almost fool proof, you need a good reason to roll your own.

bocanegra

@oid said:

@bocanegra how did it become buggy? My guess would be it is something in cell.pd, deleted something I should not have in that bit of afterthought cleaning. Will check later if someone does not find the issue.

I always test the game with a simple XXX oscillator. It cancels out to nothing over 4 generations in your patch when it should be oscillating.

Ultimately each cell only needs to be a single bit memory, everything else can be moved out. So a toggle with its sends and receives properly set will do nicely and make it simple to dynamically patch the field. But we need to leave some room for @SignalsInNoise to learn, cant just hand him a perfect completed patch.

Agreed. And I am trying real hard to keep my hands out of the patch

Each cell banging the next is just rolling your own loop, which can be useful but has issues since creation order starts playing a roll. We have [until] for looping, it is more efficient, gives a more readable patch and almost fool proof, you need a good reason to roll your own.

I have less experience with the control domain, but my gut tells me the same: the cells are feeding in to each other (not just one way) and are causing non-deterministic behavior. Tighter control of what happens when is needed. This is a case for @ingox

ingox

@bocanegra Yes, i was thinking the same thing, but didn't check the code until the end.

So i was wondering if a simple approach could be that each cell would update its neighbors if its state changes. As each cell would store the current count of active neighbors, each cell would send 1 when changing to 1 and -1 when changing to 0.

So on each new round each cell would already know their neighbors and can update accordingly. It is just that in this step Pd is going through all cells. And as each cell could affect also the following cells, the update has to be delayed, until each cell has already determined their next state.

That is why i used [pipe] in this implementation: game_of_life.zip

This way each cell will update to their new state and after all cells are updated, each cell will inform their neighbors if their state has changed.

The neighbors get identified by their rows and columns. I also numbered the cells starting at 0 and added $0 for everything.

SignalsInNoise

Wow guys, thanks for all the super helpful suggestions! Been busy with work so I haven't had time to dive deeper into them but I'm now quite confident I'll be able to tackle the issue once I do over the weekend

ingox

@SignalsInNoise Here are some other implementations of the Game of Life:

With data structures:

https://forum.pdpatchrepo.info/topic/10916/conway-s-game-of-life-implementation-with-data-structures

With ofelia:

With Ofelia / Emscripten (working in the browser):

https://forum.pdpatchrepo.info/topic/13459/simplesequencer-game-of-life-ofelia-emscripten

SignalsInNoise

So I ended up pretty much rewriting the whole thing.

@oid 's suggestion to handle the setup in its own abstraction with unitl was a game changer (pun very much intended )! The setup actually became redundant as I realized that I can just loop through the cells on each round using until and appropriate expressions. I used if-statements to clean up the expressions massively and moved almost everything outside the cells, which now only receive the number of neighbors, and, on the last round of the loop, a bang to update their state if necessary.

Good news: everything seems to work now, and the patches are much prettier than before.
Bad news: I still don't really understand what was wrong with the original version. But yeah, some weirdness must have been going on with the "custom loop" that the cells made up.

Here's my solution for anyone interested: game_of_life_v2.zip

Thanks for the help everyone! Next step: making the game play some music

oid

@SignalsInNoise Nicely done. I did up your next step for you. From this you should be able to make the entire thing a single abstraction which you start up with x and y as arguments to the abstraction. This will also allow you to add $0 to all you [value]s and the like so you can run multiple copies of your game at once without them interfering. One bug noticed, it seems not to work with unequal x and y values. Learning at least basic dynamic patching is a real time saver.
dynamic_life.pd

SignalsInNoise

@oid This is great! I thought something like this should be possible, will have to study your patch a bit to get what's going on, but that definitely saves a bunch of manual labor when creating the grid.

And yeah, I didn't test it with unequal rows & columns. Probably something wrong with the expression.