1

私はaisandbox.comコンテストのAIに取り組んでいます。私は、コンテストに参加するのではなく、楽しみのためにAIを作成しています（私が参加したかどうかをここで尋ねてルールを破る場合に備えて）。

を使用してエリアの2Dマップを取得できますself.level.blockHeights。マップ内のコーナーを見つけて防御することで、ボットが隠れることができる場所をいくつか見つけたいと思います。

だから私の質問は、0が空きスペースで1が壁である2次元の数字の配列を考えると、コーナーを見つけるための最良の方法は何ですか？

PS私はPythonを使用しています

編集：これは地図の例です（壁は黒です）そして見つけられる角は赤です： ここに画像の説明を入力してください

4

4 に答える 4

1

あなたの例のグリッドによると、少なくとも 2 で囲まれたコーナーを定義できるようです。0 1

最初はこの定義をばかげた実装で書くことから始めて (以下で意図的に行ったように)、たとえばパフォーマンスについて考えて改善することもできます。

2この実装ではコーナーを表します

Python の実装例:

g = [[1,1,1,0],
     [1,0,0,0],
     [1,0,0,0],
     [1,0,1,0],
     [1,1,1,1]]

width = len(g[0])
height = len(g)

for i in range(height):
    for j in range(width):
        if g[i][j] != 0:
            continue
        around = [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]
        walls = 0
        for (x,y) in around:
            if x < 0 or x >= height or y < 0 or y >= width:
                #Outside, count as wall
                walls += 1
            elif g[x][y] == 1:
                walls += 1
        if walls in [2,3]: # 4 would be inaccessible  
            g[i][j] = 2

出力：

[1, 1, 1, 2]
[1, 2, 0, 0]
[1, 0, 0, 0]
[1, 2, 1, 2]
[1, 1, 1, 1]
于 2012-11-17T21:28:03.597 に答える
1

これまでの答えは非常に遅いです (複雑さは線形ですが) - 特に Python では、大規模なループが含まれるためです。また、ノイズに対してあまり堅牢ではありません (ただし、ここでは必要ないことは理解しています)。

この問題を解決するための優れた方法 (scipy と numpy を使用する場合) は、画像に小さなカーネルを持つガウス フィルターを適用し、そこから元の画像を差し引くことです (アンダーフローしないように注意してください)。コーナーは背景に「にじむ」ため、結果の画像ではコーナーが最も高い強度のピクセルになります。

実際の例を次に示します。

import numpy
import scipy.ndimage
import scipy.misc

image= scipy.ndimage.imread('corners.png').astype(float)
image= numpy.mean( image, axis=2) #squash color channels
filtered=   scipy.ndimage.filters.gaussian_filter(image,1)
subtracted= (256+image)-filtered #take care not to underflow
maximum, minimum=   numpy.max(subtracted), numpy.min(subtracted)
magic= 0.48 #will depend on source image. Fool around and see what works
threshold= (maximum+minimum)/2+(maximum-minimum)*magic 
thresholded= subtracted>=threshold

print list(zip(*numpy.where(thresholded)))

出力[(190, 206), (207, 314)]

コーナー.png:

コーナー.png

フィルタリング:

フィルタリングされた

しきい値:

しきい値

于 2012-11-23T03:50:19.930 に答える
0

あなたの例から、2つの隣接するセルが壁で占められているフリーセルとしてコーナーを定義できます.2つの占有セルは、北/東、北/西、南/東、南/西の構成です。

したがって、コーナーを見つけるには、2D マップをスキャンして、すべてのフリー セルの隣接するセルを確認するだけです。

3 つの壁に囲まれたフリー セル (廊下の端など) は必要ないと想定しています。

関数があると仮定しますisWall(x,y):

def isCorner(x, y) :
     eastHasWall = isWall(x+1, y)
     westHasWall = isWall(x-1, y)
     northHasWall = isWall(x, y-1)
     southHasWall = isWall(x, y+1)

     wallArray = [eastHasWall, westHasWall, northHasWall, southHasWall]
     wallCount = wallArray.count(true)

     if wallCount == 2 :
         return (eastHasWall and northHasWall) or (eastHasWall and southHasWall) or (westHasWall and northHasWall) or (westHasWall and southHasWall)

     return false # other wall count are not corners

コードをテストしていませんが、コンパイルする必要があります。

また、マップの境界にも注意する必要があります。それらが壁と見なされるか、設定内の空きスペースと見なされるかを判断できるのは、あなただけです。

于 2012-11-17T21:24:41.203 に答える
0

疑似コード

function isCorner(x, y) {
    wallsFound = 0;
    if (withinBounds(x + 1, y) && grid[x + 1][y] == 1)
        wallsFound++
    if (withinBounds(x - 1, y) && grid[x - 1][y] == 1)
        wallsFound++
    if (withinBounds(x, y + 1) && grid[x][y + 1] == 1)
        wallsFound++
    if (withinBounds(x, y - 1) && grid[x][y - 1] == 1)
        wallsFound++
    return wallsFound  == 2 || wallsFound == 3;
}

function withinBounds(x, y) {
    return x >= 0
        && x < rows.len
        && y >= 0
        && y < cols.len
}

for i = 0 to rows.len
    for j = 0 to cols.len
        if isCorner(x, y)
            // do something

&&マップの端を壁としてカウントする場合は、||in isCorner に変更できます。

于 2012-11-17T21:28:13.643 に答える