算法用于在瓷砖地图上查找最接近的对象

Question

我有一个游戏地图，表示为瓷砖地图。目前，地图上存在两种类型的对象，与此问题相关：可收集的资源（树木，岩石等）以及玩家建造的建筑物。建筑物也通过道路连接。

我必须搞清楚一个高效的算法有问题，可以做到以下几点：

• 找到最近的资源，任何相关的建筑物（即找到最近的树的樵夫/树采集）
• 找到最接近的相关建设任何建筑（即找到最近的存储任何锯木厂）

我分开这两个问题，因为第一个不需要道路，但是第二一个应该是只有使用道路。

所以，这应该是一个单一的路径到一个单一的对象，这是最接近我从中找出它。然后，路径被工人用来收集资源并将其带回，或者说，从锯木厂选取资源并将其带到最近的存储区。

我知道如何获得最接近的路径本身（A *，Djikstra甚至是Floyd-Warshall），但我不确定如何以最佳方式处理这些路径的倍数并获得最佳/最接近的路径，特别是如果它是将定期运行，地图对象集合（道路和建筑物）预计也会定期更新。

我在Unity3D/c＃中这样做，但我想这不是Unity3D相关的问题。

我该如何继续？

Answer 1

找到两个物体之间的地理距离是一个便宜的（快速）操作 - 您可以承担每次游戏打勾多次。如果该选项可用，请使用它。

通过利用诸如道路，轨道等地形特征找到最短路径是一个更为复杂的操作。正如你已经在你的文章中提到的那样，A *搜索算法可能是你最好的选择，但它很慢。

但是总体来说，你应该不需要太多运行它往往 - 只是计算路径每X秒（为X的某个值），使你的工人在接下来的几场比赛蜱下面这个计算的路径，直到你“刷新”它。您拥有的精度越高，对游戏环境更改的响应速度（例如路径中出现的障碍）越多，您使用的CPU时间就越多。

尝试不同数量的精确度，并找到一个可以提供相当高的精确度，但CPU时间不太昂贵的精确度。 （更新时间间隔纯粹取决于预计的呼叫次数，计算100名工作人员的路径显然比1更困难。）