我对 Bridson 算法 Poisson-Disk Sampling 的实现似乎陷入了无限循环

Question

Sebastion Lague 的一段视频很好地解释了 Bridson 的算法。

过于简单化，

1. 创建具有半径/sqrt(2) 边的单元格网格。

2. 放置初始点并将列表作为生成点。

3. 将点放入网格中的单元格中。

4. 对于任何生成点，生成半径和 2*radius 之间的点。

5. 查看距离新点单元格 2 个单位的单元格。

6. 如果包含其他点，则比较距离。

7. 如果任何点比半径更接近新点，则新点无效。

8. 如果新点有效，则将新点列为生成点并放入网格中的单元格中。

9. 如果 spawnpoint 生成了太多无效点，则 spawnpoint 将被删除并变成点。

10. 重复直到不再存在生成点。

11. 返回积分。

我在 Python 3.7.2 和 pygame 1.7~ 中基本上写了同样的东西，但正如标题中所说，我陷入了递归炼狱。

我为这个算法使用了一个 Point() 类，考虑到 pygame.Vector2() 存在，这似乎是多余的，但我需要一些元素用于需要这个类才能工作的单独算法（具有无限顶点的 Delaunay）。

为了简单起见，我将删除所有特定于 Delaunay 的元素，并展示该算法所需的此类的基本框架：

class Point:

    def __init__(self, x, y):

        self.x = x

        self.y = y

    def DistanceToSquared(self,other):

        return (self.x-other.x)**2 + (self.y-other.y)**2

与 Bridson 算法相关的代码是：

def PoissonDiskSampling(width, height, radius, startPos = None, spawnAttempts = 10):

    if startPos == None:

        startPos = [width//2,height//2]

    cellSize = radius / math.sqrt(2)

    cellNumberX = int(width // cellSize + 1)  # Initialise a cells grid for optimisation

    cellNumberY = int(height // cellSize + 1)

    cellGrid = [[None for x in range(cellNumberX)] for y in range(cellNumberY)]

    startingPoint = Point(startPos[0],startPos[1]) # Add an iniial point for spawning purposes

    cellGrid[startingPoint.x//radius][startingPoint.y//radius] = startingPoint

    points = [startingPoint] # Initialise 2 lists tracking all points and active points

    spawnpoints = [startingPoint]

    while len(spawnpoints) > 0:

        spawnIndex = random.randint(0,len(spawnpoints)-1)

        spawnpoint = spawnpoints[spawnIndex]

        spawned = False

        for i in range(spawnAttempts):

            r = random.uniform(radius,2*radius)

            radian = random.uniform(0,2*math.pi)

            newPoint = Point(spawnpoint.x + r*math.cos(radian),

                            spawnpoint.y + r*math.sin(radian))

            if 0 <= newPoint.x <= width and 0 <= newPoint.y <= height:

                isValid = True

            else:

                continue

Answer 1

您的代码中可能缺少最重要的步骤：如果新点有效，则将新点列为 spawnpoint 并放入 grid 中的单元格中。我建议将这一点添加到cellGrid是否有效：if isValid:&nbsp; &nbsp; cellGrid[newPointIndex[0]][newPointIndex[1]] = newPoint&nbsp; &nbsp; points.append(newPoint)&nbsp; &nbsp; spawnpoints.append(newPoint)&nbsp; &nbsp; spawned = True&nbsp; &nbsp; breaknewPointIndex此外，在可以添加点之前，您必须验证具有索引的单元格是否尚未被占用：newPointIndex = [int(newPoint.x/cellSize), int(newPoint.y/cellSize)]if cellGrid[newPointIndex[0]][newPointIndex[1]] != None:&nbsp; &nbsp; continueneighbours = FindNeighbours(cellNumberX,cellNumberY,newPointIndex,cellGrid)最后，函数存在问题FindNeighbours。range(start, stop)为 x in 创建一个范围start <= x < stop。所以停止必须是index[0]+3而不是index[0]+2。此外，控制 2 个嵌套for循环的范围从x-2toy+2而不是 from x-2tox+2分别从y-2to运行y+2：for cellX in range(max(0,(index[0]-2)), min(cellNumberX,(index[1]+2))):&nbsp; &nbsp;for cellY in range(max(0,(index[0]-2)), min(cellNumberY,(index[1]+2)))固定功能必须是：def FindNeighbours(cellNumberX, cellNumberY, index, cellGrid):&nbsp; &nbsp; neighbours = []&nbsp; &nbsp; for cellX in range(max(0, index[0]-2), min(cellNumberX, index[0]+3)):&nbsp; &nbsp; &nbsp; &nbsp; for cellY in range(max(0, index[1]-2), min(cellNumberY, index[1]+3)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if cellGrid[cellX][cellY] != None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; neighbours.append(cellGrid[cellX][cellY])&nbsp; &nbsp; return neighbours查看结果，尺寸为 300 x 300，半径为 15：spawnpoints如果始终使用第一个点而不是随机点，则可以获得更好的结果：# spawnIndex = random.randint(0,len(spawnpoints)-1)spawnIndex = 0 # 0 rather than randomspawnpoint = spawnpoints[spawnIndex]&nbsp;