Если northWall[i][j] равно 1, то это означает, что ячейка [i,j] имеет сплошную стену сверху; в противном случае данная стена отсутствует. Нулевая строка является фиктивной строкой из ячеек, находящихся под лабиринтом, причем ее северные стены формируют нижний край лабиринта. Подобным же образом посредством eastWall[i][0] задаются любые проходы на левом краю лабиринта.
Создание лабиринта. Задайте сначала все стены сплошными, так чтобы лабиринт имел вид простой сетки из горизонтальных и вертикальных прямых линий. Программа нарисует эту сетку. Затем в произвольно выбранную ячейку помещается некая невидимая «мышь», чья работа заключается в том, чтобы «прогрызать» стены для соединения смежных ячеек. Эта мышь проверяет четыре соседних ячейки (верхнюю, нижнюю, левую и правую) и для каждой из них выясняет, все ли четыре стены у нее сплошные. Если это не так, то данный элемент ранее уже посещался и, следовательно, уже находится на каком-то пути. Может случиться так, что мышь найдет несколько вариантов ячеек, которые еще не посещались. Она выбирает одну из них случайным образом и прогрызает стену, соединяющую ее с этим элементом, а координаты других вариантов записываются в стек. Прогрызенная стена стирается, а мышь повторяет указанный процесс. Когда мышь попадает в тупик - в окружение посещенных ячеек, - она выталкивает из стека непосещенную ячейку и продолжает свое дело. Если стек пуст, то все ячейки лабиринта уже посещены. «Начальная» и «конечная» ячейки выбираются произвольно, наиболее вероятно на одном краю лабиринта. Очень интересно следить за динамикой создаваемого лабиринта, когда мышь прогрызает его стены. (Вопрос: Не лучше ли для записи вариантов ячеек использовать очередь (queue) вместо стека? Как это повлияет на порядок, в котором создаются последующие пути?)
2.7. Дополнительная литература Работа с лабиринтом. Для прохождения лабиринта мы использовали алгоритм с отходом («Ьаск-tracking» algorithm - «поиск с возвратом»). На каждом шаге мышь пытается двигаться в случайном направлении. Если стена отсутствует, мышь записывает ее координаты в стек и перемещается в следующую ячейку. Ячейку, где находится мышь, можно отметить красной точкой. Когда мышь попадает в тупик, она может изменить цвет ячейки на синий и вернуться назад, вытолкнув данные из стека. Мышь может даже построить стену, чтобы больше никогда не пытаться пройти в тупиковую ячейку.