Elite was the first game to utilize procedural generation, which has been extremely popular across multiple genres.

en.wikipedia.org/wiki/Elite_(video_game)

guinnessworldrecords.com/…/first-use-of-procedura…

While some might not consider it a game mechanic I certainly do, as gaming the proceduraly created levels is a core part of certain games, see mapping tactics in Diablo 2 for example as you use knowledge of procedural generation to reduce the time to find and kill bosses.