maze solver in C++

Question

Я создал генератор лабиринтов, используя Depth First Search, который возвращает массив фунтов и пробелов, чтобы указать лабиринт. Пример:

char maze[height][width] = 
{ 
    "#########", 
    "# # #", 
    "# ### # #", 
    "# # # #", 
    "# # # ###", 
    "# # # #", 
    "# ### # #", 
    "# # #", 
    "#########", 
}; 

Агент всегда будет начинаться в верхнем левом углу (лабиринт [1] [1]) и выход в нижнем правом углу (лабиринт [7] [7]).

Я пытаюсь сделать решатель сейчас, используя глубину первого поиска.

Проблема в том, что я довольно новичок для программистов, поэтому мне трудно понять, как реализовать глубину первого поиска на C++, и у меня есть еще труднее реализовать ее для лабиринта.

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

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

EDIT: Я не хочу готового кода !!! Я хочу, чтобы вы помогли мне понять, как передать псевдокод на C++ для лабиринта!

Answer 1

Таким образом, основные операции с глубиной первого поиска является:

Это работает так же для любого произвольного графа, как для дерева. Дерево - это особый случай. Вы можете даже визуализировать лабиринт в виде дерева:

######### 
#123# # 
#4### # # 
#5# # # 
# # # ### 
# # # # 
# ### # # 
# # # 
######### 

Единственное различие между использованием этого алгоритма на дереве против произвольного графа является то, что оно неявно известно, какие узлы в дереве были посещены , из-за иерархической структуры дерева. При произвольном графе вы можете иметь структуру, как:

##### 
#187# 
#2#6# 
#345# 
##### 

И при рассмотрении узла восемь вы не хотите рассматривать узел один, как новое место для посещения.

С вашим лабиринтом один из способов запомнить, какие узлы были посещены, состоят в том, чтобы заполнить их '#', как только вы их встретите.

---

Я довольно много понял, как представлять позицию агента, как переместить его вокруг и такие, но моя проблема в основном в том, как использовать стек для отслеживания из которых помещает агента был. По тому, что я нашел в Google, некоторые сохраняют стек посещенных мест, но я никогда не понимал, когда удалять позиции из стека, это моя самая большая путаница.

Сам стек не используется для отслеживания того, места посещаются. Он только отслеживает текущий «путь», пройденный через лабиринт. Когда вы достигаете тупиковых узлов, удаляются из стека; Эти узлы должны оставаться отмеченными как посещенные, даже если они удалены из стека. Если удаление этих узлов также приводит к тому, что эти узлы будут «недоступны», ваш поиск может постоянно пытаться и повторять тупики.

Я рекомендую вам сначала вытащить несколько маленьких лабиринтов и пройти через них вручную, используя блок-схему выше. Это даст вам лучшее понимание алгоритма. Вот несколько примеров лабиринты:

Start at O, finish at X 

#### #####  #####  ##### 
#OX# #O X#  #O#X#  #O # 
#### #####  #####  # #X# 
          ##### 

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