A video by Sebastion Lague explained the Bridson's algorithm really well.
过于简单化,
Create cell grid that has sides of radius/sqrt(2).
Place initial point and list as spawnpoint.
Place point into cell in grid.
For any spawnpoint, spawn a point between radius and 2*radius.
Look at the cells 2 units away from cell of new point.
If contains other points, compare distance.
If any point is closer to new point than the radius, new point is invalid.
If new point is valid, new point is listed as spawnpoint and placed into cell in grid.
If spawnpoint spawns too many invalid points, spawnpoint is removed and turns into point.
Repeat until no more spawnpoints exists.
Return points.
我基本上在Python3.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
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
请帮忙
代码中可能缺少最重要的步骤:
我建议将该点添加到
cellGrid
中,如果该点有效:此外,在添加点之前,必须验证索引为
newPointIndex
的单元格是否已被占用:最后,函数}中为x创建一个范围。
FindNeighbours
中存在一个问题range(start, stop)
在{因此,停止必须是
index[0]+3
,而不是index[0]+2
此外,控制2个嵌套的
for
循环的范围从x-2
到y+2
运行,而不是从x-2
到x+2
分别从y-2
到y+2
运行:固定功能必须是:
对于300 x 300的尺寸和15的半径,请参见结果:
如果总是使用
spawnpoints
的第一个点而不是随机点来:相关问题 更多 >
编程相关推荐