I think I need to start playing that game again...

Which one? Terraria or one of the Alien games?

Terraria. I really loved the game, but there was always a point where I simply didn't know what to do next, mostly because I didn't seem to really get any further improvements after a while, so even with the best equipment I could find and maxed out health, the bosses just squished me in a matter of seconds.

This may sound a bit crazy, but Kerbal Space Program may fit the bill for your. It's a different sort of exporation, survival and crafting, but I like it more than Terraria and Minecraft (and the like) b/c it rewards accomplishments instead of work. I find it boring to dig, but absolutely thrilling to perform a physics-based space feat. But overall, the games are similar in that you need to do something to parts, you use those parts to build, you build things to survive (or rescue).

You may also want to check out Sir, You Are Being Hunted. It was fair, I thought, but not great. I don't think there's any building involved, but survival and exploration and stealth are your main tools to survive. Also, the robots have a lot of spunk.

I'll 2nd this. It's my favorite a game here next to Terraria. Too bad it's so damn expensive.

Don't Starve takes the mechanics from Minecraft, and uses them to create a deep and original roguelike. But this is no building sandbox - while structures can be build, resources are scarce, and your focus will be on staying alive one more day.

The negative is that it can sometimes feel a bit dreadful:
it's raining and you're hungry and slightly insane. Now it's getting dark too. You don't have time to get back to you camp. You could build a temporary fire. You try chopping some firewood, but its raining, and you keep loosing the grip of your axe. Now its dark. You pull out your torch and stands under a tree to get cover from the rain. But your mind isn't what it should be, and these shadows seems to be moving ...

Still - great game! Really sucks you in.

Okay, there is Pixel Piracy, which let you build your ship using various blocks.

But this game have quite a few flaws:
- Due to really crappy coding, this game uses resources like crazy.
- Lotsa irritating quirps: Pop-up messages looks like its placeholders which never got finished, floating hud elements makes ship building and equiping your crew cucumbersome, etc.
- You will need to read online guides to figure out how some stuff works, or when and how the game saves your progress.

In addition if you're looking at the GOG version, it may be outdated according to a WIP thread of outdated and unsupported games on GOG. I got it from Humble Bundle DRM-free but I dunno how safe am I either.

That too? Maybe the devs gets Archivements for each new way their game screws up? :-P

Any news games ?

Starbound has been released by now but many people hate it because it arguably became worse in Early Access whilst Terraria has been getting more and more updates. Others like Starbound more.

Then there is modded Minetest and games based upon it (not on GOG but that doesn't matter because it's free and open-source software). I had some difficulties getting the mods to work earlier but with mods set up it is a very good alternative to Minecraft.

I assume you tried Craft the World?

The screenshots don't look half bad, I might check it out myself.

It has one hell of a learning curve. Good for you, I'm always in here so don't hesitate to ask for help. :P