There was a style of platformer popular in the 80s that used non-scrolling maps in a large 2D grid. eg. Saboteur 2, Montazuma's Revenge, Starquake, Below the Root, and to a lesser extent Impossible Mission. VVVVVV revived this style a few years ago. I loved that you didn't have to map these games to beat them, but it often helped. And the non-linear style tended to give the games surprising depth for something that wasn't procedurally generated. Can anyone recommend some others?