Poisson Disc Sampling - C#
I started working on this project after I had some extra time during my school project, and after I found a video on Poisson Disc Sampling and how it can be used for distributed spawn points. After that I did some research and came across a research paper and started working on the project.
Pages/Papers use for research:
- Robert Braidson: Poisson Disc Sampling
First we have the Poisson Disc Sampling algorithm, this script is static so it can be called from any script without a reference. There are 2 functions, one for generating the points and one for checking if a point is valid. First I will go over the IsValid() function, first we check if the current point is within the boundaries of the grid. If yes it starts calculating the grid position, then it checks if the position of the current spawned point is within the radius of the previously spawned point. If yes it returns false, if no it returns true meaning it is a valid point and it gets added to the spawnpoints list.
static bool IsValid(Vector2 candidate, Vector2 sampleRegionSize, float cellSize, float radius, List points, int[,] grid)
{
if(candidate.x >= 0 && candidate.x < sampleRegionSize.x && candidate.y >= 0 && candidate.y < sampleRegionSize.y)
{
int cellX = (int)(candidate.x / cellSize);
int cellY = (int)(candidate.y / cellSize);
int searchStartX = Mathf.Max(0 ,cellX - 2);
int searchEndX = Mathf.Min(cellX + 2, grid.GetLength(0) - 1);
int searchStartY = Mathf.Max(0, cellY - 2);
int searchEndY = Mathf.Min(cellY + 2, grid.GetLength(1) - 1);
for (int x = searchStartX; x <= searchEndX; x++)
{
for (int y = searchStartY; y <= searchEndY; y++)
{
int pointIndex = grid[x, y] - 1;
if(pointIndex != -1)
{
float sqrDst = (candidate - points[pointIndex]).sqrMagnitude;
if(sqrDst < radius * radius)
{
return false;
}
}
}
}
return true;
}
return false;
}
The GeneratePoints() function is a static list taking in a float for the radius, a vector2 for the size of the grid, and a number of samples so it stops attempting a valid point after a X number of attempts. X is userdefined in this case bus by default it is 30. First the function will create the radius for each point on the grid, it does this by deviding the radius by the sqrt of 2 than it generates a grid. The grid is madeup of a multidimensional Int array that returns the value of the closest int for the X and the Y by deviding the gridSize of the current axis by the previously generated cellSize. Than it generates 2 vector2 lists one for the initially calculated points and one for the spawnpoints. After making the lists it gives the spawnpoints list a value calculated by the gridsize / 2.
public static List GeneratePoints(float radius, Vector2 sampleRegionSize, int numSpamplesBeforeRejection = 30)
{
float cellSize = radius / Mathf.Sqrt(2);
int[,] grid = new int[Mathf.CeilToInt(sampleRegionSize.x / cellSize), Mathf.CeilToInt(sampleRegionSize.y / cellSize)];
List points = new List();
List spawnPoints = new List();
spawnPoints.Add(sampleRegionSize / 2);
}
It then checks if the length of the spawnpoints list is greater than 0, if no it returns the list of points for the spawner to use. If yes it will first select a random spawnpoint, then it will get the centre of the selected spawnpoint and return this as a Vector2. It then creates a local boolean called candidate accepted. Then we have a loop checking if the number of itterations is lower than the max number of attempts, if no it returns points again. If yes we create a angle which the point will generate at from the last point. The angle is caluclated by (Random value * PI * 2), after that we create 2 new Vector2 variables one called dir and one called candidate. The dir.x is calculated by calculating the Sinus of the angle, and the dir.y is calculated by calculating the Cosinus of the angle. Than the candidate position is calculated by adding the dir to the spawnCentre and multiplying that by a random value between radius and radius * 2
public static List GeneratePoints(float radius, Vector2 sampleRegionSize, int numSpamplesBeforeRejection = 30)
{
while(spawnPoints.Count > 0)
{
int spawnIndex = Random.Range(0, spawnPoints.Count);
Vector2 spawnCentre = spawnPoints[spawnIndex];
bool candidateAccepted = false;
for (int i = 0; i < numSpamplesBeforeRejection; i++)
{
float angle = Random.value * Mathf.PI * 2;
Vector2 dir = new Vector2(Mathf.Sin(angle), Mathf.Cos(angle));
Vector2 candidate = spawnCentre + dir * Random.Range(radius, 2 * radius);
}
}
return points;
}
After that it calls the IsValid() function passing in the candidate, sampleRegionSize, cellSize, radius, points list and the grid. If the point returns valid it first adds it to the points and spawnpoints list. Then it sets the grid.x and grid.y at index candidate devided by cellsize equal to points.Count. Then it sets the bool candidateAccepted equal to true. If the IsValid() function returns false more times than the allowed attempts than it removes the spawnpoint from the spawnpoints list.
if(IsValid(candidate, sampleRegionSize, cellSize, radius, points, grid))
{
points.Add(candidate);
spawnPoints.Add(candidate);
grid[(int)(candidate.x / cellSize), (int)(candidate.y / cellSize)] = points.Count;
candidateAccepted = true;
break;
}
if(!candidateAccepted)
{
spawnPoints.RemoveAt(spawnIndex);
}
Conclusion:
I wont add the Poisson Disc Generator script, this because it only uses the data to generate items on a 2D grid. If you still want to take a look at the script you can find it at the repository linked down below. I enjoyed working on this project, although it isn't fully what I wanted it was still usefull to learn since I did learn about writing a algorithm using a research paper and completely on my own without tutorials.