有效地确定集合的边界

发布于 2024-10-15 22:15:09 字数 256 浏览 1 评论 0原文

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

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

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

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

I'm writing an AI for an RTS game, using the API the game offers. One thing I want to do is determine a set of line segments bounding the enemy nation, However, the game only offers a function which tells me the teamID of a single 2D point of territory.

Queries to the game AI are incredibly expensive to execute, so I need to keep the number of queries to an absolute minimum, even if this means occasionally getting a slightly worse quality answer. It's also better to overestimate the area of the enemy territory than underestimate it.

How can I efficiently determine a set of bounding lines, around a non convex area of space, using the minimum number of queries?

Nb: Bonus points for answer written in Lua, but Pseudo-code is fine too.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

緦唸λ蓇 2024-10-22 22:15:09

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

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

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

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

You may be looking for the convex hull around a set of points, see: http://en.wikipedia.org/wiki/Convex_hull

It's an O(n log n) problem -- not too bad computationally. For some pseudocode, see: http://en.wikipedia.org/wiki/Graham_scan

EDIT: with your clarified question, I understand that the regions are not necessarily convex, so the convex hull will give you a broader region than you're looking for. However, it may be starting point (since the ultimate, non-convex region you're looking for is inside the hull) that you can refine.

MORE EDIT: if you really only have a function to query a single point, then your problem is the same as vectorizing a bitmap image. Each point is a "pixel", and the enemy region is the (approximate) vectorization of the "pixels".

冷…雨湿花 2024-10-22 22:15:09

我假设您可以在领土内的空间中找到一个点。称之为 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,乘数与区域的周长除以所选的射线端点间距有关。

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

I assume you can find a point in the space that is in the territory. Call that Z. (Since you have several cities, you could pick an average city location as being sort of central.)

Given the starting point Z, what I'd consider doing is generating a set of rays outward from that point, each ray having a lower and upper bound on size, and the set growing in number to get detail. I've sketched a scheme below. Nothing about it tested; feel free to suggest improvements.

Each ray is represented by an angle Theta, and has an origin Z. Rather than one length, each ray has two associated lengths, Inside and Outside, which we're going to try to converge. The initial value of Inside is set to 0 and outside set to a value larger than the radius any possible territory ("Horizon"); we'll shrink Outside till it is inside the territory, and grow Inside until it is not quite outside the territory, using binary search (log2 N in the diameter of your game space). We also going to increase the number of rays as the end points spread out to acquire territory boundary detail. The final result is supposed to be a set of rays that establish a bound around the territory whose endpoints are no more than "spacing" apart.

You can start with just one ray (theta=North(0), Inside=0, Outside=Horizon).
Lets call the set of rays R. We assume the set of rays R is sorted by theta,
and if we have a ray r from R, that next(r) is the next ray in the sorted set,
with next(r) for the last ray in R being the first ray in the set. Since
you know city locations, you might seed the set with rays having cities as Inside points.
It should work either way.

An additional parameter "threshold" gives you the degree of precision of your answer.

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

The running cost should be log 2 in your maximum territory diameter, with a multiplier having to do with the circumference of the territory divided by the ray end-point spacing chosen.

This scheme isn't perfect; it will fail in the presence of peninsulas of the territory that a ray happens to cross by not sampling within the peninsula. If peninsulas are arbitrarily thin, it would take arbitrarily many samples to discover them. You can perhaps choose a peninsula minimum width, and then adjust the algorithm to step outward when it finally finds a converged ray, in peninsula widths to make sure it hasn't goofed.

风流物 2024-10-22 22:15:09

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

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

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

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

编辑:

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

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

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

I suggest you approach it using Monte Carlo methods

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

Starting with a set of known points should may be able to improve additional "random" guesses based on knowledge of your targets and the results of your initial points (being the set of starting cities)

I might consider trying something akin to equi-potential lines between known points, weighted by the presumed size of the points. Islands which are incorrectly assumed to be attached early on will greatly affect these guesses though.... needs more thought.

EDIT:

So I spoke with a friend who does map analysis for locating spans of specific vegetation from sat/aerial images... somewhat related to this problem because she tries to automate locating patches before reviewing the maps herself.

She says the typical approach is to apply a grid pattern which subdivides your total area and shrinks within itself when it finds specific patterns. So you would sample a regular grid (designing this grid could include some knowledge of sizes you're looking for), if you get a hit, sample more in that area... if you don't, offset your grid and re-sample.

The optimization of this approach is in human knowledge of your search pattern. For example, you specify the number of subdivisions in your search grid based on a common expectation of size/shape.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文