Is there a known algorithm to detect pixels required to assure the continuity of a shape?

Question

I am trying to create a program in Javascript to make a small shape evolve randomly in a binary 2D space.

The first rule is that the number of pixels the shape uses remains constant. It's a very small number (currently 9).

The second rule is that all the pixels should remain contiguous (at least by their corner).

At each step, one pixel is randomly removed and moved to a position in contact with the remaining pixels. However, the pixel can be removed only if it doesn't break the continuity of the shape.

In the attached picture, the blue pixels can be moved whereas the red ones cannot.

I don't know how to detect which pixels are mandatory to maintain the continuity. Is there any known algorithm for that? The issue seems close to Conway's Game of life but I as far as I know Conway's rules ignore the idea of continuity and don't maintain a constant number of activated cells. I haven't found any suitable cellular automaton algorithm so far.

Answer 1

The constraints for the shape are very simple, if moving a pixel breaks the shape then it an invalid move.

Because we know the size is always 9 pixels in size, you can confirm if a shape is valid by counting the number of pixels if say you did a floodfill on it, while counting the number pixels filled.

So breaking this down into stages.

1. Pick a random pixel that's part of the shape.
2. Pick another random pixel that's part of the shape that is not the same as first.
3. Move random pixel.
4. Use a custom floodfill algorithm starting at the pixel got at 2. While filling the shape count the number of pixels filled.
5. If the number of pixels filled is not equal to 9, then moving the pixel was an invalid move. revert back to the original.

Below is an example, there is certainly places it could be optimised, but it should be a good starting point.

UPDATE: To handle multiple shapes, and prevent them merging, this will also work. Just a small mod is required, during the fill make sure that the pixel you moved is also included.

const canvas = document.querySelector('canvas');
const ctx = context = canvas.getContext('2d');
canvas.width = 20;
canvas.height = 10;
ctx.imageSmoothingEnabled = false;

let i = ctx.getImageData(0, 0, canvas.width, canvas.height);

const pp = (x,y) => (x + (y*canvas.width)) * 4;

function putpixel(x, y, t) {
  const s = pp(x,y);
  i.data[s] = t ? 255 : 0;
  i.data[s + 3] = t ? 255 : 0;
}

function getpixel(x, y) {
  const s = pp(x,y);
  return i.data[s] === 255;
}
  
  

for (let y = 0; y < 3; y += 1) 
  for (let x = 0; x < 3; x += 1)
    putpixel(x + 4,y + 4,true);
//let add 2 shapes, still work?    
for (let y = 0; y < 3; y += 1) 
  for (let x = 0; x < 3; x += 1)
    putpixel(x,y,true);



ctx.putImageData(i, 0, 0);

function findPixel(active) {
  while (true) {
    const x = Math.trunc(Math.random() * canvas.width);
    const y = Math.trunc(Math.random() * canvas.height);
    const p = getpixel(x,y);
    if (p === active) return {x,y, p:y*canvas.width + x};
  }
}


function isValid(p, p2) {
  let count = 0; 
  let hit = false;
  const done = {};
  function fill(x, y) {
    const pstr = `${x}:${y}`;
    if (done[pstr]) return;
    if (x < 0) return;
    if (x >= canvas.width) return;
    if (y < 0) return;
    if (y >= canvas.height) return;
    if (!getpixel(x, y)) return;
    count += 1;
    
    if (!hit) {
      if (p2.x === x && p2.y === y) hit = true;
    }
    
    done[pstr] = true;
    fill(x -1, y - 1);
    fill(x   , y - 1);
    fill(x +1, y - 1);
    
    fill(x -1, y);
    fill(x +1, y);
    
    fill(x -1, y + 1);
    fill(x   , y + 1);
    fill(x +1, y + 1);   
  }
  fill(p.x, p.y);
  return count === 9 && hit;
}
    
function evolve() {
  i = ctx.getImageData(0, 0, canvas.width, canvas.height);
  
  const movePixel = findPixel(true);
  const otherPixel = findPixel(true);
  if (movePixel.p !== otherPixel.p) {
    const rndPixel = findPixel(false);
    putpixel(movePixel.x, movePixel.y, false);
    putpixel(rndPixel.x ,rndPixel.y, true);
    if (isValid(otherPixel, rndPixel))  
      ctx.putImageData(i, 0, 0);
  }
  setTimeout(evolve, 0);
}


setTimeout(evolve, 0);

* { 
  padding: 0;
  box-sizing: border-box;
  margin: 0;
}

html {
  height: 100%;
}

body {
  background-color: black;
  display: grid;
  justify-content: center;
  align-content: center;
  height: 100%;
}

canvas {
  transform: scale(19);
  image-rendering: pixelated; 
}

<canvas>
</canvas>