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

As you see, there is a map and I want to pathfinding to identify which cities are liked each other.

The yellow tiles in the map are the Land, and blue ones are the ocean. The red font means there is a waterway, and the green font means there is a road. The correct path should be linked as road-road, waterway-waterway, road-harbor-waterway or waterway-harbor-road. Therefore,

2,6City can link to 2,4City via (2,6City)-(1,6)-(0,6)-(1,5)-(2,5)-(3,4Harbor)-(2,4City),

2,6City can link to 0,0City via (2,6City)-(1,6)-(0,6)-(1,5)-(2,5)-(3,4Harbor)-(2,4City)– (1,4)-(0,3City)-(0,2)-(0,1)-(0,0City),

2,6City can link to 3,0City via (2,6City)-(1,6)-(0,6)-(1,5)-(2,5)-(3,4Harbor)-(3,3)– (3,2)-(4,1Harbor)-(3,0City).

However, when I use GKGridGraph to create a map for Pathfinding, I don’t know how to tell the situation that waterway is not accessible to road. You can see, I DON‘T want:

2,6City can link to 2,4City via (2,6City)-(2,5)-(2.4City) or

2,4City is linked to 2,2City because (2,4City)-(3,4Harbor)-(3,3)-(3,2)-(2,2City)

So, any suggestion? Thanks a lot.

CodePudding user response：

If you are using GKGridGraph(fromStartingGridAt:width:height:diagonalsAllowed:) to create your graph then every node has connections to each of its neighbors. So a better picture of your map would be this:

Since every node is connected it will find the shortest path which will pass through the water. To prevent that you need to remove the impossible connections. Your graph should look something like this:

To achieve that you cam simply remove the unwanted connections from your graph using GKGraphNode.removeConnections(to:bidirectional:)

This could be achieved by a function like this one:

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)
}

Depending on how you store and load your map a better solution probably would be to start with an empty graph and only add the necessary connections while loading the map.