如何判断Tile组是否为闭合环路并提取内部Tile？

我已实现Tile分组绘制系统，现需完成两个功能：

• 判断一组Tile是否构成闭合环路
• 若判定为闭合环路，找出并存储该环路内部的所有Tile

示例说明 #

• 示例1：不符合闭合环路要求
• 示例2：符合闭合环路要求（高亮Tile会被识别并存储）

现有代码及扩展实现 #

let grid;
const cols = 8;
const rows = 8;
let cellSize;

let filled = [];

class Cell {
  constructor(x, y) {
    this.pos = { x: x, y: y };
    this.filled = false;
    this.isGroup = false;
    this.group = false;
    this.isOuter = false; // 新增：标记是否为外部空白Tile
  }
}

// 4邻接判断（上下左右），用于环路结构验证
const adj4 = (px, py) => {
  const adjList = [];
  const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
  for (let [dx, dy] of dirs) {
    let x = px + dx;
    let y = py + dy;
    if (x >= 0 && x < cols && y >=0 && y < rows) {
      adjList.push(grid[y][x]);
    }
  }
  return adjList;
}

const adj = (px, py) => {
  const adjList = [];
 
  for (let x = px - 1; x <= px + 1; x++) {
    for (let y = py - 1; y <= py + 1; y++) {
      if (x < 0 || x >= rows || y < 0 || y >= cols || (x == px && y == py)) continue;
     
      adjList.push(grid[y][x]);
    }
  }
 
  return adjList;
}

function setup() {
  createCanvas(400, 400);
  cellSize = width / cols;
  initializeGrid();
}

const floodCheck = (current, group) => {
  const adjTiles = adj(current.pos.x, current.pos.y);
 
  const walls = adjTiles.filter(tile => tile.filled);

  if (walls.length === 0) return false;
 
  walls.forEach(wall => {
    if (!wall.isGroup) {
      wall.isGroup = true;
      wall.group = group;
      floodCheck(wall, group);
    }
  });
}

// 标记外部空白Tile的洪水填充
const markOuter = (x, y) => {
  if (x < 0 || x >= cols || y <0 || y >= rows) return;
  let cell = grid[y][x];
  if (cell.filled || cell.isOuter) return;
  cell.isOuter = true;
  markOuter(x-1, y);
  markOuter(x+1, y);
  markOuter(x, y-1);
  markOuter(x, y+1);
}

// 判断指定分组是否为闭合环路
const isClosedLoop = (groupNum) => {
  const groupTiles = filled.filter(t => t.group === groupNum);
  if (groupTiles.length < 4) return false; // 最小闭合环路至少需要4个Tile

  // 检查每个Tile的4邻接同组数量是否为2（无分支、无端点）
  for (let tile of groupTiles) {
    const sameGroupAdj = adj4(tile.pos.x, tile.pos.y).filter(t => t.group === groupNum && t.filled);
    if (sameGroupAdj.length !== 2) {
      return false;
    }
  }

  // 重置外部标记
  grid.forEach(row => row.forEach(cell => cell.isOuter = false));

  // 从边界空白Tile开始标记外部区域
  for (let x = 0; x < cols; x++) {
    markOuter(x, 0);
    markOuter(x, rows-1);
  }
  for (let y = 0; y < rows; y++) {
    markOuter(0, y);
    markOuter(cols-1, y);
  }

  // 检查是否存在未被标记为外部的空白Tile（即内部区域）
  for (let row of grid) {
    for (let cell of row) {
      if (!cell.filled && !cell.isOuter) {
        return true;
      }
    }
  }
  return false;
}

// 获取指定闭合环路的内部Tile
const getInnerTiles = (groupNum) => {
  const innerTiles = [];
  if (!isClosedLoop(groupNum)) return innerTiles;

  for (let row of grid) {
    for (let cell of row) {
      if (!cell.filled && !cell.isOuter) {
        innerTiles.push(cell);
      }
    }
  }
  return innerTiles;
}

function draw() {
  background(220);
 
  filled.forEach(tile => {
    tile.group = false;
    tile.isGroup = false;
  });
  
  let maxGroup;

  if (filled.length > 0) {
    // 分组墙Tile
    let group = 0;
    while (true) {
      const ungrouped = filled.filter(tile => tile.group === false);
      if (ungrouped.length === 0) break;
           
      const startTile = ungrouped[0];
      startTile.group = group;

      let current = JSON.parse(JSON.stringify(startTile));
      floodCheck(current, group);

      // 检查当前分组是否为闭合环路，若是则获取内部Tile
      if (isClosedLoop(group)) {
        const innerTiles = getInnerTiles(group);
        console.log(`分组${group}是闭合环路，内部Tile数量：${innerTiles.length}`);
        // 可在此将innerTiles存储到全局变量或进行其他业务处理
      }

      group++;
    }
  }
 
  // 绘制网格，内部Tile用黄色高亮
  for (let y = 0; y < rows; y++) {
    for (let x = 0; x < cols; x++) {
      let cell = grid[y][x];
      if (!cell.filled) {
        fill(cell.isOuter ? 255 : 255, 255, 0); // 黄色标记内部Tile
      } else if (cell.isGroup) {
        switch (cell.group) {
          case 0: fill(255, 0, 255); break;
          case 1: fill(100, 200, 50); break;
          case 2: fill(175, 50, 230); break;
          default: fill(0);
        }
      } else {
        fill(100);
      }
      rect(x * cellSize, y * cellSize, cellSize, cellSize);
    }
  }
}

function initializeGrid() {
  grid = [];
  for (let y = 0; y < cols; y++) {
    grid[y] = [];
    for (let x = 0; x < rows; x++) {
      grid[y][x] = new Cell(x, y);
    }
  }
}

function mousePressed() {
  let x = floor(mouseX / cellSize);
  let y = floor(mouseY / cellSize);

  if (grid[y][x].filled) {
    grid[y][x].filled = false;
    grid[y][x].isGroup = false;
    filled = filled.filter(cell => !(cell.pos.x == x && cell.pos.y == y));
  } else {
    grid[y][x].filled = true;
    filled.push(grid[y][x]);
  }
}

实现说明 #

1. 新增Cell属性：添加isOuter标记，用于区分外部空白Tile和内部空白Tile
2. 4邻接函数：新增adj4函数，仅返回上下左右四个方向的相邻Tile，用于验证环路结构的合理性
3. 环路判定逻辑：
   • 先校验分组Tile数量（至少4个才可能形成闭合环路）
   • 遍历分组内每个Tile，确保每个Tile的4邻接同组Tile数量为2（保证无分支、无端点）
   • 通过边界洪水填充标记外部区域，若存在未被标记的空白Tile，说明该分组形成了闭合包围
4. 内部Tile提取：在确认是闭合环路后，直接收集所有未被标记为外部的空白Tile即可
5. 可视化优化：绘制时用黄色高亮内部Tile，便于直观验证结果

内容的提问来源于stack exchange，提问作者jolly lingdonberry