2d поиск пути с несколькими возможными конечными точками?

Question

У меня в настоящее время есть другой вопрос , связанный с поиском пути в Java. Однако я чувствую, что это отдельный вопрос.

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

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

Answer 1

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

Однако это специальное поведение может привести к написанию собственной реализации A*. Это не много кода; может быть, день или два домашней работы для студента колледжа, IIRC.

Answer 2

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