高效地確定集合的邊界

我正在使用遊戲提供的API爲RTS遊戲編寫人工智能。我想要做的一件事就是確定一組圍繞敵國的線段。然而，遊戲只提供一個函數，告訴我一個2D點的領土ID。高效地確定集合的邊界

對遊戲AI的查詢執行起來非常昂貴，所以我需要將查詢次數保持在絕對最小值，即使這意味着偶爾會得到質量稍差的答案。高估敵方領土的面積比低估它更好。

如何使用最少數量的查詢有效地確定圍繞非凸面空間區域的一組邊界線？

鈮：答案寫在Lua的獎勵積分，但僞代碼也很好。

2011-02-03 Martin

可以區域是任何多邊形還是他們在特定形狀的瓷磚中定名？您是否有任何關於從哪裏開始尋找的信息，或者您是否只是查詢有限的二維空間來尋找它？ – Matthew 2011-02-03 18:54:41

它們可以是任何形狀。在這裏查看默認地圖上各大洲的輪廓：http://store.introversion.co.uk/images/screen_shots/defcon_screen1.jpg – Martin 2011-02-03 18:56:06

我知道幾個起點，因爲我可以得到所有敵方城市的位置。所以，假設你從已知敵人領域的20分開始。 – Martin 2011-02-03 18:56:55

我想你可以找到a指向該領土內的空間。稱Z.（因爲你有幾個城市，你可以選擇一個平均的城市位置作爲中心）

考慮到出發點Z，我會考慮做的是從那裏產生一組光線點，每條射線在尺寸上有一個下限和上限，並且該集合的數量在增加以獲得細節。我在下面勾畫出一個方案。沒有關於它的測試;隨時提出改進建議。

每條光線由一個角度θ表示，並且具有一個原點Z.而不是一個長度，每條光線有兩個相關的長度，內部和外部，我們將試圖收斂。 Inside的初始值設置爲0，外部設置爲大於任何可能區域（「Horizon」）的半徑的值;我們會縮小外部直到它在領土內部，並使用二分搜索（遊戲空間直徑的log2 N）來增長內部，直到它不在境外。隨着端點的擴展，我們還將增加射線的數量以獲取領土邊界細節。最終的結果應該是一系列的光線，這些光線建立在其終點不超過「間隔」的領土上。

您可以從一條光線（theta = North（0），Inside = 0，Outside = Horizon）開始。讓我們調用光線集合R.我們假設光線集合R按照θ，排序，如果我們有來自R的光線r，那麼下一個（r）是有序集合中的下一條光線，與下一個r）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

的運行成本應該在你的最大直徑領土日誌2，用具有與該領土由所選擇的射線終點間隔劃分的圓周做的乘法器。

該方案並不完美;在半島存在半島的情況下，它將會失敗，因爲在半島內沒有采樣發生光線穿越。如果半島任意變薄，則需要任意數量的樣本才能發現它們。你也許可以選擇一個半島的最小寬度，然後調整算法，當它最終找到一個聚合射線時，以半島寬度來確定它沒有失真。

來源

2011-02-12 18:36:18

你可能會尋找周邊的一組點的凸包，請參閱：http://en.wikipedia.org/wiki/Convex_hull

這是一個爲O（n log n）的問題 - 不是太糟糕計算。對於一些僞代碼，請參閱：http://en.wikipedia.org/wiki/Graham_scan

編輯：你澄清的問題，據我瞭解，這些區域不一定是凸的，所以凸包會給你比你正在尋找更廣闊的區域。然而，它可能是起點（因爲您要查找的最終非凸區域位於船體內部），您可以對其進行優化。

更多編輯：如果你真的只有一個函數來查詢單個點，那麼你的問題和向量化位圖圖像一樣。每個點是一個「像素」，敵人區域是「像素」的（近似）矢量化。

來源

2011-02-03 18:59:52 payne

我建議你使用蒙特卡洛方法

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

與一組已知點的開始應該可以能夠根據你的目標，知識，提高附加的「隨機」猜測接近它和結果你的初始點（即起始城市的集合）

我可能會考慮嘗試類似於已知點之間的等電位線，用推測的點大小加權。儘管錯誤地被認爲很早就被附加的島嶼會大大影響這些猜測，儘管......需要更多的思考。

編輯：

所以我有一個朋友誰做圖分析從SAT /航拍圖像......因爲她試圖自動審查前定位補丁有些涉及到這個問題定位具體的植被跨度發言地圖本身。

她說，典型的方法是應用網格模式，該網格模式可以細分您的總面積，並在找到特定模式時自行收縮。因此，您可以對常規網格進行採樣（設計此網格可以包含您正在查找的尺寸的一些知識），如果您遇到問題，請在該區域進行更多采樣......如果您不這樣做，請補償您的網格，樣品。

這種方法的優化在於您的搜索模式的人類知識。例如，您可以根據大小/形狀的共同期望指定搜索網格中的細分數。

來源

2011-02-03 19:27:06 Matthew

高效地確定集合的邊界

回答

相關問題