I’m a big fan of the map edge as the world border – the book is cool but a little too fantastical for my tastes, like it’s “just as story” rather than “part of a larger story”. The map implies travel, which may lead on to there being other locations; and of course you can make that explicit if you do go with neighbouring towns or civilizations by having “to the ____ of ___” written along the edges with arrows. They need not even be other towns, the Valley of Dragons or the Forest of Woes or the Iron Hills or whatever would all give the impression that there’s a whole world outside the boundaries of this town/settlement.
The island and floating island feel more like biomes than map edges. They look thouroughly awesome and I want to play both of them; but those two ideas have more gameplay potential than just marking out the edges of the playing area.
I actually really like the look of the clouds, but I can understand how the cliff-like effect can work against the intention. That said, I’d really like to see clouds added; since we already have the cloud shadows moving across the ground. Don’t Starve does a really cool trick to let you know when you’re at the limit of your zoom involving clouds, and I think this would be a great gameplay/UI use for clouds that feels immersive. If you’re looking down from really high up (i.e. max zoom), there could be a border of clouds outside the playing area beyond the map border; plus a few clouds floating across the playing area. From lower down, the clouds aren’t shown, so you avoid issues with them looking weird from underneath. That lets players know immediately that they’ve reached the max zoom, and the limits of what they can directly see and control. As they get closer to the ground, they can see the map edge more clearly, and know that it will be up to their hearthlings (who can get even closer still) to actually cross that map border in order to make contact with the other sides.
One thing I’d like to point out though: I haven’t seen any complaints about a “boring” map edge; to me that means no players have a problem with it or find it immersion-breaking. That doesn’t mean it can’t be improved; but what it does mean is that your players’ expectations basically line up with what they’re seeing already in the map edge. If you make the map edge cooler, players will have a new set of expectations to go along with that. If you go with the book, then it’s reasonable to assume some carry-over of the story from one ‘chapter’ (save game) to the next; if you go with the map style border then players will expect to be able to connect the maps to contact neighbours and so on. The island absolutely mandates some kind of boats or sailing; even if it’s just for trading and exploring with off-map neighbours. The floating island would necessitate some kind of story about why that chunk of world was torn out and thrown into the sky; and probably some kind of portal or flight mechanic to explain how visitors get there…
Whichever way you go, most of the cooler options require something else to really make them pop. So, I’d suggest you guys hold off on any changes to the map border until you’ve nailed down what gameplay effect it has – are there neighbours, trade routes, invading armies (I’m thinking dozens- or even hundreds-strong forces that set up a camp near the map edge and prepare for a full-on conquest), allies requesting your aid, etc. etc.? When you know how players will interact with the map edge (or not at all, if that’s what you end up with), you can express that much more easily through artistic choices; but right now the ideas are disconnected from what the player actually gets to do with the map edge.
As I see it, there’s no urgency at all to implement map edge improvements; so that gives you a LOT of creative freedom to do something really cool with it