Если хранить "целиком" как массив, то каждый тайл удобней для экономии места кодировать полубайтом, это 16 вариантов. Так сделано в Lode Runner, причём там вообще 8 вариантов тайлов, насколько помню. Само собой, можно ещё и сжать каждый экран, вопрос во времени распаковки-упаковки обратно (раз планируется сохранение "истории действий" на карте при переходах по экранам).
Либо генерить программно, тут основная задача - подбор алгоритма построения, чтоб рисовалась вменяемая карта, а не хаос по RND. Грамотному алгоритму понадобятся лишь несколько байт, задающих генерацию всего экрана.
Местоположение итемов, врагов и прочее тоже можно генерить, хотя бы частично.