Searching for still life - algorithm

[automator]

Hi,

I'm new to this forum and I was thinking about still life generator (it doesn't need to be strict). The code should be as simple as possible. Firstly I generate random matrix and then iterate though every element and check this two rules:
1. Live cell must have either 2 or 3 live neighbors.
2. Dead cell can have any number of live neighbors except 3.
If cell doesn't satisfy this rules, I toggle it (if it was dead, I make it alive etc.) untill it meets those rules. Unfortunately if I change one cell another needs to be fixed and it takes forever to stabilize.

So the question is:
How I can search for still life easier? Can you share some code/ideas how you do it?

Here is the code in matlab that I created according to my idea. The code is not working properly, especially the part where I'm trying to toggle the cell that meets the rules

Code: Select all

% live cell must have either 2 or 3 live neighbors.
% dead cell can have any number of live neighbors except 3.

DIM = 20;
M = randi(2, DIM+1) - 1;
%zeros the bounds
M(1,:) = 0;
M(DIM,:) = 0;
M(:,1) = 0;
M(:,DIM) = 0;

    for x = 2:length(M)
        for y = 2:length(M)
            %M = double((M & neighbours == 2) | neighbours == 3);
            neighbours = conv2(M, [1 1 1; 1 0 1; 1 1 1], 'same'); % returns numbers of neighbours
            if neighbours(x,y) == 1 || neighbours(x,y) == 0
                M(x,y) = 0;
            end
            if M(x, y) == 1 && (neighbours(x,y) > 3) || M(x, y) == 0 && neighbours(x,y) == 3 % still life
                if M(x,y)
                    todel = neighbours(x, y)-3;
                else
                    todel = 1;
                end
                   
                while todel
                    a = randi(3, 1) - 2; % randomly choose cell to toggle
                    b = randi(3, 1) - 2;
                    if (a || b)
                        M(x+a, y+b) = ~M(x+a, y+b); % toggle cell
                        sprintf('(%d, %d);;(%d, %d)',x, y, x+a, y+b)
                        neighbours = conv2(M, [1 1 1; 1 0 1; 1 1 1], 'same'); % returns numbers of neighbours
                        if ((M(x, y) == 1 && (neighbours(x,y) == 2 || neighbours(x,y) == 3)) ||  (M(x, y) == 0 && neighbours(x,y) ~= 3)) % still life
                            todel = todel-1;
                        end
                    end
                end
            end 
            
            M(1,:) = 0;
            M(DIM,:) = 0;
            M(:,1) = 0;
            M(:,DIM) = 0;
        end
    end
%end

imshow(M, 'InitialMagnification', 1000);
drawnow;

[dvgrn]

So the question is:
How I can search for still life easier? Can you share some code/ideas how you do it?

Paul Callahan's still-life generator comes to mind -- it's a Java applet, though, so it doesn't work automatically in most browsers, the way it used to.

I don't remember if anyone has come up with a modernized in-browser version of this, but the source code is right there if anyone wants to give it a try...!

[72c20e]

TIP:Depth first search

[BlinkerSpawn]

What sorts of conditions are you placing on your search? Just generating a random still life in an X-by-Y container?