効率的にセットの境界を特定する

Question

私は、ゲームが提供するAPIを使用して、RTSゲームのAIを作成しています。私がしたいことの1つは、敵国を囲む線分のセットを決定することです。しかし、このゲームでは、単一の2D地点のチームIDを教えてくれる関数しかありません。

ゲームAIへのクエリは実行するのに非常にコストがかかるので、時にはわずかに悪い質の回答が得られることを意味しても、クエリの数を絶対最小値に保つ必要があります。それは、それを過小評価するよりも、敵の領域の面積を過大評価する方が良い。

最小のクエリ数を使用して、非凸面領域の周りの境界線の集合を効率的に決定するにはどうすればよいですか？

Nb：答えのボーナスポイントはLuaで書かれていますが、疑似コードも問題ありません。

Answer 1

の地点にある地点にあると思われます。あなたはいくつかの都市を持っているので、中央の都市の場所を一種の中心として選ぶことができます。

出発点Zを考えると、各レイはサイズの下限と上限を持ち、セットは細部を得るために数が増えています。私は以下のスキームをスケッチしました。それについては何もテストされていません。気軽に改善を提案してください。

各光線は角度θで表され、原点Zを持ちます。各光線は1つの長さではなく、内側と外側の2つの長さがあり、収束しようとします。内側の初期値は0に設定され、外側は可能な半径（「水平線」）より大きい値に設定されます。私たちはそれが領土内に収まるまでOutsideを縮小し、二分探索（あなたのゲーム空間の直径でlog2 N）を使用して、それが領土のかなり外に出るまで内部で成長します。また、境界線の詳細を取得するために端点を広げて、光線の数を増やします。最終的な結果は、終点が「間隔を空けて」離れていない領域の境界を確立する一連の光線であると考えられます。

1本の光線から始めることができます（theta = North（0）、Inside = 0、Outside = Horizo​​n）。 一連の光線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を記録すべきです。

このスキームは完全ではありません。半島の中でサンプリングしないことによって、光線が交差するようになるという領土の半島の存在下では失敗するでしょう。もし半島が恣意的に薄ければ、それを発見するために任意に多くの標本が必要になるだろう。おそらく、半島の最小幅を選択し、最後に収束していないことを確認する半球幅の収束光線を見つけたら、外側にステップするアルゴリズムを調整することができます。

Answer 2

あなたが見、点のセットの周りの凸包を探していることがあります。http://en.wikipedia.org/wiki/Convex_hull

それはO（n個のnを記録）問題だ - あまりにも悪い、計算。いくつかの擬似コードは、以下を参照してくださいhttp://en.wikipedia.org/wiki/Graham_scan

EDITを：あなたの明確質問で、私は地域が必ずしも凸ではないことを理解し、その凸包は、あなたが探しているよりも広い範囲を提供します。しかし、それは出発点になる可能性があります（あなたが探している究極の非凸領域は船体の内側にあるので）。

詳細編集：実際には単一点を照会する機能しかない場合、問題はビットマップ画像をベクトル化することと同じです。各点は「画素」であり、敵領域は「画素」の（近似的な）ベクトル化である。

Answer 3

私はあなたは既知の点の集合で開始モンテカルロ法

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

を使用すると、追加の「ランダム」あなたのターゲットの知識に基づいて推測し、結果を向上させることができなければならないアプローチを提案あなたの最初のポイント（開始都市のセット）

ポイントの推定サイズで重み付けされた、既知ポイント間の等電位線に似たものを試してみることがあります。初期に誤ってアタッチされていると思われる島々は、これらの推測に大きな影響を与えます。

EDIT：彼女は見直し前にパッチの場所を自動化しようとするため

は、だから私はこの問題に幾分関連...土/航空写真から特定の植生のスパンの場所を特定するためのマップ解析を行い友人と話をしました地図自身。

彼女は典型的なアプローチでは、特定のパターンを見つけたときに、全体の領域を細分化して縮小するグリッドパターンを適用すると言います。あなたがヒットした場合、その領域でより多くのサンプルを...あなたがしない場合、あなたのグリッドをオフセットし、再配置してください（あなたが探しているサイズのいくつかの知識を含むことができる）サンプル。

この方法の最適化は、人間があなたの検索パターンを知っていることです。たとえば、サイズ/形状の一般的な期待に基づいて、検索グリッド内の細分数を指定します。