алгоритм, используемый для поиска ближайшего объекта на карте плитки

Question

У меня есть карта игры, представленная в виде карты плитки. В настоящее время на карте присутствуют два типа объектов, относящихся к этой проблеме: gatherable resources (деревья, камни и т. Д.) И здания, построенные игроком. Здания также связаны дорогами.

У меня есть проблема, выясняя эффективный алгоритм, который мог бы сделать следующее:

• найти ближайший ресурс любого соответствующее зданию (т. Е найти ближайшее дерево к Дровосек/дерево-собирателю)
• найти ближайшее релевантное здание любого здания (то есть. найти ближайшее хранение в любую пилораму)

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

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

Я знаю, как получить самый близкий путь (A *, Djikstra или даже Floyd-Warshall), но я не уверен, как оптимально перейти к кратким результатам и получить лучший/самый близкий, особенно если это будет проводиться очень регулярно, и ожидается, что коллекции объектов карты (дороги и здания) будут меняться регулярно.

Я делаю это в Unity3D/C#, но я думаю, что это не проблема, связанная с Unity3D.

Как я могу продолжить?

Answer 1

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

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

Но в целом, вы должны не нужны запускать его слишком часто - просто вычислить тракт каждые Х секунды (при некотором значении X), и сделать свой рабочий не тратить следующую несколько игры клещ после этого вычисленного пути, до тех пор, вы «обновляете» его. Чем больше у вас точность и чем больше реагирует на изменения в игровой среде (например, препятствия, возникающие на вашем пути), тем больше процессорного времени вы будете использовать.

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