c++ - 如何找到网格中两个单元格之间路径中的最窄点

Question

我正在为 rts 游戏编写机器人(在网格 map 上一个村庄对另一个村庄，还有可交叉的单元格 - 草地，森林 - 和不可交叉的单元格 - 水，山丘)。如何找到这两个单元格之间路径上的最窄点？对算法有什么建议吗？ (我正在使用 A* 找到最近的路径，我想机器人决定在哪里放置塔(坚固的防御建筑)，放置在最窄的点上，这样敌人就不能绕过 - 可能可以，取决于 map ，但不太可能) .

Answer 1

一些想法。

考虑一个(可能太多了)简化版本，其中 X 代表不可交叉的单元格，.代表 crossable，A 代表一个村庄，B 代表另一个。

XXXA.XXXXX
XXX..XXXXX
XX.....XXX
XXX....XXX
XXX...XXXX
XXX.....XX
XXXX....XX
XXXX.BXXXX

由于连接两个村庄的道路上没有“分支”，我们可以将 map 转移到

    000A100000
    0001100000
    0011111000
    0001111000
   C0001110000D
    0001111100
    0000111100
    00001B0000

其中 0 和 1 表示在单元格上行驶的成本。道路上的最窄点是从C 到D 花费最少的路径。该路径在下图中用# 表示

    000A100000
    ##########
    #01111100#
    #00111100#
   C#00111000#D
    0001111100
    0000111100
    00001B0000

由于只有原始 map “道路”上的单元成本大于 0，因此最小化 C 和 D 之间成本的最短路径确实会给出道路上“最窄点”位置的线索。

好吧，这只是一个简化版本，因为只有一条“主干道”连接着两个村庄。但我希望它能以某种方式指明解决方案的正确方向。