一个寻路问题：如何判断水路情况？

Question

如你所见，有一张地图，我想寻路找出哪些城市互相喜欢。

图中黄色方块是陆地，蓝色方块是海洋。红色字体表示有水路，绿色字体表示有是一条路。正确的路径应该是 link 道路-道路，水路-水路，路-港-水路或水路-港-路。因此，

2,6City 可以通过 (2,6City)-(1,6)-(0,6)-(1,5)-(2,5)-( link 到 2,4City 3,4海港)-(2,4城市),

2,6City 可以通过 (2,6City)-(1,6)-(0,6)-(1,5)-(2,5)-( link 到 0,0City 3,4海港)-(2,4城市)– (1,4)-(0,3City)-(0,2)-(0,1)-(0,0City),

2,6City 可以通过 (2,6City)-(1,6)-(0,6)-(1,5)-(2,5)-( link 到 3,0City 3,4海港)-(3,3)– (3,2)-(4,1港口)-(3,0城市).

但是，当我使用GKGridGraph为Pathfinding创建地图时，我不知道如何讲述水路不通公路的情况。你可以看到，我不想要：

2,6City 可以通过 (2,6City)-(2,5)-(2.4City) 或 link 到 2,4City 或

2,4City linked 为 2,2City 因为 (2,4City)-(3,4Harbor)-(3,3)-(3,2)-(2,2City)

那么，有什么建议吗？非常感谢。

Answer 1

如果您使用 GKGridGraph(fromStartingGridAt:width:height:diagonalsAllowed:) 创建您的图，那么每个节点都与它的每个邻居都有连接。所以你的地图的更好的图片是这样的：

由于每个节点都是相连的，它会找到最短的路径穿过水。为防止这种情况，您需要删除不可能的连接。您的图表应如下所示：

要实现这一点，您只需使用 GKGraphNode.removeConnections(to:bidirectional:)

从图表中删除不需要的连接

这可以通过这样的函数来实现：

func disconnect(_ a: vector_int2, _ b: vector_int2) {
    guard
        let first = grid.node(atGridPosition: a),
        let second = grid.node(atGridPosition: b)
    else {
        return
    }

    first.removeConnections(to: [second], bidirectional: true)
}

根据您存储和加载地图的方式，更好的解决方案可能是从一个空图开始，并且仅在加载地图时添加必要的连接。

一个寻路问题：如何判断水路情况？

A pathfinding problem: how to tell water-road situation?

algorithm

path-finding

ios

swift

gameplay-kit