我正在为 rts 游戏编写机器人（网格地图上一个村庄与另一个村庄对抗，还有可穿越的单元格 - 草、森林和不可穿越的单元格 - 水、山丘）。如何找到这两个单元格之间路径上的最窄点？对算法有什么建议吗？（我正在使用 A* 来寻找最近的路径，并且我想通过机器人决定将塔（坚固的防御建筑）放置在最窄的点上，这样敌人就无法穿越 - 可能可以，取决于地图，但可能性较小） .
问问题
275 次
2 回答
4
一些想法。
考虑一个（可能太多）简化版本，其中 X 代表不可交叉细胞，. 代表crossable，A代表一个村庄，B代表另一个。
XXXA.XXXXX
XXX..XXXXX
XX.....XXX
XXX....XXX
XXX...XXXX
XXX.....XX
XXXX....XX
XXXX.BXXXX
由于连接两个村庄的道路上没有“分支”，我们可以将地图转移到
000A100000
0001100000
0011111000
0001111000
C0001110000D
0001111100
0000111100
00001B0000
其中 0 和 1 表示在单元格上旅行的成本。道路上最窄的点是从 C 到 D 花费最少的路径。路径在下面的地图中用 # 表示
000A100000
##########
#01111100#
#00111100#
C#00111000#D
0001111100
0000111100
00001B0000
由于只有原始地图“道路”上的单元格成本大于 0，因此 C 和 D 之间成本最小的最短路径确实会给出道路上“最窄点”位置的线索。
好吧，这只是一个简化版本，因为只有一条“主要道路”连接两个村庄。但我希望它能以某种方式指出解决方案的正确方向。
于 2012-10-29T00:53:34.270 回答
2
请记住，这甚至不一定是您想要的。T考虑一个具有攻击范围的塔t
..t..
.ttt.
ttTtt
.ttt.
..t..
A和一个分支图，其中从点到点有一条窄的直接路径和一条宽的间接路径B。A假设标记周围的直接点n是可步行的，但不能建造塔。
xBxxxxxxx
x.......x
x.......x
x.......x
x..xx...x
x..xx...x
x..xx...x
x.......x
xnnn....x
xnnn....x
xAnxxxxxx
最初，字符将跟随路径p
xBxxxxxxx
xp......x
xp......x
xp......x
xp.xx...x
xp.xx...x
xp.xx...x
xp......x
xp......x
xp......x
xA.xxxxxx
放置T在最窄的点上，如果角色继续在同一路径上，将导致 3 次命中。但是，如果塔的痛苦相对于速度目标很高，例如肯定是致命的，则不会发生这种情况。相反，字符将被转移到更长的路径。
xBxxxxxxx
xp......x
xppppp..x
x.t..p..x
xttxxp..x
xtTxxp..x
xttxxp..x
x.t..p..x
x....p..x
xppppp..x
xA.xxxxxx
在这种情况下，更好的位置是保证至少一次命中的位置。（请记住，最接近的最佳位置T被A认为是不可建造的。）
xBxxxxxxx
x.......x
x.......x
x.......x
x..xx...x
x..xx...x
x.txx...x
xttTtt..x
x.ttt...x
x..t....x
xA.xxxxxx
因此，您可能想要的是一个T可以最大化最小成本路径的成本的位置，该路径将在T. 研究 maximin (minimax) 算法。当然，放置时还有其他需要考虑的事情，例如塔本身的防御性。
于 2012-10-29T15:27:42.867 回答