algorithm - 在 RTS 中确定一组单位的方法

Question

寻找一种算法，用于确定在像星际争霸这样的实时战略游戏中作为一个小队一起移动的单位组。我目前关注的方向是一种聚类算法，但很难找到哪个算法最有效，因为单元作为一个整体在移动，而不仅仅是静止不动。任何帮助都会很棒。

Answer 1

K-means 不是最佳选择，因为它需要您指定希望找到的聚类数。那么有些可能包含单个对象。

我建议采用 DBSCAN。特别是通用版本 GDBSCAN。

为此，您需要定义一个单位的邻域构成 - 例如，2 范围内的任何其他单位属于同一玩家并大致朝同一方向移动(达到 x 和 y 速度的某个增量阈值)。

接下来，您需要指定何时考虑单位开始形成初始集群，称为“核心点”。假设至少有 3 个单位。

然后使用 DBSCAN 是非常基本的，应该会给你很好的结果。您需要稍微微调参数。像这个最小大小这样的东西显然是一个输入参数，并且取决于您的用例。邻域定义也是如此:您正在寻找向同一方向移动的群体，这些信息需要以某种方式放入算法中。使用 GDBSCAN，这很简单，只需调整邻域定义即可。