4

我已经实现了洪水填充算法，该算法将 array[15*15] 与路径一起使用，并生成他在填充路径时所采取的步骤队列。tl;博士看起来像这样

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
}

但是现在我有一系列步骤来填充网格，但我不知道如何应用这些信息让我的对象跟随并从头到尾。我的意思是，一条路径很简单，但如果它像这样分裂（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()) 它会做上帝知道什么。我如何过滤它，所以它只会退出然后停止？我不能把头绕在它周围。

4

3 回答 3

3

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

以这种方式，每当您找到从同一单元格经过的另一条路径时，如果距离小于存储的路径，则该路径比以前的路径更好，否则您可以忽略它并跳到下一个路径。

通过这种方式，您最终可以拥有多条到达目标的路径，但它们都具有相同的长度（因此您可以只选择其中之一）。到达目标节点后，您可以回溯：对于从目标开始距离x处的每个节点，搜索距离x-1处的邻居。

只是为了让您对我的意思有一个图形化的概念：

在此处输入图像描述

请注意，这不是最快的解决方案，它仅适用于小型平铺地图，对于较大的平铺地图，您需要比广度优先搜索更好的算法。

于 2013-01-12T22:08:58.757 回答
2

迪斯，我会说你走在正确的轨道上！

现在，您的代码将简单地遍历所有内容并且无处可去。你忘记了几件事。
首先，Enemy::find_path必须返回一个布尔值：它是否到达目的地。所以，在顶部你有

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

我注意到第一个是防止它回溯到自身之上。
第二个很清楚：它撞到了墙上。因此，必须return false在它之后表明它已经走到了死胡同。但是您需要第三个，这样，如果它到达目的地，它就会返回 true。

然后，当您调用四向迭代时，测试它们是否返回true。如果他们return true在达到目标后再次这样做，则搜索、查找并拉回源头！

请注意，压缩回源部分，因为那是您可以使用的部分。现在，您的队列将到处都是随机垃圾。走错路后它不会空。然而，这个后拉部分是完美的——而不是队列，使用堆栈，一旦到达目的地，在拉回堆栈时推送每个节点，从而提供从头到尾的完整路径！

希望我能帮忙;-)

编辑：好的，所以我必须提到一件更重要的事情：工作，但效率低下的路径。
你的算法会找到一条路径，但并不总是最短的路径——事实上，有时它甚至会找到一条很长的路径。幸运的是，解决这个问题有点简单。首先，您需要有目的地的坐标。然后，在find_path函数的每次迭代中，重新排序方向迭代器。首先你选择右，然后左，然后上，然后下。相反，看看哪个方向会朝着目标的方向前进。然后检查那个方向。如果失败，请尝试下一个最接近的。如果失败，则尝试下一个最近的，以及下一个最近的（嗯，现在是最远的）。

是的，我知道这不会是最短距离，因为它通常倾向于靠墙，但绝对比完全随机的方向要好。

于 2013-01-12T22:25:25.150 回答
0

在您获得的最终网格上进行深度优先搜索 (dfs)。

http://en.wikipedia.org/wiki/Depth-first_search

您将获得单独的路径。如果你想选择最短的，你可以做的优化很少。

  • 保持最大限制，如果 dfs 看起来比这更远，请跳过该路径。
  • 如果您找到长度小于最大限制的路径。将最大限制设置为。

希望这会有所帮助。

编辑：我写了这段代码，它应该适合你。它将以向量< pair > 作为 x,y 坐标给出最短路径。

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin("map.txt");

int width, height;
int map[10][10];
// Start (x,y), End (x,y)
int sy, sx, ey, ex;

bool visited[10][10];

vector<pair<int, int> > final_path;
int max_size = 9999;

void getInput() {
  fin >> width >>  height;

  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
        int x;
        fin >> x;
        map[i][j] = x; 

        if(x == 8){
          sy = i;
          sx = j;
        }

        if(x == 9){
          ey = i;
          ex = j;
        }
    }
  }
}

void dfs(int x, int y, vector<pair<int, int> > path) {
  if(path.size() > max_size){
    cout << "Returning : path size too big" << endl;
    return;
  }

  if(x < 0 || x >= width || y < 0 || y >= height){
    cout << "Returning : bounds" << endl;
    return;
  }

  // If the tile is blocked, can't go there
  if(map[y][x] == 0){
    cout << "Returning : blocked" << endl;
    return;
  }

  if(visited[y][x]){
    cout << "Returning : visited" << endl;
    return;
  }

  // We don't want to revisit a tile
  visited[y][x] = true;

  cout << "Visiting " << x << " " << y << endl;

  path.push_back(make_pair(x, y));
  if(map[y][x] == 9) {
    final_path = path;
    visited[y][x] = false;
    return;
  }

  dfs(x, y - 1, path);
  dfs(x + 1, y, path);
  dfs(x, y + 1, path);
  dfs(x - 1, y, path);

  visited[y][x] = false;

  return;
}

int main() {

  getInput();
  cout << "Got Input" << endl;
  cout << width << " " << height << endl;

  memset(visited, 0, sizeof(visited));
  vector<pair<int, int> > starting_path;

  cout << sx << " " << sy << endl;

  dfs(sx, sy, starting_path);

  cout << "Path size is " << final_path.size() << endl;

  for(int i = 0; i < final_path.size(); i++){
    cout << final_path[i].first << " " << final_path[i].second << endl;
  }

  return 0;
}

map.txt 包含您在问题中提供的地图。

于 2013-01-12T22:26:18.307 回答