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, height, minumum distance.
2. Create an array with a size of width and height 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 _cellWidth = _radius / sqrt(2);
    
    var _cols = floor(_width / _cellWidth);
    var _rows = floor(_height / _cellWidth);
    show_debug_message(_cols)
    
    var _result = array_create(_cols * _rows);
    var _active = ds_list_create();
    
    var _x = _width * 0.5;
    var _y = _height * 0.5;
    var _xIndex = floor(_x / _cellWidth);
    var _yIndex = floor(_y / _cellWidth);
    _result[_xIndex * _cols + _yIndex] = [_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 < 30; _n++) {
            var _angle = random(360);
            var _dist = random_range(_radius, _radius * 2);
            _x = _pos[0] + lengthdir_x(_dist, _angle);
            _y = _pos[1] + lengthdir_y(_dist, _angle);
            _xIndex = floor(_x / _cellWidth);
            _yIndex = floor(_y / _cellWidth);
            
            if (_xIndex >= 0 && _yIndex >= 0 && _xIndex < _cols && _yIndex < _rows) {
                if (!is_array(_result[_yIndex * _cols + _xIndex])) {
                    var _ok = true;
                    for (var _i = -1; _i <= 1; _i++) {
                        for (var _j = -1; _j <= 1; _j++) {
                            var _xCheck = _xIndex + _i;
                            var _yCheck = _yIndex + _j;
                            if (_xCheck >= 0 && _yCheck >= 0 && _xCheck < _cols && _yCheck < _rows) {
                                var _point = _result[_yCheck * _cols + _xCheck];
                                if (is_array(_point)) {
                                    if (point_distance(_point[0], _point[1], _x, _y) < _radius) {
                                        _ok = false;
                                    }
                                }
                            }
                        }
                    }
                
                    if (_ok) {
                        _result[_yIndex * _cols + _xIndex] = [_x, _y];
                        ds_list_add(_active, [_x, _y]);
                        _found = true;
                        break;
                    }
                }
            }
        }
    
        if (!_found) { ds_list_delete(_active, _index); }
    }
    
    return _result;
}

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

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

/// Object Event: Draw
var _len = array_length(points)
for (var _i = 0; _i < _len; _i++) {
    var _p = points[_i];
    if (is_array(_p)) {
        var _pX = _p[0];
        var _pY = _p[1];
        // Do things here with _pX and _pY
    }
}

Example

Here are the results of the above code. You can see that all the points are evenly spread out, with no visible clumping.

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! -AH