高效确定一个集合的边界

Question

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

向游戏AI查询的成本非常昂贵，因此我需要尽可能地减少查询次数，即使这意味着偶尔得到稍差一些的答案也可以。过高估计敌方领土的面积要比低估它好。

如何有效地确定一组边界线，在非凸空间周围，使用最少的查询次数？

注：用Lua编写答案会获得额外加分，但伪代码也可以。

- Martin

---

领土可以是任何多边形吗？还是它们只能用特定形状的瓦片来表示？您是否有任何关于如何开始查找或者只是查询一个有限的二维空间的信息？ - Matthew

它们可以是任何形状。在此处查看默认地图上大陆的轮廓：http://store.introversion.co.uk/images/screen_shots/defcon_screen1.jpg - Martin

你有其他资源吗？比如敌方领土的总面积？或者扩张规则？ - Matthew

可能存在孤岛，实际上这些孤岛上可能没有敌方城市，这使得城市成为一个不好的起点。但现在我们可以忽略这一点。如果我必须使用一些猜测来定位领土内的第一个点，那也没关系。除了知道一个点是否在领土内，我没有其他资源。 - Martin

@Matthew PK: Defcon (introversion.co.uk/defcon)，你可以在这里关注我（偶尔）开发的机器人的进展，github地址是github.com/martindevans/Joshua-Bot。 - Martin

Answer 1

您可能正在寻找一组点周围的凸包，参见: http://en.wikipedia.org/wiki/Convex_hull 这是一个O(n log n)问题 - 计算上不太糟糕。有关伪代码，请参见：http://en.wikipedia.org/wiki/Graham_scan 编辑：根据您澄清的问题，我了解到区域不一定是凸的，因此凸包将给您比您要寻找的更广泛的区域。然而，它可能是一个起点（因为最终，您要寻找的非凸区域在外壳内），您可以对其进行改进。

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

- payne

---

抱歉，在我的回答中我说了非凸，我想说的是非凹。敌方领土绝对不是凸包。此外，我不确定标准凸包算法是否适用，因为它们假定点的访问成本很低，而对我来说，真正的问题是确定查询哪些（最少数量的）点。 - Martin

OP 不是在寻找如何找到凸包，他正在寻找多边形边界点的最佳定位方式。 - Matthew

嗯，凸包确实是找到边界点（即多边形）位置的最佳方法，但他澄清了它不一定是凸的。这使得它更有趣。嗯嗯 <思考中>。 - payne

我同意凸包可能是一个很好的起点。但我不认为我能以高效的方式确定凸包。像 Graham Scan 这样的算法会寻找具有最大 y 坐标的点，然后分类所有点，直到找到具有最大 x 坐标的点等等。由于点位于实空间中，对我来说有无限多的点需要查询！我需要一种算法，不仅可以从点集中确定凹壳，还可以确定生成这些点的最佳查询位置。 - Martin

凸包可能是最小化搜索区域以定位领土实际边界的良好起点，但在这种情况下不起作用。凸包计算涉及一组已知点。手头的任务是通过有根据的猜测来优化地定位边界。 - Matthew

Answer 2

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

给定起点Z，我考虑生成一组从该点向外的光线，每个光线具有较小和较大的大小范围，并且随着数量的增加而增长以获得详细信息。我下面草拟了一个方案。尚未测试任何内容；随时提出建议。

每个光线由角度Theta表示，并具有原点Z。每个光线不是一个长度，而是具有两个相关的长度：Inside和Outside，我们将尝试使其收敛。Inside的初始值设置为0，外部设置为比可能的领土半径更大的值（“Horizon”）；我们将缩小Outside，直到它在领土内部，并增加Inside，直到它不完全在领土外部，使用二进制搜索（log2 N是游戏空间的直径）。当端点扩散以获取领土边界细节时，我们还将增加光线的数量。最终结果应该是一组光线，它们在距离“spacing”不超过一定距离的情况下建立了领土边界的范围。

你可以从一个光线（theta=North(0)，Inside=0，Outside=Horizon）开始。我们称这组光线为R。我们假设光线集R按theta排序，如果我们有来自R的光线r，则next(r)是排序集中的下一个光线，其中最后一个光线的next(r)是集合中的第一个光线。由于你知道城市位置，你可以使用城市作为Inside点来种植光线集。它应该任何一种方式都可以。

另外一个参数“threshold”为您提供答案的精度程度。

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

在你的最大领地直径范围内，运行成本应该是log2，乘数与领地周长和所选射线端点间距有关。这个方案并不完美；如果射线没有在半岛内取样，它将无法运行。如果半岛非常窄，则需要采集大量样本才能发现它们。或许你可以选择一个半岛最小宽度，并调整算法以确保当它最终找到收敛的射线时向外步进半岛宽度，以确保没有出错。

- Ira Baxter

---

我自己想出并实现了一个类似这样的方案。它运行得相当不错，我开始怀疑它可能是最佳解决方案！ - Martin

我想到另一种方法是在图形世界中所谓的“洪水填充”不规则形状。我没有查看过，当然可以逐像素地进行填充，但使用越来越大的矩形（例如，在上次成功洪水点附近每次尝试时加倍）作为样本进行填充是有意义的。 - Ira Baxter

通常情况下，维基百科是有帮助的：http://en.wikipedia.org/wiki/Flood_fill。那里描述了很好的洪水算法，包括存储区域边界，这正是您想要的。它们中没有一个执行我的示例-更大的矩形建议；它们假设您可以轻松访问像素，而您声称您没有。不过我想知道，您每场比赛只需要确定一次国家形状...您确定这行不通吗？ - Ira Baxter

Answer 3

我建议您使用蒙特卡罗方法来解决这个问题。

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

从一组已知点开始，可能能够根据您的目标和初始点的结果改进更多的“随机”猜测（即起始城市的集合）。

我可能考虑尝试类似于已知点之间的等电位线，加权以点的预定大小。早期错误地假设为连接的岛屿会极大地影响这些猜测...需要更多的思考。

编辑：

所以我和一位朋友交流过，她是用卫星/航空图像进行特定植被区域的定位和分析的。这与这个问题有些相关，因为她试图在自己查看地图之前自动定位补丁。

她说典型的方法是应用一个网格模式，将您的总区域细分，并在发现特定模式时缩小。因此，您会对正则网格进行采样（设计此网格可以包括您正在寻找的大小的某些知识），如果找到匹配项，则在该区域内进行更多采样...如果没有，偏移网格并重新采样。

此方法的优化在于人类对您的搜索模式的了解。例如，您可以根据大小/形状的常见预期指定搜索网格中的细分数。

- Matthew

---

你肯定需要采样，而且你可以在城市周围进行采样。但是你需要一些能够相对快速地高效覆盖任意大块领土的东西，否则你的成本将会是领土面积（N^2）除以采样大小（小常数）。 - Ira Baxter