Hunter was an early sandbox game on the Amiga and was quite good back in the day. Mercenary series too. Daggerfall was/is a huge sandbox rpg. Minecraft was the first to capture the lego style creativity though. Dwarf fortress is probably the closest to Minecraft.

Survival games existed before Minecraft but in a very different form.

Survival Kids is a konami series of games that started on the GBC and went on to have 3 more episodes on the DS, where the premise is always “you’re stranded on an island and must find a way to be rescued”, but unlike modern survival games, the world is custom built and the evolution of the plot is usually pre-determined, with maybe some branching but nothing extremely dynamic. You also couldn’t alter the game world in any significant way beyond what was already expected, such as building bridges in predetermined spaces and so on.

It has some hallmarks of the later versions of the genre, like an emphasis on crafting and needs management such as hunger and thirst, so the connection is definitely there.

The technology wasn’t ready.

Minecraft was groundbreaking in optimizing the handling of destructible maps. This was during a time where every other game were trying to do realistic graphics. Using blocks or voxels was considered silly because it couldn’t ever look realistic. The game Delta Force used voxels for the landscape and even if it looked nice for that, it also showed that the use of voxels was not ideal for detailed realistic graphics.

Destructible landscape was used in 2d games like Worms, but that was basically just a bitmap image, so it didn’t require much memory to keep track of the limited map size. Minecrafts map is theoretically infinite, and while some other games also had chunk loading, it was new that the game was able to save the precise state of all the unloaded chunks. The magic is that the game only saves changes that are made. The rest of the map is procedurally generated, so it doesn’t have to save everything. It can just recalculate the map and apply the changes. No other game did this.

Gameplay wise, the survival game Stranded was close but it was limited by using ordinary polygon graphics, so while it had crafting and some mining (gathering materials), the map itself was not destructible. It also had a storyline so it wasn’t as much of a sandbox game.

So basically, Minecraft combined a lot of different technologies to make it possible and it was only possible because the graphics were grossly simplified. It started as a hobby project and I doubt that any AAA publisher would have funded it at the time, because the idea of block voxels was so far out.

There was Wurm online which was a complicated messy sandbox MMO. I also remember plenty of physics and combat sandboxes in the Flash space. Sim City was a city builder sandbox. As for block building sandboxes there was Infiniminer.

As for survival, many games have had survival elements. A core mechanic of roguelikes is something called a hunger clock. It doesn’t necessarily have to be food based but the idea is a game that is about exploration and conquest having a mechanic that limits exploration creating tension where you have to explore with purpose instead of meandering. Some MUDs might be able to be seen as precursors to massively multiplayer survival games like Rust.

I played the shit out of Garry’s Mod before Minecraft was a thing