What's a good way to implement pathfinding when the travelling object is not a point?

Question

I'm working on a game where I have a sea filled with islands. I want a ship (which has a large rectangular bounding box) to navigate this sea without bumping any islands. In some cases, the islands are clustered pretty close together (and there are a lot of them). Ideally, I'd like to end up with a list of waypoints that the ship can follow to avoid the islands.

In most of the pathfinding literature I've found, the path is assumed to be a point -- that's not the case in my situation (it's a large rectangle). What's a good algorithm I can apply to this case? Is A* search applicable to this case?

Answer 1

You need to combine "normal" topological path finding with geometric constraints.

This can be done by defining the network topology first and then checking to see whether links are viable for the ship.

As a first cut, suppose you define a square grid of suitable resolution, say the width of the ship. Remove all vertexes less than half the ship width from an island.

Create a link between each vertex and neighbours in the grid, including diagonals.

(*) For each link create the rectangle created by the ship as it goes straight along the link. Remove any that overlap an island.

You are now left with a "navigable" network - not allowing for turn radius etc.

You can play with the grid resolution or type for better results.

($) Also, the initial link set could contain links between non-adjacent vertices, giving smoother paths. Unless we allow quite long links in the initial set, this approach will still give a fairly uneven path.

So, take the path generated and attempt to see which nodes in that path could be removed without colliding with an island, as in step (*). Maybe that means we do not need to bother with step ($) or any diagonals?

Answer 2

I would put waypoint markers around the islands in the water and then run a standard path finding algorithm with those.