首页 文章

通过墙找到最短路径的算法

提问于
浏览 次
2

我正在为一个基于文本的游戏编写AI，我遇到的问题是我如何确定如何确定墙的最薄部分 . 例如，以下代表2D Map ，其中'^'是想要通过'*'字符表示的墙到达标记为'X'的位置的字符：

------------------
|  X *           |
|*****           |
|****            |
|***             |
|**      ^       |
|                |
|                |
|                |
------------------

我已经连续几天都在考虑这个问题而且我的想法已经用完了 . 我尝试过使用*算法，当它试图通过墙角时，g-cost非常高 . 不幸的是，算法决定永远不会在墙上寻找路径 .

代理只能左右上下而不是对角线，一次只能移动一个空格 .

上面例子中通过墙壁的最短路径是一条，因为它只需要通过一个'*'字符 .

我只需要几个简单的想法:)

algorithm path-finding shortest-path

4 回答

  • 1

    所有流行的图搜索算法通常用具有一些实数（即浮动/双重）成本的成本来制定 . 但这不是必需的 . 所有您真正需要的成本都是严格的订购和添加等操作 .

    您可以对此应用标准A * .

    • 定义表格 (a,b) 的成本

    • a 是墙细胞上的移动次数

    • b 是正常单元格上的移动次数 .

    • 定义这些单元格的排序如下：

    • [(a1,b1) < (a2,b2)] == [(a1<a2) || (a1==a2 && b1<b2)]

    • 这只是一个字典排序，我们总是喜欢在墙壁上移动更少的移动，然后我们更喜欢在正常细胞上移动更少的移动

    • 如下定义对这些成本的添加操作：

    • (a1,b1) + (a2,b2) == (a1+a2,b1+b2)

    • 将启发式（即剩余目标距离的下限估计）定义为 (0,b) ，其中 b 是距目标的曼哈顿距离

    一个直接的反对意见可能是“通过启发式，在试图穿过墙壁之前，必须探索墙外的整个空间！” - 但这正是要求的 .

    根据信息和要求，您实际上 the optimal A *启发式 .

    更复杂的方法可以提供更好的最佳案例性能，将上述内容与bidirectional search结合起来 . 如果您的目标位于一个很小的区域内，双向搜索可以在搜索的早期找到一些候选"cheapest paths through the wall" .

    回复于
  • 4

    只需将其作为加权图，并给所有“墙壁”一个荒谬的大重量 .

    小心不要溢出整数 .

    回复于
  • 2

    假设任何数量的移动总是比通过墙壁便宜（意味着10000000000非穿墙移动比1穿墙移动便宜）（否则设置成本适当），我可以看到任何算法的特殊情况我可以想到这几乎不涉及搜索整个 Map ，所以......

    • 从源头做一个详尽的A *，停在墙上，记录每个位置的最短路径 .

    • 对于靠近墙壁的每个探索位置，穿过墙壁 . 然后将所有这些（如适用）的A *组合起来，再次停在墙壁上 .

    • 对于靠近墙壁的这些新探索位置中的每一个，穿过墙壁并继续A * .

    • 等等......直到我们找到目标 .

    跳过已经探索过的位置 - 新路径应该总是比已经存在的路径长 .

    你真正想要做A *而不是BFS的唯一原因是因为当你到达包含目标的区域时，这将允许更少的探索 . 这是否更有效取决于 Map .

    正如Sint所提到的，如果开始时间总是在一个开阔的区域并且终点位于一个小区域内，那么反转这种搜索会更有效率 . 但这只有在您知道是否真的时才适用 . 检测它不太可能有效，一旦你有了，你就会失败，如果两者都在合理大小的区域 .

    An example:

    X** |
**  |
**  |
** ^|

    初始BFS：

    X**3
**32
**21
**10

    穿过墙壁和BFS（没有BFS发生，因为他们无处可去，但通过墙壁）：
    （我们可以忽略的那些标有 % ）

    X*4%
*4%%
*3%%
*2%%

    步入墙和BFS（BFS到目标）：

    65%%
5%%%
4%%%
3%%%
    回复于
  • 1

    使用Dijkstra .

    因为你're dealing with a text-based game, I find it highly unlikely that you'谈论大于1000×1000字符的 Map . 这将以非常低的成本 O(n*logn) 为您提供最佳答案，并且代码非常简单直接 .

    基本上，每个搜索状态都必须跟踪两件事：到目前为止你走了多少墙，以及有多少常规的空白空间 . 通过假设例如每个墙具有要遍历的2 ^ 16的成本，可以将其编码为用于搜索和标记矩阵的单个整数 . 因此，Dijkstra的自然顺序将确保首先尝试具有最少墙壁的路径，并且在穿过墙壁之后，您不会重复已经到达的路径而不经过尽可能多的墙壁 .

    基本上，假设一个32位整数，一个状态已经通过5个空格和3个墙，将看起来像这样： 0000000000000011 0000000000000101 . 如果你的 Map 真的很大，像迷宫一样，墙壁很多，墙壁很少，或者诸如此类的东西，你可以调整这种表示来为每个信息使用更多或更少的位，或者如果你觉得更舒服，甚至可以使用更长的整数，如如果存在需要遍历超过65,000个空白空间的最短路径，则此特定编码示例将为"overflow" .

    使用单个整数而不是两个整数（对于墙/空间）的主要优点是，您可以使用单个简单的 int mark[MAXN][MAXM]; 矩阵来跟踪搜索 . 如果您在穿过 5 墙时到达了特定的方格，则无需检查是否可以使用4个，3个或更少的墙到达它以防止无用状态的传播 - 此信息将自动嵌入到整数中，只要将 walls 的数量存储到更高的位中，就不会在具有更高的"wall cost"时重复路径 .

    这是C中一个完全实现的算法，考虑它是伪代码，以便更好地可视化和理解上面提出的想法:)

    int rx[4] = {1,0,-1,0};
int ry[4] = {0,1,0,-1};
int text[height][width]; // your map
int mark[height][width]; //set every position to "infinite" cost
int parent[height][width]; //to recover the final path

priority_queue<int64_t, vector<int64_t>, greater<int64_t> > q;
int64_t state = (initial_y<<16) + initial_x;
q.push(state);
while(!q.empty()){
    state = q.top(); q.pop();
    int x = state & 0xFF;
    int y = (state>>16) & 0xFF;
    int cost = state>>32;
    if(cost > mark[x][y]) continue;
    if(text[x][y] == 'X') break;
    for(int i = 0; i < 4; ++i){
        int xx = x+rx[i];
        int yy = y+ry[i];
        if(xx > -1 && xx < width && yy > -1 && yy < height){
            int newcost = cost;
            if(text[yy][xx] == ' ') newcost += 1;
            else newcost += 1<<16;
            if(newcost < mark[yy][xx]){
                mark[yy][xx] = newcost;
                parent[yy][xx] = i; //you know which direction you came from
                q.push( ((int64_t)newcost << 32) + (y<<16) + x);
            }
        }
    }
}
// The number of walls in the final answer:
// walls = state>>48;
// steps = (state>>32) & 0xFF; // (non walls)
// you can recover the exact path traversing back using the information in parent[][]
    回复于

相关问题