c++ - 在C++中应用寻路算法(塔防)

Question

我已经实现了泛洪填充算法，该算法采用带有路径的数组 [15*15] 并生成他在填充路径时所采取的步骤队列。 tl;dr 它看起来像这样

std::queue <int> f_path;

void Enemy::find_path(int *map, int *grid, int node) {

    if (grid[node] == 1) // colored-grid
        return;
    if (map[node] == 0) // grid with defined map (0 - no path, 1 path)
        return;

    f_path.push(node);
    grid[node] = 1;

    if ((node + 1) % 15 != 0) this->find_path(map, grid, node + 1); // go right
    if (node % 15 != 0) this->find_path(map, grid, node - 1); // go left
    if (node - 15 > 0) this->find_path(map, grid, node - 15); // go up
    if (node + 15 < 15*15) this->find_path(map, grid, node + 15); // go down
}

但现在我有一个填充网格所需的步骤队列，但我不知道如何应用这些信息让我的对象从头到尾遵循和完成。我的意思是，只有一条路很简单，但如果它像这样 split (9 是导出):
0 0 1 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 9 0 0
我将在队列中有左右路径，所以如果我做一个简单的 go(f_path.front()) 它会做什么天知道。我如何过滤它，所以它只会退出然后停止？我无法理解它。

Answer 1

我不知道您的算法的确切内部结构，但您可以通过将每个节点与当前路径请求中找到的起始节点的最小距离关联起来，轻松获得到达目的地的最短路径。

通过这种方式，只要你发现另一条路径从同一个单元格经过，如果距离小于存储的路径，那么这条路径比之前的路径更好，否则你可以忽略它并跳到下一条。

通过这种方式，您最终可以有不止一条到达目标的路径，但它们的长度都相同(因此您可以只选择其中一条)。一旦到达目标节点，您就可以回溯:对于距离 x 的每个节点，从目标开始搜索距离 x-1 的邻居。

只是为了让您对我的意思有一个图形化的了解:

请注意，这不是最快的解决方案，它仅适用于小型图 block map ，对于较大的图 block map ，您需要比 breadth first search 更好的算法。 .