Как мне начать делать лабиринт с кратчайшим путем из матрицы лабиринта в Java?

Question

Поэтому я хотел бы создать лабиринт с кратчайшим путем, который решает лабиринт. Лабиринт похож на это:

Мои лабиринты всегда будут окружены стеной. Кроме того, @ это стены, если вы не можете сказать.

@@@@@@@@
@   S@ @
@@@ @@E@
@   @  @
@@@   @@
@@@@@@@@

Где S - начало, а E - конец.

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

1. Проверьте текущую позицию (которая начинается в начале). Если это E, вернуть "путь" <- который...? Иначе, отметьте текущую позицию как посещенную и каким-то образом отметьте, с какой позиции она пришла...
2. Поставьте в очередь все текущие позиции соседей, которые не являются стенами и еще не посещены.
3. Повторите номер 1 для всех соседей и поставьте в очередь всех соседей соседей.

... Я в замешательстве, пожалуйста, помогите. У меня есть класс, который содержит координаты x и y как начала, так и конца, а также char[][] фактического лабиринта. Также я пытаюсь распечатать решенную версию лабиринта. То есть замените позиции кратчайшего пути чем-то вроде точки. Любая помощь с благодарностью.

Answer 1

Один из наиболее широко используемых и эффективных алгоритмов поиска путей - это алгоритм поиска путей A*. Хотя он, вероятно, является излишним для ваших потребностей, он часто используется в играх и других формах информатики и масштабируется в соответствии с вашими потребностями.

Answer 2

Я сделал это с помощью Java и алгоритма A-star около 7 лет назад, когда я учился в университете. Насколько я помню, эта статья очень пригодилась во время моих исследований. Вы можете скачать код и посмотреть, есть ли что-нибудь, из чего можно поучиться. Извините, я не могу помочь, я некоторое время не пользовался Java

Answer 3

Вы можете начать с рассмотрения этой реализации, которая очень похожа на фактическое определение проблемы. Вы должны начать с определения класса, который "интерпретирует" информацию из лабиринта char[][]. Методы, которые вы должны реализовать (как минимум): getStartPosition(), getGoalPosition(), getValidMovementsFrom(position). Эти методы позволяют вам перемещаться по карте, получая все пустые соседние плитки из конкретной позиции. Затем вы можете использовать любой подходящий алгоритм (BFS, DFS, Dijkstra, A*), чтобы решить его с помощью сторонней библиотеки или собственной реализации.

Вас может заинтересовать этот полный пример проблемы с использованием A * с библиотекой Hipster для Java.