I am trying to implement Poisson Disk Sampling algorithm to place trees on my map. I have been trying to implement for hours but it does not seem to work. The activeGrid array only increases, which means the function never ends to run. Any help would be appreciated.
Here is the function to generate the points:
function GeneratePoints(radius, sampleRegionSize, k)
local cellSize = radius / math.sqrt(2)
local columns = math.floor(sampleRegionSize.X / cellSize)
local rows = math.floor(sampleRegionSize.Y / cellSize)
local grid = table.create(rows, table.create(columns, -1))
local activeGrid = {}
local points = {}
local initialPos = sampleRegionSize / 2
table.insert(activeGrid, initialPos)
while #activeGrid > 0 do
local randIndex = math.random(1, #activeGrid)
local randPoint = activeGrid[randIndex]
local isPointFound = false
for n = 1, k do
local angle = math.random() * math.pi * 2
local dir = Vector2.new(math.cos(angle), math.sin(angle))
local mag = math.random(radius, 2 * radius)
local sample = randPoint + dir * mag
if IsSampleValid(sample, sampleRegionSize, cellSize, radius, points, grid) then
table.insert(points, sample)
table.insert(activeGrid, sample)
local sampleIndexX = math.clamp(math.round(sample.X / cellSize), 1, math.huge)
local sampleIndexY = math.clamp(math.round(sample.Y / cellSize), 1, math.huge)
grid[sampleIndexX][sampleIndexY] = #points
isPointFound = true
break
end
end
if not isPointFound then
table.remove(activeGrid, randIndex)
end
wait()
end
return points
end
Here is the code to check if point is valid:
function IsSampleValid(sample, sampleRegionSize, cellSize, radius, points, grid)
if sample.X > 0 and sample.X <= sampleRegionSize.X and sample.Y > 0 and sample.Y <= sampleRegionSize.Y then
local cellX = math.clamp(math.round(sample.X / cellSize), 1, math.huge)
local cellY = math.clamp(math.round(sample.Y / cellSize), 1, math.huge)
local searchStartX = math.max(1, cellX - 2)
local searchEndX = math.min(cellX + 2, #grid)
local searchStartY = math.max(1, cellY - 2)
local searchEndY = math.min(cellY + 2, #grid[1])
for x = searchStartX, searchEndX do
for y = searchStartY, searchEndY do
local pointIndex = grid[x][y]
if pointIndex ~= -1 then
local dist = (sample - points[pointIndex]).Magnitude
if dist < radius then
return false
end
end
end
end
return true
end
return false
end