Minecraft kind of started it. Maybe Roguelikes such as Nethack? They certainly had the survival elements, although were much more brutal. That's as close as I've ever seen that could be comparable to Minecraft or survival sandbox games prior to Minecraft itself. It feels like if it did exist, it would be known by a Euro gamer; all the crazy cool complex games from really early days of gaming I have found were made in and popular in Europe, but didn't see much action here in the states.