Searching for still life - algorithm

For scripts to aid with computation or simulation in cellular automata.
Post Reply
automator
Posts: 1
Joined: January 14th, 2017, 8:39 am

Searching for still life - algorithm

Post by automator » January 14th, 2017, 8:53 am

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;

User avatar
dvgrn
Moderator
Posts: 6725
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Searching for still life - algorithm

Post by dvgrn » January 14th, 2017, 11:53 am

automator wrote: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
Posts: 55
Joined: June 10th, 2016, 5:52 am

Re: Searching for still life - algorithm

Post by 72c20e » May 25th, 2017, 10:01 am

TIP:Depth first search

Code: Select all

x = 15, y = 36, rule = B38/S23-
bo$2bo$3o14$13bo$12bo$12b3o2$11bo$12bo$10b3o4$12b3o$12bo$13bo2$10bo$8b
obo$9b2o$6b2o$5bobo$7bo!

User avatar
BlinkerSpawn
Posts: 1964
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Searching for still life - algorithm

Post by BlinkerSpawn » May 25th, 2017, 11:23 am

What sorts of conditions are you placing on your search? Just generating a random still life in an X-by-Y container?
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Image

Post Reply