В значительной степени вам нужно разделить море на пиксели и сделать что-то вроде A *. Вы могли бы немного оптимизировать его, объединив смежные пиксели в большие области, но если вы сохраните все квадраты, это, вероятно, облегчит поиск. Поиск больше не будет в манхэттенском стиле, но если у вас будет достаточно много квадратов, дополнительное время принятия решения о подключении будет более чем компенсировано.
В качестве альтернативы, вы можете итеративно «вырастить» многоугольники из всех ваших портов, создав выпуклые многоугольники (так, чтобы любая точка внутри многоугольника была достижима из любой другой, не выходя наружу, вы хотите, например, избежать формы PacMan) , хотя это уточнение / усложнение / оптимизация подхода «квадратов», о котором я впервые упомянул. Ключ в том, что вы знаете, когда попадаете в область, куда вы можете попасть куда-либо еще в этой области.
Не знаю, поможет ли это, извините. Это был долгий день. Удачи, хотя. Звучит как забавная проблема!
Редактировать: Забыл упомянуть, вы также можете предварительно обработать вашу область в квадродерево. То есть, возьмите всю свою карту и разделите ее пополам по вертикали и горизонтали (вам не нужно делать оба разделения одновременно, и если вы хотите потратить некоторое время на создание «лучших» разделений, вы можете сделать это позже) и делайте это рекурсивно до тех пор, пока каждый узел не окажется полностью сухопутным или морским. Из этого вы можете тривиально создать сеть соединений (просто подключите соседние листья), и A * должно быть достаточно простым для реализации оттуда. В любом случае, это будет самый простой способ реализовать мое первое предложение. :)