How to cluster cells in a Cellular Automata?

Question

I'm trying to code a Cellular Automata similar to Conway's Game of Life, but with altered rules which should result in clustered cells.

My only rule is: If the cell has less than N neighbours, it moves to a random empty neighbouring field. If it has more than N neighbours, it stays where it is. This should result in a clustered matrix where there are no lone cells. The cells are generated at random in the beginning, and should stay the same amount throughout the whole thing.

However, my problem is that the number of cells keeps decreasing with each loop and I just can't figure out why.

I am doing this in p5.js. This is the code I have so far (I took the original Conway's Game of Life and altered it). I think the problem probably lies in the "rules" part at the end of the code.

var n = 3;
let w;
let columns;
let rows;
let board;
let next;

function setup() {
  frameRate(2);
  createCanvas(600, 600);

  // width of one cell
  w = 10;

  // calculate columns and rows
  columns = floor(width / w);
  rows = floor(height / w);

  // make a 2D array
  board = new Array(columns);
  for (let i = 0; i < columns; i++) {
    board[i] = new Array(rows);
  }

  // going to use multiple 2D arrays and swap them
  next = new Array(columns);
  for (i = 0; i < columns; i++) {
    next[i] = new Array(rows);
  }

  init();
}

function draw() {
  background(255);
  generate();
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      if (board[i][j] == 1) fill(0, 0, 255);
      else fill(255);
      //stroke(0);
      noStroke();
      rect(i * w, j * w, w - 1, w - 1);
    }
  }
}

// reset board when mouse is pressed
function mousePressed() {
  init();
}

// fill board randomly
function init() {
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      // lining the edges with 0s
      if (i == 0 || j == 0 || i == columns - 1 || j == rows - 1)
        board[i][j] = 0;
      // filling the rest randomly
      else board[i][j] = floor(random(2));
      next[i][j] = 0;
    }
  }
}

// creating the new generation
function generate() {
  
  // loop through every spot in 2D array
  for (let x = 1; x < columns - 1; x++) {
    for (let y = 1; y < rows - 1; y++) {
      
      // add up all the states in a 3x3 surrounding grid
      let neighbors = 0;
      for (let i = -1; i <= 1; i++) {
        for (let j = -1; j <= 1; j++) {
          neighbors += board[x + i][y + j];
        }
      }
      // subtract the current cell's state
      neighbors -= board[x][y];

      
      // RULES (this is probably where the problem is)

      if (board[x][y] == 1 && neighbors <= n) {
        
        // check a random neighbor
        var i = 0;
        while (i < 9) {
          var randomCheckX = [
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
          ];
          var randomCheckY = [
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
          ];

          // if the neighbor is dead, turn alive
          if (board[x+randomCheckX[i]][y+randomCheckY[i]] == 0) {
            next[x+randomCheckX[i]][y+randomCheckY[i]] = 1; // random neighbor turns alive
            next[x][y] = 0; // current cell dies
            i = 10; // stop the loop

            // if the neighbor is alive, look for another random neighbor
          } else {
            i++;
          }
        }

      // the alive cells with enough neigbors stay alive and the dead cells stay dead
      } else {
        next[x][y] = board[x][y];
      }
    }
  }

  // swap
  let temp = board;
  board = next;
  next = temp;
}

This is the kind of result I anticipate, but obviously it's not working.

I am doing this for a uni project and the deadline is this Friday, so I really appreciate any help or tips you have!

user_16462950 · Answer

A neighbor that has turned alive in the line

next[x+randomCheckX[i]][y+randomCheckY[i]] = 1;

will turn dead again later in the line

next[x][y] = board[x][y];

That might cause the effect you observe, and it is certainly against the rules as you describe them.

Addendum

In the following code, the generate method has two phases:

Count the neighbors and determine the targets of the moves.
Carry out the moves.

Phase 1 only reads from the board and phase 2 only writes. The next board is no longer needed.

var n = 3;
let w;
let columns;
let rows;
let board;

function setup() {
  frameRate(2);
  createCanvas(600, 600);

  // width of one cell
  w = 10;

  // calculate columns and rows
  columns = floor(width / w);
  rows = floor(height / w);

  // make a 2D array
  board = new Array(columns);
  for (let i = 0; i < columns; i++) {
    board[i] = new Array(rows);
  }

  init();
}

function draw() {
  background(255);
  generate();
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      if (board[i][j] == 1) fill(0, 0, 255);
      else fill(255);
      //stroke(0);
      noStroke();
      rect(i * w, j * w, w - 1, w - 1);
    }
  }
}

// reset board when mouse is pressed
function mousePressed() {
  init();
}

// fill board randomly
function init() {
  for (let i = 0; i < columns; i++) {
    for (let j = 0; j < rows; j++) {
      // lining the edges with 0s
      if (i == 0 || j == 0 || i == columns - 1 || j == rows - 1)
        board[i][j] = 0;
      // filling the rest randomly
      else board[i][j] = floor(random(2));
    }
  }
}

// creating the new generation
function generate() {
  var moves = [];

  // loop through every spot in 2D array
  for (let x = 1; x < columns - 1; x++) {
    moves[x] = [];
    for (let y = 1; y < rows - 1; y++) {
      if (board[x][y] === 0) continue; // empty cells stay empty

      // add up all the states in a 3x3 surrounding grid
      let neighbors = 0;
      for (let i = -1; i <= 1; i++) {
        for (let j = -1; j <= 1; j++) {
          neighbors += board[x + i][y + j];
        }
      }
      // subtract the current cell's state
      neighbors -= board[x][y];
      if (neighbors <= n) {
        
        // check a random neighbor
        var i = 0;
        while (i < 9) {
          var randomCheckX = [
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
          ];
          var randomCheckY = [
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
            random([-1, 0, 1]),
          ];

          // if the neighbor is dead, turn alive
          if (board[x+randomCheckX[i]][y+randomCheckY[i]] == 0) {
            moves[x][y] = {
              x: x+randomCheckX[i],
              y: y+randomCheckY[i]
            }; // random neighbor turns alive
            i = 10; // stop the loop

            // if the neighbor is alive, look for another random neighbor
          } else {
            i++;
          }
        }
      }
    }
  }

  // carry out moves
  for (x = 1; x < columns - 1; x++)
    for (y = 1; y < rows - 1; y++)
      if (moves[x][y]) {
        board[moves[x][y].x][moves[x][y].y] = 1;
        board[x][y] = 0;
      }
}

How to cluster cells in a Cellular Automata?

1 Answers

Addendum