2

我正在为基于文本的游戏编写 AI，我遇到的问题是我被困在如何确定墙的最薄部分上。例如以下表示 2D 地图，其中 '^' 是想要穿过由 '*' 字符表示的墙壁到达标记为 'X' 的位置的字符：

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

我已经连续几天考虑这个问题了，但我已经没有想法了。我尝试使用 a* 算法，当它试图穿过墙壁字符时，g-cost 非常高。不幸的是，该算法决定从不通过墙壁进行路径查找。

代理只能左右上下移动，不能沿对角线移动，一次一个空间。

上例中穿过墙壁的最短路径是 1，因为它只需要穿过一个“*”字符。

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

4

4 回答 4

4

所有流行的图搜索算法通常都使用具有一些实数（即浮点/双倍）成本的成本来制定。但这不是要求。您真正需要的只是具有严格排序和加法等操作的东西。

您可以对此应用标准 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到目标的距离

一个直接的反对意见可能是“使用这种启发式方法，必须先探索墙外的整个空间，然后才能尝试穿过墙！” ——但这正是所要求的。

根据您提供的信息和要求，这实际上是最佳的 A* 启发式。

一种更复杂的方法可以提供更好的最佳情况性能，是将上述方法与双向搜索结合起来。如果您的目标是在一个很小的围墙区域内，则双向搜索可以在搜索的早期找到一些候选的“穿过墙的最便宜路径”。

于 2013-05-31T14:25:12.913 回答
2

把它做成一个加权图，给所有的“墙”一个大得离谱的权重。

小心不要溢出你的整数。

于 2013-05-31T15:43:22.463 回答
1

假设任何数量的移动总是比穿墙便宜（意味着 10000000000 次非穿墙移动比 1 穿墙移动便宜）（否则适当地设置成本会起作用），我可以看到任何算法的特殊情况我能想到这实际上并不涉及搜索整个地图，所以......

  • 从源头做一个详尽的 A*，停在墙上，记录每个位置的最短路径。
  • 对于靠近墙壁的每个探索位置，跨过墙壁。然后对所有这些进行组合 A*（如果适用），再次停在墙上。
  • 对于这些靠近墙壁的新探索位置中的每一个，穿过墙壁并继续 A*。
  • 依此类推……直到我们找到目标。

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

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

正如 Sint 所提到的，如果起点总是在一个开阔的区域，而终点总是在一个小区域，那么反向搜索会更有效。但这只有在你知道它是否适用的情况下才真正适用。检测它不太可能是有效的，一旦你做到了，你已经完成了大部分工作，如果两者都在合理大小的区域，你就会失败。

一个例子：

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

初始 BFS：

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

穿过墙壁和 BFS（没有 BFS 发生，因为它们无处可去，只能穿过墙壁）：（
我们可以忽略的标记为%）

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

Step into wall and BFS (BFS on target):

65%%
5%%%
4%%%
3%%%
于 2013-05-31T12:02:38.837 回答
1

使用 Dijkstra。

由于您正在处理基于文本的游戏，我发现您谈论的地图不太可能大于 1000 x 1000 个字符。这将以非常低的成本O(n*logn)和非常简单直接的代码为您提供有保证的最佳答案。

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

基本上，假设一个 32 位整数，一个经过 5 个空白空间和 3 个墙壁的状态将如下所示 0000000000000011 0000000000000101：如果你的地图真的很大，像迷宫一样，有很多墙，很少有墙等等，你可以调整这个表示来为每个信息使用更多或更少的位，或者如果你觉得更舒服，甚至可以使用更长的整数，如如果存在需要穿过超过 65,000 个空白空间的最短路径，则此特定编码示例将“溢出”。

使用单个整数而不是两个整数（对于墙壁/空白空间）的主要优点是您可以拥有一个简单的int mark[MAXN][MAXM];矩阵来跟踪搜索。如果你在穿5墙时到达了一个特定的方格，你不必检查你是否可以用 4、3 或更少的墙到达它以防止无用状态的传播——这些信息将自动嵌入到你的整数中，只要您将数量存储walls到更高的位中，您就永远不会重复路径，同时具有更高的“墙成本”。

这是一个在 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[][]
于 2013-05-31T15:32:14.800 回答