как создать лабиринт, используя двоичное матричное представление?

Я предполагаю создать лабиринт, используя двоичную матрицу, когда 0 представляет собой пустую ячейку, а 1 - стену.

Я попытался использовать алгоритм DFS, проблема в том, что DFS относится к ячейкам и стенам между ними (каждая ячейка имеет не более четырех стен)

" затем выбирает случайную соседнюю ячейку, которая еще не была посещена. Компьютер удаляет "стену" между двумя ячейками и.."

Я не понимаю аналогии с представлением, которое меня попросили реализовать

у кого-нибудь есть идеи?


binary matrix depth-first-search maze
person tit    schedule 28.11.2015    source источник
comment
Можете ли вы опубликовать то, что у вас есть до сих пор?   -  person wogsland    schedule 28.11.2015
comment
Я абсолютно в начале, у меня есть интерфейс Maze3dGenerator, и я работаю над конкретными классами для его реализации, у меня есть класс maze3d   -  person tit    schedule 28.11.2015
comment
который содержит трехмерный двоичный массив, я как бы застрял в понимании аналогии   -  person tit    schedule 28.11.2015

Ответы (2)


arrow_upward
1
arrow_downward

Когда меня попросили сделать сетку, я бы начал с создания многомерного массива. Пусть внешний массив содержит каждую строку вашей сетки, а каждый вложенный массив - столбцы. В зависимости от того, должна ли каждая ячейка помнить о посещении, каждый слот массива может содержать простой класс или структуру (в зависимости от выбранного вами языка). В противном случае они могут просто содержать int или bool.

Простым примером может быть:

var grid = [
              [1, 1, 1],
              [1, 0, 1],
              [1, 1, 1]
           ];

Представляя собой пустую ячейку посередине, окруженную стенами.

person smithii    schedule 17.02.2017

arrow_upward
0
arrow_downward

Идея состоит в том, чтобы построить шаблон ячеек, а затем построить стену между ними, но не тогда, когда у нее есть ребро дерева DFS.

Пример запуска DFS (двухмерный случай, ребро удалено, можно вывести из порядка узлов):

 O

 O
 O

 O
OO

OO
OO
(this branch is stuck so start a new one)
OOO
OO
...
OOO
OOO
OOO

Теперь постройте лабиринт:

OXSOO
OXOXO
OOOXO
XXXXO
EOOOO

O -> cell
X -> wall
S -> start
E -> end

Стена может быть как блоком, так и просто плоскостью, топология одинаковая.

person Kh40tiK    schedule 17.02.2017