Read the original post on my blog for a smoother experience.
Godot Tutorial
- First let’s go over the variables
# Variables
@export var minDistance : float = 30.0 ## Minimum distance between points
@export var sampleAttempts : int = 30 ## Number of attempts to place a point around an active point, avoids infinite loops
@export var maxDistanceMultiplier : float = 2 ## Multiplied to the minimum distance to get the max distance it'll look for a location from the point
@export var chunkSize : Vector2 = Vector2(200, 200)
@export var pointOffset : Vector2 = Vector2(100, 100) ## Adds an offset to the final position if needed
@export var obstacles : Array[ChunkObstacle] = []
@export_group("Debug")
@export var debugMode : bool = true
@export var pointDebug : PackedScene
var grid : Array = []
var gridCellSize : float
var activeList : Array = [] ## Used for when generating the list of points
var points : Array = [] ## Stores the final points
var usedPoints : Array = []- `minDistance`: Minimum distance required between the two points
- `sampleAttempts`: Number of attempts to place a point, stopping any chances of an infinite while loop
- `maxDistanceMultiplier`: Used to determined the max distance from a point another point can be placed, calculated by multiplying it by the `minDistance`
- `chunkSize`: Size of the chunk
- `pointOffset`: Adds an offset to the final positions if needed depending on world structure
- `activeList`: Used to loop through all the points to check for more valid points when getting a list of points
- `points`: Stores all the final and valid points
- The script is made up of a few functions
func _poisson_disc_sampling_algorithm() -> void:
_initialize_grid()
_generate_points()
if debugMode:
_draw_points()
_place_obstacles()- Let’s start with initializing the grid
func _initialize_grid() -> void:
## Get grid sizing
gridCellSize = minDistance / sqrt(2)
var gridWidth : int = int(ceil(chunkSize.x / gridCellSize))
var gridHeight : int = int(ceil(chunkSize.y / gridCellSize))
## Create 2D grid array
grid = []
for i in range(gridWidth):
grid.append([])
for j in range(gridHeight):
grid[i].append(null)- Why do we divide by `sqrt(2)` to find the grid cell size?
- > The equation to find the longest distance across the cell aka the diagonal is `diagonal = side length * sqrt(2)*
- > To ensure the entire cell is within range of r (minimum distance), you want the diagonal cell to be les than or equal to r
- > So `r / sqrt(2)` ensures that if two points are more then r apart, they won’t be in the same cell or neighboring cells
- Next let’s actually determine our points
func _generate_points():
## Start with a random point
var firstPoint : Vector2 = Vector2(randf_range(0, chunkSize.x), randf_range(0, chunkSize.y))
_add_point(firstPoint)
## Find all valid points
while activeList.size() > 0:
var point : Vector2 = activeList.pick_random()
var isFound : bool = false
for i in range(0, sampleAttempts):
var newPoint : Vector2 = _generate_random_point_around(point)
if _is_valid_point(newPoint):
_add_point(newPoint)
isFound = true
break
if !isFound:
activeList.erase(point)- Let’s break down some of the functions getting called
- First let’s go over the function to add the point
func _add_point(_point: Vector2):
points.append(_point)
activeList.append(_point)
var gridPos = _point_to_gridPos(_point) ## Convert the position into a grid cell ID
grid[gridPos.x][gridPos.y] = _point- First things first, it stores the point in the points list and the active list of points to get a point from
- Then to add it to the grid we need to convert the points location to a spot in the grid to store it in the array
func _point_to_gridPos(_point: Vector2) -> Vector2:
return Vector2(int(_point.x / gridCellSize), int(_point.y / gridCellSize))- Then, we search for all the valid points
- The variable `sampleAttempts` gets used to make sure we don’t get stuck in an infinite loop
- When getting a new point we generate that point based on the current point we’re basing it off of
func _generate_random_point_around(_point: Vector2) -> Vector2:
var r = randf_range(minDistance, maxDistanceMultiplier * minDistance)
var angle = randf() * TAU
return _point + Vector2(cos(angle), sin(angle)) * r- First, let’s breakdown the line `var r = randf_range(minDistance, maxDistanceMultiplier * minDistance)`
- > This generates a point (`r`) from the existing point to be placed
- > It gets a point anywhere from the minimum distance to the max distance, which is calculated via the `maxDistanceMultiplier` and the `minDistance`, ensuring it’s not too close and not too far
- >> NOTE: You could always give a specific max distance value instead of just multiplying by the `minDistance` if you want!
- Next, let’s breakdown the line `var angle = randf() * TAU`
- > This gets an angle which determines the direction the new point will be placed compared to the existing point
- > TAU is the same as 2π radians (360 degrees), so it gets a random point within a circle
- Lastly, let’s breakdown the line `return _point + Vector2(cos(angle), sin(angle)) * r`
- > This gets the new position of the point based on the distance and angle
- > cos/sin gets a vector that points in the correct direction (between -1 and 1)
- > Then we multiply that be `r` to get the desired distance
- > Lastly, we add that offset to the existing point to get the new point location
- Now that we have our point, we have to make sure it’s valid
func _is_valid_point(_point: Vector2) -> bool:
## Check if the point is within chunk bounds
if _point.x < 0 or _point.x >= chunkSize.x or _point.y < 0 or _point.y >= chunkSize.y:
return false
var gridPos = _point_to_gridPos(_point)
## Check neighboring cells in the grid
for i in range(-1, 2):
for j in range(-1, 2):
var neighborPos = gridPos + Vector2(i, j)
if neighborPos.x >= 0 and neighborPos.x < grid.size() and neighborPos.y >= 0 and neighborPos.y < grid[0].size():
var neighborPoint = grid[neighborPos.x][neighborPos.y]
if neighborPoint != null:
if _point.distance_to(neighborPoint) < minDistance:
return false
return true- First we check if it’s within bounds of our chunk
- Then we convert the point to it’s location on the grid
- Next we go through 2 for loops to check all the surrounding neighbors
- > We store the grid position to check and make sure it exists within the grid array
- > If it does, we then get the value stored in that location, if it’s null then it’s valid and we return true, otherwise we check the distances between the points to make sure they area/greater then the minimum distance required and if they’re not then we return false
- Alright, now that we have all the points let’s continue
- In order to better visualize the program, we can place a bunch of circle meshes at each point
func _draw_points():
## Draw the generated points as circle mesh instances
for point in points:
var newPoint = pointDebug.instantiate()
self.add_child(newPoint)
newPoint.global_position = Vector3(point.x - pointOffset.x, 0, point.y - pointOffset.y) ## Add an offset to the location- When placing the point, we may want to add an offset depending on the structure of the world
- Lastly, let’s update the obstacles positions
func _place_obstacles() -> void:
## Reset used points
points += usedPoints
usedPoints.clear()
## Place obstacles on random points
for obstacle in obstacles:
var targetPoint : Vector2 = points.pick_random()
targetPoint -= pointOffset
obstacle.place_obstacle(targetPoint)
usedPoints.append(targetPoint)
points.erase(targetPoint)- Before placing the obstacles, we’ll want to reset the `usedPoints` since I want to move all the obstacles, otherwise if you only want to move a few you can simple remove those specific obstacles locations via a for each loop from the usedPoints instead of all of them
- Then when placing the obstacles we simply want to pick a random point, add the offset to it and store it as a used point and removing it form the list of valid points
- In my case, the obstacles already exist so I simply call a function to update the placement of the obstacle but in other cases you may generate the obstacle at run time as well
And that’s it! Now you have a poisson disc sampling algorithm that you can build upon to fit your games needs. Here are some things that can be added on:
- Support for Multiple Generations: Let’s say you want to use this algorithm to place obstacles but to ALSO place enemies. Your obstacles (like a building) is probably much bigger then an enemy so your distance checks will be different. Adding in an extra system that can check previously placed chunks with it’s own distance value on top of the current system is one add-on that can be done.
- Storing Previous Runs: Let’s say you mix this with, oh I don’t know, a chunk loading system not too different from my own *cough* you can see the tutorial here *cough*, adding in a system to store the locations of the obstacles so that they can be reloaded when needed can be another QoL feature to add.
Tune in next week for how we’ll combine last weeks post with this weeks post to make a basic chunk loading system! If you want to support me, you can get the project template for this on my itchio.
