Poisson Disk Sampling

Posted on May 08, 2020

GameMaker Studio 2 Tutorials

Overview

Similar to my last tutorial, I’m going to be coding a function for another type of uniform randomness. This time were dealing with Poisson Disk Sampling. Given a distance, this method with create a list of random points that are all uniformly distributed, with no clumping. The exact way I’m implementing this can be found in this paper. Anyways, let’s get coding.

Algorithm

  1. Assume the width “w”, height “h”, minumum distance “r”, and a constant “k”.
  2. Create a grid with a size of w and h divided by (r/sqrt(2)).
  3. Create an empty list for checking active points.
  4. Add a random point to the grid and active list as our starting point.
  5. If there are points in the active list, generate a random point r - r*2 units away, k times.
  6. Check the 8 grid indices directly surrounding the active point to see if it’s not taken.
  7. If there is a valid point, add that to the grid and active list.
  8. If there are no valid points, delete the current active point from the list.
  9. After some time, all the available grid indices will be taken, and the loop will end.

Code

/// Function poisson_disk_sample(width, height, radius)

var _width = argument0;
var _height = argument1;
var _r = argument2;
var _k = 30;
var _cellW = _r/sqrt(2);

var _cols = floor(_width/_cellW);
var _rows = floor(_height/_cellW);

var _grid = ds_grid_create(_cols, _rows);
var _active = ds_list_create();

var _x = _width/2;
var _y = _height/2;
var _xInd = floor(_x/_cellW);
var _yInd = floor(_y/_cellW);
_grid[# _xInd, _yInd] = [_x, _y];
ds_list_add(_active, [_x, _y]);

while (ds_list_size(_active) > 0) {
    var _index = irandom(ds_list_size(_active)-1);
    var _pos = _active[| _index];
    
    var _found = false;
    for (var _n = 0; _n < _k; _n++) {
        var _angle = random(360);
        var _dist = random_range(_r, _r*2);
        _x = _pos[0] + lengthdir_x(_dist, _angle);
        _y = _pos[1] + lengthdir_y(_dist, _angle);
        _xInd = floor(_x/_cellW);
        _yInd = floor(_y/_cellW);

        if (_xInd >= 0 && _yInd >= 0 && _xInd < _cols && _yInd < _rows) {
            if (!is_array(_grid[# _xInd, _yInd])) {
                var _ok = true;
                for (var _i = -1; _i <= 1; _i++) {
                    for (var _j = -1; _j <= 1; _j++) {
                        var _xCheck = _xInd + _i;
                        var _yCheck = _yInd + _j;
                        if (_xCheck >= 0 && _yCheck >= 0 && _xCheck < _cols && _yCheck < _rows) {
                            var _point = _grid[# _xCheck, _yCheck];
                            if (is_array(_point)) {
                                if (point_distance(_point[0], _point[1], _x, _y) < _r) {
                                    _ok = false;
                                }
                            }
                        }
                    }
                }
                
                if (_ok) {
                    _grid[# _xInd, _yInd] = [_x, _y];
                    ds_list_add(_active, [_x, _y]);
                    _found = true;
                }
            }
        }
    }
    
    if (!_found) {
        ds_list_delete(_active, _index);
    }
}

return _grid;

And to utilize this grid, I have these code snippets in an object.

/// Object Event: Create

points = poisson_disk_sample(room_width, room_height, 20);
/// Object Event: Draw

for (var _x = 0; _x < ds_grid_width(points); _x++) {
    for (var _y = 0; _y < ds_grid_height(points); _y++) {
        var _p = points[# _x, _y];
        if (is_array(_p)) {
            var _pX = _p[0];
            var _pY = _p[1];
            draw_circle(_pX, _pY, 1, false);
        }
    }
}

Example

Example Image Here are the results of the above code. You can see that all the points are evenly spread out, when compared to the completely random distribution with the same amount of points. All of the points are indeed at least 20 pixels away, and no more than 40 pixels away from each other.

Final Thoughts

This way of getting points is really useful for things like object placement, or creating uniform textures. I’ve been finding this a good way to seed other effects, such as drawing clouds dynamically. I hope this code will also be as useful for you as well.

Thanks for reading!

🠬 Previous Post: Perlin Noise
Next Post: Music Sequencing 🠮