Как пройти лабиринт программно, когда вы попали в тупик

Question

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

Answer 1

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

Answer 2

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

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

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

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

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

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

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

Answer 3

Эрик Липперт написал серию статей о создании реализации C # A * , что может быть более эффективным.