看不到如何将 flood fill routine 更改为 DFS one

Question

我一直在使用泛洪填充例程检查某种类型的块，然后找到相同类型的所有连接块并将它们更改为类型 "stone" 我主要对块的坐标感兴趣，不想更改它们，但是当我删除 "change to stone" 语句时，它似乎无休止地运行。经过研究，深度优先搜索似乎可行，但不确定如何实现 - 似乎我只需要调整洪水填充，但我尝试的所有内容要么无限循环，要么在第一次迭代时停止。这里是原程序。

//interact
var node1 = {
 xy : []
};
var blockp;
//starting block type and position
blockp = world.getBlock(npc.getBlockX(), npc.getBlockY() - 1, npc.getBlockZ() + 1);
node1.xy[0] = npc.getBlockX();
node1.xy[1] = npc.getBlockZ() + 1;
node1.xy[2] = npc.getBlockY() - 1;
//
var floodfill = function (nameb, node) {
 if (nameb == "minecraft:stone" || nameb == null) {
  return;
 }
 var blkname;
 var xy0 = node.xy[0];
 var xy1 = node.xy[1];
 var xy2 = node.xy[2];
 //
 //Line I would like to remove
 world.setBlock(node.xy[0], node.xy[2], node.xy[1], world.createItem("minecraft:stone", 0, 1));
 //
 // collect x y z positions for all blocks
 world.getTempData("X_corr").push(node.xy[0]);
 world.getTempData("Y_corr").push(node.xy[2]);
 world.getTempData("Z_corr").push(node.xy[1]);
 //
 node.xy[0] = xy0;
 node.xy[1] = xy1 + 1;
 node.xy[2] = xy2;
 if (world.getBlock(node.xy[0], node.xy[2], node.xy[1]) == null) {
  blkname = null;
 } else {
  blkname = world.getBlock(node.xy[0], node.xy[2], node.xy[1]).name;
 }
 floodfill(blkname, node);
 //
 node.xy[0] = xy0;
 node.xy[1] = xy1 - 1;
 node.xy[2] = xy2;
 if (world.getBlock(node.xy[0], node.xy[2], node.xy[1]) == null) {
  blkname = null;
 } else {
  blkname = world.getBlock(node.xy[0], node.xy[2], node.xy[1]).name;
 }
 floodfill(blkname, node);
 //
 node.xy[0] = xy0 + 1;
 node.xy[1] = xy1;
 node.xy[2] = xy2;
 if (world.getBlock(node.xy[0], node.xy[2], node.xy[1]) == null) {
  blkname = null;
 } else {
  blkname = world.getBlock(node.xy[0], node.xy[2], node.xy[1]).name;
 }
 floodfill(blkname, node);
 //
 node.xy[0] = xy0 - 1;
 node.xy[1] = xy1;
 node.xy[2] = xy2;
 if (world.getBlock(node.xy[0], node.xy[2], node.xy[1]) == null) {
  blkname = null;
 } else {
  blkname = world.getBlock(node.xy[0], node.xy[2], node.xy[1]).name;
 }
 floodfill(blkname, node);
 //
 node.xy[0] = xy0;
 node.xy[1] = xy1;
 node.xy[2] = xy2 + 1;
 npc.say("go up " + blkname);
 if (world.getBlock(node.xy[0], node.xy[2], node.xy[1]) == null) {
  blkname = null;
 } else {
  blkname = world.getBlock(node.xy[0], node.xy[2], node.xy[1]).name;
  npc.say("go up " + blkname);
 }
 floodfill(blkname, node);
 //
 node.xy[0] = xy0;
 node.xy[1] = xy1;
 node.xy[2] = xy2 - 1;
 if (world.getBlock(node.xy[0], node.xy[2], node.xy[1]) == null) {
  blkname = null;
 } else {
  blkname = world.getBlock(node.xy[0], node.xy[2], node.xy[1]).name;
 }
 floodfill(blkname, node);
 //
 return;
}
floodfill(blockp.name, node1);

Answer 1

让我从 floodfill 永不结束的原因开始：它不知道什么时候必须停止，因为 none 个块发生了变化。该程序认为它以前从未遇到过该块，并一次又一次地查看它...

深度优先搜索是一种不断深入直到无法再进行搜索的搜索方法。当你碰到一个部分的末尾时，你会返回，直到遇到一个你以前从未见过的项目，然后尽可能深入地研究与之相关的任何内容。

广度优先搜索恰恰相反。它检查连接到您的起点的内容，检查所有内容，然后检查他们的所有子项，以及他们的子项等等。

因为您想找到所有相互连接的块，所以您选择这些搜索方法中的哪一种都没有区别，因为它们会以相同的 O(n) 复杂度找到所有项目。

我个人对您要制作的东西一无所知，但我正在努力使它尽可能具有普遍性。

对于这些搜索中的任何一个，block 应该有一个名为 visited 或类似名称的变量，您可以使用它来表示您之前是否遇到过此块。您可能必须自己创建此变量。您还需要一种方法来查找 block 连接到的所有 block 并将 return 作为数组或列表。在示例中，我将调用此函数 neighbours().

要实施 DFS，您需要 Stack。堆栈是后进先出的数据结构，这意味着最后进来的东西最先出来。将一些东西放入堆栈称为 push。取回物品称为 pop.

这是 DFS 的伪代码：

DFS(Block start) {
    Stack stack = new stack();
    stack.push(start); // Put the first block in the stack
    while(stack.count > 0) {
         Block current = stack.pop();

         if(current.visited)
              continue; // if we've already seen this block, don't bother 
         current.visited = true;

         /* YOU CAN DO ANYTHING YOU WANT WITH THE BLOCK HERE */

         Block[] neighbours = current.neighbours();
         foreach(neighbour in neighbours)
              stack.push(neighbour);
    }
}

BFS 是不同的，并且稍微更适合您正在尝试做的事情。它使用 Queue 以先进先出的顺序存储需要搜索的所有内容。这意味着搜索树中更靠下的东西将被稍后搜索，这通常更适合任何搜索。向队列中添加东西称为 enqueue，取出下一个东西称为 dequeue。

这是 BFS 的伪代码：

BFS(Block start)
    Queue queue = new Queue();
    queue.enqueue(start); // Put the first block in the stack
    while(queue.count > 0) {
         Block current = queue.dequeue();

         if(current.visited)
              continue; // if we've already seen this block, don't bother 
         current.visited = true;

         /* YOU CAN DO ANYTHING YOU WANT WITH THE BLOCK HERE */

         Block[] neighbours = current.neighbours();
         foreach(neighbour in neighbours)
              queue.enqueue(neighbour);
    }
}

正如你所看到的，两种搜索方法非常相似，它们都是运行在 O(n) time complexity.

祝编码顺利！

看不到如何将 flood fill routine 更改为 DFS one

Can't see how to change flood fill routine to DFS one

javascript

minecraft