массивы — решатель лабиринта в переполнении стека

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: я не хочу готовый код! Я хочу, чтобы вы помогли мне понять, как перенести псевдокод в C ++ для лабиринта!

-1

Решение

Итак, основная операция поиска в глубину:

Глубина первой поисковой схемы

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

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

дерево

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

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

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

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


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

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


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

Start at O, finish at X

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

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

2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector