(Game initially released in Early Access on 2013, went out of Early Access on 2016.)
I actually feel bad for not playing this game as much as I want to whilst still including it on this list. But the reality is, Starbound is more than just “Terraria in space”. It’s a perfect example of offering a vast, procedurally-generated universe while at the same time still including some worthwhile gameplay elements while you’re out exploring on a planet you’ve just landed.
Also, the game has its own tilde.town server. Pretty cool, right? Hop onto #starbound on the internal IRC for more info!