Red Faction, which was mostly taking place in underground mines, had generic deformable/destructible terrain reminiscent of Lemmings terrain, but 3D. It was artificially limited in some ways, otherwise you'd just drill your way straight to the level end (similarly to some Lemmings levels with unpiercable material).

Drilling through was not just a gimmick but actually part of the game, e.g instead of finding a key à la Doom/Descent, you'd have to detonate a rocket, a mine, or a grenade at walls near locked doors to create holes big enough to go around them (took me a surprisingly long time the first time to figure I was supposed to do that, especially as the level is intentionally deceptive as you have door with buttons/keys before).

There were also actual boring machines to help you drill through big time. You could make bridges fall into a chasm by blasting both ends. In enemy-crowded open areas you'd have to create your own cover by carving holes in walls or in the ground.

Trivia: Red Faction was initially due to be Descent 4 (as a prequel to Descent), but turned into a on-foot FPS in a different universe.

https://en.wikipedia.org/wiki/Red_Faction_(video_game)