1

我正在为 aisandbox.com 比赛开发 AI。我制作 AI 是为了好玩，而不是为了参加比赛（以防万一我在这里问我是否违反了规则）。

我可以使用 获得该区域的 2d 地图self.level.blockHeights，并且我想通过在地图中找到角落并让它们在那里防御来找到我的机器人可以隐藏的一些地方。

所以我的问题是，给定一个 2d 数字数组，其中 0 是自由空间，1 是墙，找到角落的最佳方法是什么？

Ps 我正在使用 Python

编辑：这是一个地图示例（墙壁是黑色的），要找到的角落是红色的： 在此处输入图像描述

4

4 回答 4

1

根据您的示例网格，似乎可以定义一个角，该角0 至少被 2 包围 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

从您的示例中，可以将角定义为自由单元格，其中两个相邻的单元格被墙壁占据，这两个占据的单元格配置为北/东、北/西、南/东和南/西。

因此，找到角落只是扫描您的 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 回答