有效地确定集合的边界

Question

我正在使用游戏提供的 API 为 RTS 游戏编写 AI。我想做的一件事是确定一组包围敌国的线段，但是，游戏只提供了一个函数，可以告诉我单个 2D 领土点的 teamID。

对游戏 AI 的查询执行起来非常昂贵，因此我需要将查询数量保持在绝对最低限度，即使这意味着偶尔会得到质量稍差的答案。高估敌方领土面积也比低估敌方领土面积要好。

如何使用最少数量的查询有效地确定围绕空间非凸区域的一组边界线？

Nb：用 Lua 编写的答案加分，但伪代码也很好。

Answer 1

您可能正在寻找一组点周围的凸包，请参阅：http://en.wikipedia.org /wiki/Convex_hull

这是一个 O(n log n) 问题——计算起来还不错。对于一些伪代码，请参阅：http://en.wikipedia.org/wiki/Graham_scan

编辑：根据您澄清的问题，我知道这些区域不一定是凸的，因此凸包将为您提供比您想要的更广泛的区域。然而，它可能是您可以细化的起点（因为您正在寻找的最终非凸区域位于船体内部）。

更多编辑：如果您确实只有一个查询单个点的函数，那么您的问题与矢量化位图图像相同。每个点都是一个“像素”，敌人区域是“像素”的（近似）矢量化。

Answer 2

我假设您可以在领土内的空间中找到一个点。称之为 Z。（因为你有几个城市，你可以选择一个平均城市位置作为中心位置。）

给定起点 Z，我会考虑做的是从该点向外生成一组光线，每条光线大小有下限和上限，并且集合的数量不断增加以获取详细信息。我在下面画了一个方案。没有任何内容经过测试；请随时提出改进建议。

每条射线都由角度 Theta 表示，并具有原点 Z。每条射线不是只有一个长度，而是有两个相关的长度：内部和外部，我们将尝试将其收敛。 Inside 的初始值设置为 0，outside 的初始值设置为大于任何可能区域的半径（“地平线”）；我们将使用二分搜索（游戏空间直径的 log2 N）缩小 Outside 直到它位于区域内，并增大 Inside 直到它不完全超出区域。我们还将随着端点的展开而增加光线数量，以获取区域边界细节。最终结果应该是一组光线，它们在区域周围建立了边界，其端点之间的距离不超过“间距”。

您可以仅从一条射线开始（theta=North(0)、Inside=0、Outside=Horizo​​n）。
我们将光线集称为 R。我们假设光线集 R 按 theta 排序，
如果我们有来自 R 的射线 r，则 next(r) 是排序集中的下一条射线，
其中 R 中最后一条射线的 next(r) 是集合中的第一条射线。自从
如果您知道城市位置，则可以使用以城市作为内部点的光线来播种该集合。
无论哪种方式都应该有效。

附加参数“阈值”为您提供答案的精确度。

R = empty
add_to_R(0,0,Horizon)
repeat until done
    done = true
     for each ray r in R
      guess = average(Inside(r),Outside(r))
      if guess>threshold
         then done = false
      if interritory(Z+(Theta(r),guess))
        then Inside(r)=guess
        else Outside(r)=guess
     for each ray r in R
       if (distance(Inside(r),Inside(next(r)))> spacing
          then add_to_R(average(Theta(r),Theta(next(r)),
                        min(Inside(r),Inside(next(r)),
                        max(Outside(r),Outside(next(r))
end

运行成本应该是最大区域直径的 log 2，乘数与区域的周长除以所选的射线端点间距有关。

这个方案并不完美；如果射线碰巧穿过的领土上存在半岛，则如果不在半岛内进行采样，它将失败。如果半岛任意薄，就需要任意多个样本才能发现它们。您也许可以选择半岛最小宽度，然后在最终找到收敛射线时调整算法以半岛宽度向外步进，以确保它没有出错。

Answer 3

我建议您使用蒙特卡洛方法

http://en.wikipedia.org/wiki/Monte_Carlo_method

从一组已知点开始应该能够根据您的目标知识和初始点的结果（作为起始城市的集合）改进额外的“随机”猜测

我可能会考虑尝试类似于等势的东西已知点之间的线，按点的假定大小加权。不过，早期被错误地认为附属的岛屿将极大地影响这些猜测……需要更多的思考。

编辑：

所以我和一位朋友进行了交谈，他进行地图分析，以从卫星/航空图像中定位特定植被的跨度...与这个问题有些相关，因为她尝试在自己查看地图之前自动定位斑块。

她说，典型的方法是应用网格图案，该图案可以细分整个区域，并在发现特定图案时在其内部缩小。因此，您将对常规网格进行采样（设计此网格可能包括您正在寻找的尺寸的一些知识），如果您得到了命中，则在该区域进行更多采样...如果没有，则偏移您的网格并重新-样本。

这种方法的优化取决于人类对搜索模式的了解。例如，您可以根据尺寸/形状的常见期望指定搜索网格中的细分数量。