I tried to come up with an idea how to actually do this in a 2d tilebased game. I think you could modify Tiles in a way that turned some tiles into a shelter, instead of just building a shelter-tile. So instead of building the shelter you'd build protection from rain, protection from groundmoisture, protecture from insects, etc. You'd just build up all the protection you need around you, but in a logical way. for example using leaves for a roof would provide some protection from rain, but building your whole shelter in a cave or under a tree would be even better. So you'd kinda expand the natural landscape to fit your needs. So you're probably better off buidling a fire in a cave than starting to chopping down trees to build a small lean-to shelter.
One thing I would love to see in a game is having to actually design/build your shelters and possibly tools. Not "You have collected 10 sticks, and 50 palm leaves, now you may build a lean-too, aka Shelter_Level_1", but "I have collected a number of procedurally generated branches, now let me play with a physics engine of some kind and actually put something together using the natural landscape".
I still have difficulties trying to think of ways to expand gameplay in an intesting way. What happens when you have a shelter and maybe a way to get all the food you need? I would appreciate some input on that as well