this and that, but have never seen that of which I was most proud and was most successful in terms of bringing both fun and immersion of exploration into the game world: charting the open seas.
The premise of the campaign was in some ways similar to Chris Perkins' Iomandra Campaign, although I assure you we came up with similar ideas independently. In it, scattered disparate islands on a watery world were kept under the oppressive regime of the Arkhosian Empire. The dungeoneers were the chosen few who could rise up and defeat the Empire. To do so, however, they needed to (among other things) unite the far-flung island communities and become masters of the open seas. The focus of this post is how our group collectively created the mechanics to go about exploring a vast oceanic world.
Before any dice were rolled, the campaign started with a Party Creation Template, not unlike the kind suggestion by Chatty DM. One key part of the was the question posed to everyone: "What one island locality do you have a connection to? What is that connection?" The very first thing we did at the table together as a group was draw those islands on a huge 30" sheet of paper, which would later become our map. As Dungeon Master, I gave the campaign the initial impetus to action by drawing the stating location, known as Korth Island, where the first adventure was to be had on the dead center of the map. There was no scale here, one would be added weeks later when we started messing around with rules for travel time and running out of provisions while at sea. The map was free-form, with everyone just doodling in their own little corner of this new world.
As the campaign progressed, new islands were hinted to, sought after, and ultimately discovered. The locations of these islands was always given in some sort of easy to decode puzzle format. The most common of these was a very simple system of listing the name of the constellation to point towards, and then how many miles to travel, although often the origin point of the directions become a mystery in and of themselves. the constellations, as you can see from the image below, needed only be a symbol representative of a direction. I used evenly spaced directions around 360-degrees, but could have easily spiced things up with gaps and clumps of constellations across the night sky.
I created a compass rose, a physical prop and guide to slap down on the table to represent the stalwart dungeoneers, gazing up at the night sky, circumnavigating the globe using nothing but the stars and the wind. Luckily for us, one of the players had ready access to a transparency machine, creating a clean piece of plastic that could be easily placed onto our map for exploration purposes. When we needed to, we came to decide that every 50 miles was an inch on the map. We had a lot of fun times hunched over the gaming tables, charting the locations of the world's scattered islands,
These sheets of paper would go on to inspire curiosity and an insatiable itch for exploring the unknown and finding out just where everything was. Through reverse-engineering, the dungeoneers were later able to determine the point of origin for all of these directions by finding one of the islands (Carr-Hae perhaps?) and going backwards. Many of these locations hint at the destinies of the plots, family members, and various entanglements of the dungeoneers. For example, the isle of Rhegium had the location of Bane's Fallen Temple, leading the dungeoneers to find The Iron Codex at the behest of one of the dungeoneers who was keenly interested in finding the fallen temples of the gods.
Exploration of new worlds is one of the major draws that got me into this hobby, and something that too often gets thrown to the wayside in favor of developing railroading plotlines as if the Dungeon Master were writing a novel. Develop the world, shroud it in mystery, make things interesting, and let your players steer the boat.