基于JS与p5的方形逐层扩散网格河流路径查找实现问题

核心需求 #

• 基于网格搭建河流路由系统，查找沿河流延伸、覆盖指定数量单元格的连通路径，河流为块状非线状结构
• 替换原有深度优先泛洪逻辑，改为正方形圈层逐层向外扩展的遍历规则：先查找起点周围正方形范围内的河流邻格，再基于上一圈层向外扩展下一层正方形范围，全程保持路径连通
• 单元格属性规则：
  • 带.bee属性的单元格为河流单元格
  • 两类标记：点击选中的起点标记为红色（对应marked属性），查找到的路径单元格标记为黄色（对应marked2属性）

原有实现参考 #

原有代码采用递归深度优先搜索实现泛洪填充，会无差别遍历完所有连通的河流单元格，无法实现按圈层分层、控制路径长度的需求：

Cell.prototype.mark = function(x,y){
  this.marked = true;
  if (this.bee) {
    this.floodFill();
  }
}

var done = 0;

Cell.prototype.floodFill = function() {
  for (var xoff = -1; xoff <= 1; xoff++) {
    for (var yoff = -1; yoff <= 1; yoff++) {
      var i = this.i + xoff;
      var j = this.j + yoff;
      if (i > -1 && i < cols && j > -1 && j < rows) {
        var neighbour = grid[i][j];
        if (neighbour.bee && !neighbour.marked2) {
            neighbour.marked2 = true;
            neighbour.floodFill();
        }
      }
    }
  }
  done++
  console.log("D"+done);
}

改造方案 #

正方形圈层的本质是按切比雪夫距离分层：和起点切比雪夫距离为k的所有单元格，正好构成以起点为中心、边长为2k+1的正方形边界，天然匹配逐层扩展正方形的需求。采用广度优先搜索（BFS）按层遍历即可实现该逻辑，同时保证所有遍历到的单元格8连通，符合路径连通要求。

改造后代码如下：

// 按需修改该值，控制最终路径覆盖的单元格总数
const TARGET_PATH_LENGTH = 20;

Cell.prototype.mark = function(x,y){
  this.marked = true; // 标记起点为红色
  if (this.bee) {
    this.layeredSearch();
  }
}

Cell.prototype.layeredSearch = function() {
  // 队列维护待遍历单元格，记录每个单元格所属的圈层（和起点的切比雪夫距离）
  const searchQueue = [{ cell: this, layer: 0 }];
  this.marked2 = true;
  let counted = 1;
  let currentLayer = 0;

  while (searchQueue.length > 0 && counted < TARGET_PATH_LENGTH) {
    // 取出当前圈层所有待处理节点，保证整层处理完成后再进入下一层
    const currentLayerNodes = [];
    while (searchQueue.length > 0 && searchQueue[0].layer === currentLayer) {
      currentLayerNodes.push(searchQueue.shift());
    }

    // 遍历当前圈层所有节点，查找下一圈层的符合条件的邻格
    for (const node of currentLayerNodes) {
      const cur = node.cell;
      // 保留原有的8邻接遍历范围，匹配正方形扩展逻辑
      for (let xoff = -1; xoff <= 1; xoff++) {
        for (let yoff = -1; yoff <= 1; yoff++) {
          if (xoff === 0 && yoff === 0) continue; // 跳过单元格自身
          const i = cur.i + xoff;
          const j = cur.j + yoff;
          // 越界判断
          if (i < 0 || i >= cols || j <0 || j >= rows) continue;
          const neighbour = grid[i][j];
          // 是未标记的河流单元格则纳入路径
          if (neighbour.bee && !neighbour.marked2) {
            neighbour.marked2 = true; // 标记为黄色
            counted++;
            searchQueue.push({ cell: neighbour, layer: currentLayer + 1 });
            if (counted >= TARGET_PATH_LENGTH) break;
          }
        }
        if (counted >= TARGET_PATH_LENGTH) break;
      }
      if (counted >= TARGET_PATH_LENGTH) break;
    }
    currentLayer++;
  }
  console.log(`路径查找完成，共覆盖${counted}个河流单元格`);
}

实现说明 #

• 遍历过程严格按正方形圈层推进，每一轮扩展的范围都是在上一层正方形基础上向外扩1格的标准正方形轮廓
• 所有被标记的单元格都是8连通的，完全满足路径连通要求
• 达到指定的单元格数量后会立即终止遍历，不会遍历整个连通河流块
• 采用循环队列实现，没有递归调用，不会出现大网格下的栈溢出问题

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