I have done 90% of my development for 20kAtm using test levels made by hand, which is kinda ridiculous for a procedural dungeon crawler. But hey, better later than never, I now have a fully procedural world generator and here's what it looks like in the radar and with the zoomed-out mode, to find your bearings:

In 20kAtm you explore little islands of a world with incredibly high air density, making this exploration impossible outside of the machinery you are piloting.
It's a dungeon crawler at heart, but you don't move up and down a dungeon or a tower, instead you travel from island to island.
The issue I had here, was that the usual technique for generating random dungeons is grid-based and it looked too blocky on the radar, and initially it looked like crap:


Instead, I went for another approach, with connected lines and points, in order to get cleaner shapes and resemble small towns on top of an island (an island with killing turrets and creepy creatures, of course).

For the fellow developers, the algorithm to generate the islands is divided in three main stages:
1) Generate a voronoi field, they are interconnected cells with random shapes.
2) Because they form topological connections, I can start from a cell in the center and grow a perimeter until I have a nice looking island shaped thing (and by the way, I gotta thank @ThePrimalAce  for the tip on this one).
3) Now that I have a perimeter, I just take all the contained cells and shrink them down to form roads and buildings, all without risking dead zones.

The rest is just up to the requirements of the game design which are quickly ramping up, but for now I just need precomputed spawn points for the enemies,  and there are some walled up areas that require finding a key first to be opened.
Here are some examples of islands wit different voronoi scales: 

Bigger islands are of course meant for latter stages of the game, as exploring even a tiny one can be problematic initially if you don't know how to keep a nuticrawl in check ; )

Also, the nice thing of having a sci-fi setting and an on-board log-monitor, is that you can do all this environment processing, while telling the player that the computer is actually scanning the environment, which is pretty honest I'd say.


As for the story side of this story-driven procedural game, I wanted to do something a bit more involved than just: explore, loot, find the amulet, end of the game.
I think the challenges of a procedural game trying to tell a story, are about how you justify this ever-shifting experience to the player, and how you make progress in a story that restarts from scratch each time.

Ever seen Groundhog Day? It's a roguelike movie.

In 20kAtm you are a thief, a rogue who stole a machinery meant for the nobles, and as such, you have no idea how to pilot or control this clunky thing.
On each play you are a new person, stealing a different nauti-crawl somewhere else, the only difference is the knowledge of the machine and the story elements you've gained from the previous play. 
At every new attempt there will be messages intercepted by the computer, revealing parts of the story, but also guiding the player more and more after each death, to avoid total frustration. The nauticrawl has many secrets but they won't be revealed all at once.

As for the main reason why the player explores these islands, it is something too spoiley to tell,  and the same goes for the system used to move from one island to another.
Suffice to say I'm working on a whole new room of the nauticrawl, with even more controls and challenges, but this time they are not meant for land exploration.

Thanks for reading along!