[karmakaze]

First thing that comes to my mind is the procedural generation in Rescue on Fractalus! (Behind Jaggi Lines) 1984 by LucasFilm Games which blew my mind on Atari 6502.