2

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.

antonakos
  • 8,261
  • 2
  • 31
  • 34
Emil Ivanov
  • 37,300
  • 12
  • 75
  • 90

4 Answers4

6
  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

Tiendil
  • 541
  • 3
  • 11
  • I definitely agree with the approach of breaking the grid down into a more manageable search space, and also with the other idea of simply implementing object avoidance to go round islands. – Kylotan Dec 02 '10 at 18:17
  • Wow, this idea with the vertexes in a graph seems quite good. Will try and report results. – Emil Ivanov Dec 02 '10 at 21:04
  • One more thing bothers me - how do I connect the vertexes and the points without crossing the islands? – Emil Ivanov Dec 02 '10 at 21:53
  • For each pair of points you should check if line segment (between points) intersect with any of the polygons. To check intersection of line segment and polygon you can check if segment intersect one of it border. So you need function to check intersection of two line segments, which described, for example, here: http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect. – Tiendil Dec 03 '10 at 10:00
1

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.

Michael
  • 41,026
  • 70
  • 193
  • 341
  • 2
    This algorithm will be invoked many times a second - it has to be damn fast. – Emil Ivanov Dec 02 '10 at 13:53
  • 1
    If the grid does not change, you can pre-calculate in advance the shortest paths for all node pairs. Picking up a path by node pair definitely will be damn fast :) – Michael Dec 02 '10 at 14:09
0

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.

Emile
  • 2,200
  • 27
  • 36
0

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.

antonakos
  • 8,261
  • 2
  • 31
  • 34