Rescue: The Beagles (2008)
In 2008, the game development forum TIGSource had a procedural generation contest. Several interesting projects came out of that, but the winner was Rescue: The Beagles, a game by Nenad Jalsovec about rescuing beagles from animal testing.
It uses its height map generation and object placement to cleverly create lots of little action movement puzzles. While it’s gameplay language draws from the long history of arcade games, it creates its tight action spaces on the fly. The impressive thing here is not just that the levels are procedurally generated, its that they’re well designed levels. This flow grows out of the cooperation between the rules of the game and the construction of the level generator.