Помощь в решении лабиринта D & D с использованием Java

Question

Я читал некоторые другие вопросы, которые были размещены на stackoverflow, и я немного ошеломлен количеством алгоритмов поиска. Я не ищу код и больше страницы, которая выходит за рамки алгоритма и, возможно, некоторый код sudo. Я знаю, что есть алгоритмы, подобные A *, но из-за нехватки времени я не знаю, смогу ли я завершить программу этим алгоритмом. Лабиринт создается с помощью серверной программы, и решатель подключается к серверу, чтобы посылать команды большему количеству игроков. У меня нет доступа к методам внутри серверной программы. Я должен решить лабиринт, который был создан, чтобы быть как лабиринт D & D. Вот основной обзор игры:

Классическая компьютерная игра D & D состоит из подземелья (лабиринта), где Цель игры - пробраться через подземелье, войдя в на «входе» в лабиринт и выход на его «выходе». Делать вещи более сложные, макет подземелья не известен априори и есть препятствия (зомби, ямы и двери), которые должны быть преодолены с помощью объектов (тарифы, лестницы и ключи), которые найдено по пути.

Я заметил, что многим другим постам не нужно беспокоиться о препятствиях для завершения лабиринта, будет ли это серьезной проблемой для адаптации алгоритма для компенсации препятствий? Мне было интересно, если что-то вроде правила правой руки будет хорошо для решения лабиринта, и если нет, то каким будет алгоритм, который настолько прост, насколько это возможно для решения лабиринта (из-за того, что я должен завершить программу в ближайшее время). Любые другие ссылки были бы хороши, так как я знаю, что мне нужно завершить эту программу снова в Objective-C, и я хотел бы реализовать что-то более мощное, чем правило правой руки, когда это произойдет. Спасибо за любую помощь.

Answer 1

хорошо для простых лабиринтов, вы в основном "идете" по тропинке, пока не доберетесь до перекрестка. В этот момент вы записываете все ваши варианты. Затем вы выбираете один (используя любую эвристику, которая вам нравится, для техники правой руки вы всегда «идете направо»). Как только вы записали параметры, вы помещаете их в стек. Затем вы продолжаете вперед.

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

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

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

Он определенно не скажет вам оптимальный путь или лучший путь подсчета очков, он просто приведет вас к выходу, когда вы наткнетесь на него.

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

Так что, если вы столкнетесь с вампиром, это будет узел без выходов в конце зала. Позже, когда вы получите распятие и деревянный кол, вы «узнаете», где находится вампир, и сможете пересечь график обратно к вампиру (конечно, при условии, что он не движется).

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

Но для обхода простого лабиринта техника стека работает очень хорошо.

Приложения:

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

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

Это просто поиск в глубину дерева, для которого вы еще не знаете макет. Но также важно, чтобы вы также отслеживали, где вы были другим способом. Например, если ваш лабиринт представлен в виде большого массива элементов пола и стен, вы можете записать координаты каждого элемента пола, который вы ввели в простой список.

Причина этого в том, что если в лабиринте есть циклы, вы не хотите «идти вперед» по тем пространствам, по которым вы уже шли. Очевидно, что вы должны сделать это при возврате. Но при изучении нужно знать, что у тебя есть, а что нет. Как вы отследите, что зависит от структуры данных вашей карты.

Рассмотрим этот тривиальный лабиринт:

# ########
# ########
# # #    #
# # #### #
# #a    b#
# # #### #
#   #    #
##### ####
#    c   #
# ########

Вы можете видеть, что вам нужно вставлять в стек только в точках a, b и c. Если вы можете пометить пол, на котором вы были, ваша карта может выглядеть так на первом перекрестке:

#.########
#.########
#.# #    #
#.# #### #
#.#a    b#
#.#.#### #
#. .#    #
##### ####
#    c   #
# ########

И ваш стек будет выглядеть так:

{d,d,d,d,d,d,d,l,u}

Для 7 падений, одного влево и одного вверх.

Если вы не можете пометить карту, вы можете вместо этого отслеживать координаты.Все зависит.

Answer 2

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

  public static int recursion(int x, int y) {
    if (location == end) {
      return 0; //found the end
    }
    if (deadEnd) {
      //backtrack
    }
    if (trapName) {
      //put whatever you need to do to get around it
    }
    if (x+1 <= edge) {
      recursion(x+1,y); //Moves right
    }
  }

Это более или менее псевдокод. Надеюсь, это поможет, хотя!