python - My implementation of Bridson's algorithm Poisson-Disk Sampling seems to be stuck in an infinite loop

Question

A video by Sebastion Lague explained the Bridson's algorithm really well.

To oversimplify,

1. Create cell grid that has sides of radius/sqrt(2).

2. Place initial point and list as spawnpoint.

3. Place point into cell in grid.

4. For any spawnpoint, spawn a point between radius and 2*radius.

5. Look at the cells 2 units away from cell of new point.

6. If contains other points, compare distance.

7. If any point is closer to new point than the radius, new point is invalid.

8. If new point is valid, new point is listed as spawnpoint and placed into cell in grid.

9. If spawnpoint spawns too many invalid points, spawnpoint is removed and turns into point.

10. Repeat until no more spawnpoints exists.

11. Return points.

I basically written the same thing down in Python 3.7.2 and pygame 1.7~, but as said in the title, I'm stuck in recursive purgatory.

I used one Point() class for this algorithm, which might seem redundant given that pygame.Vector2() exists, but I needed some elements for a separate algorithm (Delaunay's with infinite vertices) that required this class to work.

For the sake of simplicity I'm going to cut away all the Delaunay-specific elements and show the bare-bones of this class that is needed for this algorithm:

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

The code that is related to the Bridson's algorithm is:

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

            newPointIndex = [int(newPoint.x//cellSize), int(newPoint.y//cellSize)]
            neighbours = FindNeighbours(cellNumberX,cellNumberY,newPointIndex,cellGrid)

            for neighbour in neighbours:
                if newPoint.DistanceToSquared(neighbour) < radius**2:
                    isValid = False
                    break

            if isValid:
                points.append(newPoint)
                spawnpoints.append(newPoint)
                spawned = True
                break
            else:
                continue

        if spawned == False:
            spawnpoints.remove(spawnpoint)

    return points

def FindNeighbours(cellNumberX, cellNumberY, index, cellGrid):
    neighbours = []
    for cellX in range(max(0,(index[0]-2)), min(cellNumberX,(index[1]+2))):
        for cellY in range(max(0,(index[0]-2)), min(cellNumberY,(index[1]+2))):
            if cellGrid[cellX][cellY] != None:
                neighbours.append(cellGrid[cellX][cellY])
    return neighbours

Please help.

Answer 1

The probably most important step is missing in your code:

8. If new point is valid, new point is listed as spawnpoint and placed into cell in grid.

I suggest to add the point to the cellGrid if it is valid:

if isValid:

    cellGrid[newPointIndex[0]][newPointIndex[1]] = newPoint

    points.append(newPoint)
    spawnpoints.append(newPoint)
    spawned = True
    break

Further, you have to verify if the cell with the index newPointIndex is not already occupied before a point can be add:

newPointIndex = [int(newPoint.x/cellSize), int(newPoint.y/cellSize)]
if cellGrid[newPointIndex[0]][newPointIndex[1]] != None:
    continue

neighbours = FindNeighbours(cellNumberX,cellNumberY,newPointIndex,cellGrid)

---

Finally there is an issue in the function FindNeighbours. range(start, stop) creates a range for x in start <= x < stop.
So the stop has to be index[0]+3 rather than index[0]+2.

Further the ranges which control the 2 nested for loops, run both from x-2 to y+2 rather than from x-2 to x+2 respectively from y-2 to y+2:

for cellX in range(max(0,(index[0]-2)), min(cellNumberX,(index[1]+2))):
   for cellY in range(max(0,(index[0]-2)), min(cellNumberY,(index[1]+2)))

The fixed function has to be:

def FindNeighbours(cellNumberX, cellNumberY, index, cellGrid):
    neighbours = []
    for cellX in range(max(0, index[0]-2), min(cellNumberX, index[0]+3)):
        for cellY in range(max(0, index[1]-2), min(cellNumberY, index[1]+3)):
            if cellGrid[cellX][cellY] != None:
                neighbours.append(cellGrid[cellX][cellY])
    return neighbours

---

See the result, for a size of 300 x 300 and a radius of 15:

---

An even better result can be achieve, if always the 1st point of spawnpoints is used to rather than a random point:

# spawnIndex = random.randint(0,len(spawnpoints)-1)
spawnIndex = 0 # 0 rather than random
spawnpoint = spawnpoints[spawnIndex]