泊松盤采樣(Poisson Disk Sampling)生成均勻隨機點

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public static class PoissonDiscSampling
{
    public static List<Vector3> GeneratePoints(float radius, Vector2 sampleRegionSize, int numSamplesBeforeRejection = 32)
    {
        bool IsValid(Vector3 candidate, Vector2 sampleRegionSize, float cellSize, float radius, List<Vector3> points, int[,] grid)
        {
            if (candidate.x - radius >= 0f && candidate.x + radius < sampleRegionSize.x && candidate.z - radius >= 0f && candidate.z + radius < sampleRegionSize.y)
            {
                int cellX = Mathf.RoundToInt(candidate.x / cellSize);
                int cellZ = Mathf.RoundToInt(candidate.z / cellSize);
                int searchStartX = Mathf.Max(0, cellX - 3);
                int searchEndX = Mathf.Min(cellX + 3, grid.GetLength(0) - 1);
                int searchStartZ = Mathf.Max(0, cellZ - 3);
                int searchEndZ = Mathf.Min(cellZ + 3, grid.GetLength(1) - 1);
                //如果要檢測其它格子內的球，需要遍歷周圍6個格子

                for (int x = searchStartX; x <= searchEndX; x++)
                {
                    for (int z = searchStartZ; z <= searchEndZ; z++)
                    {
                        int pointIndex = grid[x, z] - 1;//存長度不存索引，取時減1,0就變成了-1，不需要初始化數組了
                        if (pointIndex != -1)
                        {
                            float dst = (candidate - points[pointIndex]).magnitude;
                            if (dst < radius * 2f)
                            {
                                return false;
                            }
                        }
                    }
                }

                return true;
            }

            return false;
        }

        float cellSize = radius / Mathf.Sqrt(2);

        int[,] grid = new int[Mathf.CeilToInt(sampleRegionSize.x / cellSize), Mathf.CeilToInt(sampleRegionSize.y / cellSize)];
        List<Vector3> points = new List<Vector3>();
        List<Vector3> spawnPoints = new List<Vector3>();

        spawnPoints.Add(new Vector3(sampleRegionSize.x / 2f, 0f, sampleRegionSize.y / 2f));
        while (spawnPoints.Count > 0)
        {
            int spawnIndex = Random.Range(0, spawnPoints.Count);
            Vector3 spawnCenter = spawnPoints[spawnIndex];

            bool candidateAccepted = false;
            for (int i = 0; i < numSamplesBeforeRejection; i++)
            {
                float angle = Random.value * Mathf.PI * 2f;
                Vector3 dir = new Vector3(Mathf.Sin(angle), 0f, Mathf.Cos(angle));
                Vector3 candidate = spawnCenter + dir * Random.Range(2f, 3f) * radius;

                if (IsValid(candidate, sampleRegionSize, cellSize, radius, points, grid))
                {
                    points.Add(candidate);
                    spawnPoints.Add(candidate);
                    grid[Mathf.RoundToInt(candidate.x / cellSize), Mathf.RoundToInt(candidate.z / cellSize)] = points.Count;
                    candidateAccepted = true;
                    break;
                }
            }
            if (!candidateAccepted)
            {
                spawnPoints.RemoveAt(spawnIndex);
            }
        }

        return points;
    }
}

using System.Collections.Generic;
using UnityEngine;

public class Test : MonoBehaviour
{
    public float radius = 0.3f;
    public Vector2 sampleRegionSize = new Vector2(3f, 3f);
    private List<Vector3> mPoints;


    private void OnEnable()
    {
        mPoints = PossonDiscSampling.GeneratePoints(radius, sampleRegionSize);
    }

    private void OnDrawGizmos()
    {
        if (mPoints == null) return;

        float cellSize = radius / Mathf.Sqrt(2);

        Color cacheColor = Gizmos.color;
        Gizmos.color = new Color(0.5f, 0.5f, 0.5f, 0.5f);
        for (float x = 0; x < sampleRegionSize.x; x += cellSize)
        {
            for (float z = 0; z < sampleRegionSize.y; z += cellSize)
                Gizmos.DrawWireCube(new Vector3(x, 0f, z), new Vector3(cellSize, 0f, cellSize));
        }//生成對應采樣點的調試方格
        Gizmos.color = cacheColor;

        for (int i = 0; i < mPoints.Count; i++)
        {
            Vector3 vector = mPoints[i];

            Gizmos.DrawWireSphere(vector, radius);

            int x = Mathf.FloorToInt(vector.x / cellSize);
            int z = Mathf.FloorToInt(vector.z / cellSize);

            Gizmos.DrawWireCube(new Vector3(x, 0f, z) * cellSize, new Vector3(cellSize, 0f, cellSize));
            //生成當前點所屬方格
        }
    }
}