Tips for custom pathfinding for a large world?

Hi, does anyone have suggestions for how to build a custom pathfinding algorithm for moving things on water, different islands and in the air for a large open world? Realise that this will be a relatively advanced algorithm, but any pointers? My plan for now is probably to try and make grids of different sizes and trace through smaller and smaller, when the pathfinder has found the main route?
Any tutorials or pointers would be very appreciated :smiley: