Thanks! You're guessing right, except that this is not quite A*.
Actually before I implemented the above solution I had found a discussion about A* and wormhole tunnels. As you know in A*, when picking a new node, you have to "estimate" the node's distance to the destination. And the proposal was to not take the distance from the new node but the distance from the wormhole tunnel's other end node to the destination.
This sounds quite reasonable. But I wasn't sure about mixing up distances and fuel costs, and so I stayed with Dijkstra (which is fast and robust in any case).
Bookmarks