在二进制网格中扩展块(扩展)

Question

对于A*实现(为“汽车”机器人生成路径)，我需要调整我的模型以考虑汽车的“宽度”，从而避开障碍物。

我得到的一个想法是将所有障碍物扩展到汽车的宽度，这样所有离障碍物太近的单元格也会被标记为障碍物。

我试过使用两个简单的算法来做这件事，但它仍然太慢(特别是在大网格上)，因为它会多次遍历相同的单元：

    unreachable = set()
    # I first add all the unreachables to a set to avoid 'propagation'
    for line in self.grid:
        for cell in line:
            if not cell.reachable:
                unreachable.add(cell)

    for cell in unreachable:
        # I set as unreachable all the cell's neighbours in a certain radius
        for nCell in self.neighbours( cell, int(radius/division) ):
            nCell.reachable = False

下面是邻居的定义：

def neighbours(self, cell, radius = 1, unreachables = False):
    neighbours = set()
    for i in xrange(-radius, radius + 1):
        for j in xrange(-radius, radius + 1):
            x = cell.x + j
            y = cell.y + i
            if 0 <= y < self.height and 0 <= x < self.width and (self.grid[y][x].reachable or unreachables )) :
                neighbours.add(self.grid[y][x])

    return neighbours

有没有序列算法(或O(n.log(N)可以做同样的事情？

Answer 1

我最终使用了卷积乘积，将我的'map‘(一个矩阵，其中'1’是障碍物，'0‘是一个自由单元)作为第一个操作数和一个汽车大小的矩阵，并用’1‘填充作为第二个操作数。

这两个矩阵的卷积积给出了一个矩阵，其中不在任何障碍物(即:在邻域中没有任何障碍物)的单元的值为' 0 '，而在邻域中至少有一个障碍物的单元(即等于‘1’的单元)的值为!= 0。

下面是Python实现(对卷积产品使用scipy )：

    # r: car's radius; 1 : Unreachable ; 0 : Reachable
    car = scipy.array( [[1 for i in xrange(r)] for j in xrange(r)] )
    # Converting my map to a binary matrix
    grid = scipy.array( [[0 if self.grid[i][j].reachable else 1 for j in xrange(self.width)] for i in xrange(self.height)] )

    result = scipy.signal.fftconvolve( grid, car, 'same' )

    # Updating the map with the result
    for i in xrange(self.height):
        for j in xrange(self.width):
            self.grid[i][j].reachable = int(result[i][j]) == 0

Answer 2

你要找的是所谓的Minkowski sum，如果你的障碍物和汽车是凸的，有一个线性算法来计算它。