Структура данных для представления лабиринта

Будет ли лабиринт прямоугольной сеткой? Что-то еще?

Это также зависит от того, какая часть карты будет содержать полезную информацию (проходы или объекты).

Если это прямоугольная сетка и большинство квадратов сетки будут содержать что-то, хорошей структурой данных является двумерный массив (массив массивов), с каждым элементом массива, представляющим 1 строку, каждый элемент внутренних массивов, представляющих 1 ячейку в этой строке, которая является объектом, содержащим данные, относящиеся к этой ячейке (которая является соседней ячейкой). ячейки можно перемещать в то, что содержит ячейка, есть ли на ней символ).

Однако, если лабиринт не является прямоугольником, или если большинство ячеек в большом лабиринте на самом деле не содержат полезных элементов (например, являются непроходимыми блоками), хорошей структурой данных является граф.

Каждая вершина графа является проходимой ячейкой. Ребра представляют собой пары ячеек, между которыми вы можете перемещаться (вы можете сделать его ориентированным графом, если некоторые двери являются только односторонними). Каждая вершина / ячейка является объект, содержащий информацию об этой ячейке (например, ее местоположение в физическом лабиринте, который нужно нарисовать, и т. д...).

Преимущество структуры массива массивов заключается в том, что ее очень легко нарисовать и довольно прямолинейно обработать (любое движение-это просто вход/выход индекса). Добавление / удаление стенок так же просто, как изменение данных в элементах массива 2 соседних ячеек.

Преимущество структуры графа состоит в том, что он занимает намного меньше места, если проходы лабиринта очень разрежены (например, только 1/100 от field is passes); это единственная структура, которая может представлять случайную (например, непрямоугольную сетку) геометрию, и обработка довольно проста. Добавление / удаление стенок легко, так как это просто добавление ребра к графику.