是否有已知的算法来检测确保形状连续性所需的像素？

Question

我正在尝试在 Javascript 中创建一个程序，使一个小形状在二进制 2D space 中随机演变。

第一条规则是形状使用的像素数保持不变。这是一个非常小的数字（目前是 9 个）。

第二条规则是所有像素应该保持连续（至少在它们的角处）。

在每一步中，一个像素被随机移除并移动到与其余像素接触的位置。但是，只有在不破坏形状连续性的情况下才能删除像素。

在附图中，蓝色像素点可以移动，红色像素点不能移动。

我不知道如何检测哪些像素是必须保持连续性的。 是否有任何已知的算法？这个问题似乎接近康威的生命游戏，但据我所知，康威的规则忽略了连续性的想法，并且不保持恒定数量活化细胞。目前还没有找到合适的元胞自动机算法

Answer 1

这些被称为切点或接合点，是的，有一个algorithm可以找到它们。

Answer 2

形状的约束非常简单，如果移动一个像素破坏了形状，那么它是一个无效的移动。

因为我们知道尺寸始终为 9 个像素，所以如果您对形状进行了填充，您可以通过计算像素数来确认形状是否有效，同时计算填充的像素数。

所以把它分成几个阶段。

随机选择一个属于形状的像素。
选择另一个随机像素，它是与第一个形状不同的形状的一部分。
移动随机像素。
使用自定义填充算法，从 2 处的像素开始。填充形状时计算填充的像素数。
如果填充的像素数不等于9，则移动该像素为无效移动。恢复原状。

下面是一个例子，肯定有可以优化的地方，但它应该是一个很好的起点。

更新：要处理多个形状并防止它们合并，这也将起作用。只需要一个小 mod，在填充过程中确保您移动的像素也包括在内。

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>

是否有已知的算法来检测确保形状连续性所需的像素？

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

javascript

algorithm

pixel

cellular-automata