[Taugeshtu]

Всё можно сделать чуточку проще. Представьте себе, что вам нужно сделать кольчугу из квадратиков. Причём базовый элемент кольчуги должен быть одинаковый. Что мы сделаем? Правильно, сделаем элемент, который имеет соединения типа "папа" с, допустим, нижней и правой стороны, и "мама" с верхней и левой. И тогда можно строить какие угодно кольчуги.

Тот же принцип и здесь:
чтобы не было повторяющихся стенок, храним информацию только о 2х из 4х стенок - информацию о двух других стенках в любом случае содержат наши "соседи". С точки зрения хранения инфы это всего 2 бита инфы для ячейки, + если для хранения одной ячейки используется 1 байт, у тебя остаётся ещё 6 бит на описание того, что находится в ячейке.

Из потенциальной проблемы только границы уровня, но тут либо делать их всегда закрытыми, либо добавлять ещё по ряду "лишних" клеток с незаписываемых сторон лабиринта.

В аттаче помалевал поверх лабиринта его "схему" - зелёные линии получились там, где нижняя стенка, синие - где правая, белые уголки - где обе хранимые стенки. Думаю, понятно вышло...

UPD.
В принципе получается, что "стеночный" лабиринт вдвое больше по количеству информации, чем его "блочный" собрат.

Что касается формы хранения и обработки - 2 бита на стенки, 6 на содержимое должно хватить (2^6 = 64 разных состояния клетки, или 63 айтема + пустая клетка), во время перемещения персонажа я бы держал в памяти для удобства массивчик Surround 3х3, в котором хранил бы возможность перейти в соседнюю клетку из текущей. ЧТобы просчитать Surround-карту достаточно точечно (считай - без вложенного цикла) взять 8 позиций из карты лабиринта (не нужно брать нижнюю правую клетку, т.к. её данные ни на что не повлияют) если персонаж может гулять по диагонали, или вообще 3, если не может (левее, выше, и прямо где персонаж).