在贴图上找到最近的对象的算法
本文关键字：最近 对象 算法 | 更新日期: 2023-09-27 18:17:48
我有一个用贴图表示的游戏地图。目前，地图上有两种与这个问题相关的对象:可收集资源(树、岩石等)和玩家建造的建筑。建筑物也由道路连接。
我有一个问题，找出一个有效的算法，可以做以下事情:
- 找到离任何相关建筑最近的资源(例如:找到离伐木工人/采集者最近的树)
- 找到离任何建筑物最近的相关建筑物(即。找到离锯木厂最近的仓库)
我把这两个问题分开，因为第一个不需要道路，而第二个应该只有使用道路。
因此，结果应该是通向一个对象的单一路径，这是最接近我要找到的那个对象的路径。然后，工人使用该路径收集资源并将其带回来，或者让我们说，从锯木厂取出资源并将其带到最近的存储。
我知道如何获得最近的路径本身(A*， Djikstra甚至Floyd-Warshall)，但我不确定如何最佳地处理这些并获得最佳/最接近的路径，特别是如果它将经常运行并且地图对象集合(道路和建筑物)预计也会定期变化。
我在Unity3D/c#中这样做，但我想这不是真正的Unity3D相关的问题。
我该怎么做?
查找两个对象之间的地理距离是一种便宜(快速)的操作——你可以在每个游戏周期执行多次。如果该选项可用，请使用。
利用道路、轨道等地形特征寻找最短路径是一项复杂得多的操作。正如你已经在你的帖子中提到的，A*搜索算法可能是你最好的选择，但它相当慢。
但是一般来说，你应该不需要太频繁地运行——只需要每X秒计算一次路径(对于某些X值)，并让你的worker在接下来的几个游戏时间里沿着这个计算路径运行，直到你"刷新"它。你的精确度越高，对游戏环境变化的响应能力越强(例如，在你的路径上出现障碍)，你使用的CPU时间就越多。
尝试不同数量的精度，并找到一个提供体面的精度，而不是太昂贵的CPU时间。(更新间隔完全取决于您期望拨打的电话数量。计算100个工人的路径显然比计算1个工人的路径要困难得多。