Android - Внутренние предложения по поиску путей

Question

В настоящее время я работаю над проектом поиска пути внутри помещений. Вы можете представить это так: введите описание изображения здесь

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

Есть ли у вас какие-либо предложения о том, как я могу сделать это для реализации алгоритма A * на Android, как показано на рисунке?

Answer 1

A * алгоритм опирается на теорию графов .

Итак, сначала вы должны построить свою комнату в виде графика (каждая комната / этаж - это вершина или узел, а каждая дверь - это ребро). Я предлагаю вам использовать известные реализации для этого ( здесь является примером).

Исходя из вашей схемы, ваш график должен выглядеть следующим образом

Сохраните HashMap (или что-то еще), чтобы отслеживать, какая комната сопоставлена ​​с каким узлом, а также какой коридор связан с каким краем.

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

List<Node> path = aStar.findPath();

Переназначить список узлов в список комнат и показать его вашему пользователю.

NB. Если вы хотите сделать его очень чистым, вы можете переписать AStar.java, чтобы принять список Room, и заставить его выплевывать другой список Room.