Ship movement algorithm

Question

Let's say we have a rectangular sea. It's quite large - 10000x20000.

We have islands, as well. For simplicity's sake, let's assume they are rectangular as well. We know their exact places (coordinates).

If we have a ship, somewhere on the map - (x1, y1), how can we find the shortest path to another point on the map (x2, y2) without going over any of the islands?

Update: There are no constraints so far - for the ship or for the sea. If we can simplify (and speed up) things by adding a few - this is more than welcome.

The path even doesn't have to be the best - it can be 10% off for example - perfectly acceptable.

Answer 1

1. aproximate islands' borders with 2D poligons
2. connect vertexes of separated poligons (and start and finish points) with edges (they must not cross islands)
3. apply A* to resulting graph

Such graph much less then 10000x20000 grid and let find more realistic paths in better time

Update: if islands is not big you can just move ship in direction of finish point and bypass islands on their left or right border

Answer 2

I would try to represent the grid as a graph and run the Dijkstra algorithm.

The graph probably takes 1G or even more, but it fits RAM in any modern computer.

The algorithm complexity is O(E + V*log(V)), i.e. O(size of the grid). Since there are ~10^8 nodes, I guess it must be feasible. Let's say we have ~1000 CPU ticks per node. If we have 4G CPU, a tick is 2.5*10^-10 sec, i.e. we have 2.5*10-7 sec. per node. For 2*10^8 nodes we have ~ 1 minute.

Answer 3

If the islands are relatively sparse in a big see, you could use an algorithm I implemented last year for robots chasing a moving ball in an environment with objects to avoid.

What I did was define grid points around the the robot, the ball, and the obstacles, and add a sparse uniform grid over the whole environment. The cost of an edge between two gridpoints depends on how close obstacles are to this edge (if the edge goes through the obstacle cost would be infinite). Then calculate the best route using A*. This is done 40 times per second on an old laptop, programmed in Java.

Answer 4

Related to Tiendil's suggestion, LaValle's Planning Algorithms book has a discussion of what edges to include in graphs for shortest-path searches if the islands are 2D polygons.