Если раскидать деревья, камни или точки спавна через Random.Range, получится лес с проплешинами и кучками стволов, растущих друг из друга. В этой статье разберём Poisson Disk Sampling — алгоритм, который выдаёт точки на минимальном расстоянии друг от друга и при этом плотно заполняет область. Вы получите готовую реализацию алгоритма Бридсона на C#, версию с переменной плотностью и запретными зонами, компонент для расстановки объектов по Terrain, бесшовный тайлящийся вариант и список ошибок, на которых обычно спотыкаются.
Почему Random.Range даёт кучки и пустоты
Равномерно случайные точки — это не равномерно расположенные точки. У независимых случайных координат нет памяти: каждая следующая точка понятия не имеет, где лежат предыдущие. Поэтому часть точек неизбежно оказывается почти друг на друге, а между ними остаются заметные пустые пятна. Глаз очень хорошо ловит такие скопления, и сцена выглядит «нагенерированной».
Первая попытка исправить это — сетка с дрожанием (jitter): делим область на клетки и ставим в каждую по одной точке со случайным смещением. Скоплений меньше, но появляются две новые проблемы. Во-первых, сетка всё равно читается, особенно сверху и на больших площадях. Во-вторых, гарантии минимального расстояния нет: две точки в соседних клетках могут сместиться к общей границе и встать вплотную. Можно ограничить смещение, но тогда сетка становится ещё заметнее.
Нужен третий вариант: точки стоят случайно, но никакие две не ближе заданного радиуса r, и при этом в области не остаётся места, куда можно было бы втиснуть ещё одну. Такое распределение называют Poisson disk (иногда blue noise — «синий шум», потому что в нём почти нет низких частот, то есть крупных скоплений и дыр). Его используют для растительности, декора, точек спавна, сэмплирования теней и SSAO, расстановки лута и вообще везде, где нужно «случайно, но аккуратно».
Наивный подход: метание дротиков
Самый прямолинейный способ — dart throwing. Генерируем случайную точку, проверяем расстояние до всех уже принятых, если ближе r — выбрасываем. Повторяем, пока не наберём нужное количество или пока подряд не случится много промахов.
List<Vector2> DartThrowing(Vector2 size, float radius, int maxFailures)
{
var points = new List<Vector2>();
int failures = 0;
while (failures < maxFailures)
{
var p = new Vector2(Random.value * size.x, Random.value * size.y);
bool ok = true;
foreach (var q in points)
{
if ((p - q).sqrMagnitude < radius * radius) { ok = false; break; }
}
if (ok) { points.Add(p); failures = 0; }
else failures++;
}
return points;
}У этого кода три проблемы. Проверка идёт по всем точкам, поэтому стоимость растёт квадратично. Чем плотнее заполнена область, тем реже попадаем в свободное место, и последние точки достаются сотнями промахов. И главное — непонятно, когда остановиться: при маленьком maxFailures остаются дыры, при большом генерация тянется бесконечно, а момента «места больше нет» алгоритм не видит.
Алгоритм Бридсона: идея
В 2007 году Роберт Бридсон опубликовал короткую статью «Fast Poisson Disk Sampling in Arbitrary Dimensions», где описал алгоритм с линейным временем работы. Он стал стандартом де-факто, и почти все реализации в играх — его вариации. Держится он на двух идеях.
Фоновая сетка для быстрой проверки соседей
Область делится на квадратные клетки со стороной r/√2. Диагональ такой клетки равна ровно r, поэтому в одной клетке физически не могут оказаться две точки: расстояние между ними было бы меньше r. Значит, сетку можно хранить как простой массив индексов, где −1 означает «пусто».
Чтобы проверить кандидата, не нужно перебирать все точки — достаточно посмотреть клетки вокруг. Конфликтная точка лежит не дальше r, а r — это примерно 1,41 стороны клетки, поэтому хватает квадрата 5×5 клеток с центром в клетке кандидата. Двадцать пять обращений к массиву вместо обхода тысяч точек.
Рост от активных точек
Вместо того чтобы бросать кандидатов по всей области, алгоритм растит распределение от уже поставленных точек. Он ведёт активный список — точки, вокруг которых, возможно, ещё есть свободное место.
- Ставим первую точку в случайное место, кладём её в сетку и в активный список.
- Пока активный список не пуст, берём из него случайную точку.
- Генерируем до k кандидатов в кольце между радиусами r и 2r вокруг неё.
- Первый кандидат, который прошёл проверку по сетке, становится новой точкой и тоже попадает в активный список.
- Если все k кандидатов отвергнуты, считаем, что вокруг этой точки места нет, и убираем её из активного списка.
Кольцо r…2r выбрано не случайно: ближе r кандидат заведомо конфликтует с центральной точкой, а дальше 2r мы бы перепрыгивали через место, куда могла бы встать точка. Бридсон рекомендует k = 30, и на практике этого хватает: распределение получается плотным, а лишней работы немного. Каждая точка попадает в активный список один раз и выходит из него после не более чем k неудачных попыток, отсюда и линейная сложность.
Критерий остановки встроен в алгоритм: когда активный список пуст, область заполнена. Никаких магических maxFailures.
Базовая реализация на C#
Начнём с минимальной версии: прямоугольная область, постоянный радиус, свой генератор случайных чисел с сидом. Код не зависит от сцены и компонентов, поэтому его легко тестировать и запускать хоть в редакторе, хоть в рантайме.
using System;
using System.Collections.Generic;
using UnityEngine;
public static class PoissonDisk
{
public static List<Vector2> Sample(Vector2 size, float radius, int seed, int attempts = 30)
{
var rng = new System.Random(seed);
float cellSize = radius / Mathf.Sqrt(2f);
int gridW = Mathf.CeilToInt(size.x / cellSize);
int gridH = Mathf.CeilToInt(size.y / cellSize);
var grid = new int[gridW * gridH];
Array.Fill(grid, -1);
var points = new List<Vector2>();
var active = new List<int>();
float r2 = radius * radius;
AddPoint(new Vector2(Next() * size.x, Next() * size.y));
while (active.Count > 0)
{
int activeIndex = rng.Next(active.Count);
Vector2 center = points[active[activeIndex]];
bool found = false;
for (int i = 0; i < attempts; i++)
{
float angle = Next() * Mathf.PI * 2f;
// Равномерно по площади кольца, а не по радиусу
float dist = Mathf.Sqrt(Mathf.Lerp(r2, 4f * r2, Next()));
Vector2 candidate = center + new Vector2(Mathf.Cos(angle), Mathf.Sin(angle)) * dist;
if (IsValid(candidate))
{
AddPoint(candidate);
found = true;
break;
}
}
if (!found)
{
// Удаление перестановкой с последним: O(1) вместо сдвига списка
int last = active.Count - 1;
active[activeIndex] = active[last];
active.RemoveAt(last);
}
}
return points;
float Next() => (float)rng.NextDouble();
void AddPoint(Vector2 p)
{
int index = points.Count;
points.Add(p);
active.Add(index);
grid[CellY(p) * gridW + CellX(p)] = index;
}
int CellX(Vector2 p) => (int)(p.x / cellSize);
int CellY(Vector2 p) => (int)(p.y / cellSize);
bool IsValid(Vector2 p)
{
if (p.x < 0f || p.y < 0f || p.x >= size.x || p.y >= size.y)
return false;
int cx = CellX(p), cy = CellY(p);
int x0 = Mathf.Max(cx - 2, 0), x1 = Mathf.Min(cx + 2, gridW - 1);
int y0 = Mathf.Max(cy - 2, 0), y1 = Mathf.Min(cy + 2, gridH - 1);
for (int y = y0; y <= y1; y++)
{
for (int x = x0; x <= x1; x++)
{
int other = grid[y * gridW + x];
if (other != -1 && (points[other] - p).sqrMagnitude < r2)
return false;
}
}
return true;
}
}
}Использование — одна строка:
List<Vector2> points = PoissonDisk.Sample(new Vector2(200f, 200f), radius: 4f, seed: 42);Детали, которые легко сделать неправильно
Расстояние в кольце. Если брать расстояние как Lerp(r, 2r, случайное число), кандидаты будут чаще оказываться у внутренней границы кольца: площадь внешней части больше, а вероятность одинаковая. Чтобы точки распределялись равномерно по площади, интерполировать нужно квадрат радиуса и потом брать корень, как в коде выше. На итоговое распределение это влияет не катастрофически, но равномерная выборка даёт чуть более плотное и ровное заполнение.
Сравнение квадратов. sqrMagnitude вместо magnitude избавляет от квадратного корня во внутреннем цикле. Мелочь, но это самое горячее место алгоритма.
Случайный выбор из активного списка. Если всегда брать последнюю добавленную точку, распределение растёт «червяком» и в нём появляются заметные направленные структуры. Случайный индекс плюс удаление перестановкой с последним элементом дают и правильный вид, и O(1) на удаление.
Свой генератор. UnityEngine.Random — глобальное состояние. Если между вызовами его трогает другой код (а это делает почти каждый скрипт с эффектами), результат с тем же сидом будет разным. Отдельный экземпляр System.Random гарантирует, что один и тот же сид в той же сборке всегда даёт ту же расстановку. Для строгого детерминизма между разными версиями рантайма лучше взять генератор с известным алгоритмом: например, Unity.Mathematics.Random из пакета Mathematics. Это структура на xorshift, её сид не должен быть нулём, а передавать её между методами нужно по ref, иначе вы будете крутить копию состояния.
Проверяем, что гарантия соблюдается
Алгоритм простой, но опечатка в границах цикла по сетке легко пропускает конфликтные пары, а визуально это заметно не сразу. Поэтому стоит один раз написать тест в Unity Test Framework, который проверяет гарантию полным перебором. На паре тысяч точек квадратичная проверка занимает доли секунды.
using NUnit.Framework;
using UnityEngine;
public class PoissonDiskTests
{
[TestCase(1)]
[TestCase(7)]
[TestCase(12345)]
public void PointsRespectMinimumDistance(int seed)
{
const float radius = 2f;
var points = PoissonDisk.Sample(new Vector2(60f, 40f), radius, seed);
Assert.Greater(points.Count, 100);
for (int i = 0; i < points.Count; i++)
for (int j = i + 1; j < points.Count; j++)
Assert.GreaterOrEqual((points[i] - points[j]).magnitude, radius - 1e-4f);
}
[Test]
public void SameSeedGivesSameResult()
{
var a = PoissonDisk.Sample(new Vector2(50f, 50f), 3f, 99);
var b = PoissonDisk.Sample(new Vector2(50f, 50f), 3f, 99);
CollectionAssert.AreEqual(a, b);
}
}Второй тест ловит случайное использование глобального Random внутри алгоритма, что особенно неприятно, если расстановка должна совпадать у всех игроков в мультиплеере или восстанавливаться из сохранения по сиду.
Переменная плотность и запретные зоны
Лес с одинаковым шагом между деревьями выглядит как питомник. В реальной сцене нужна переменная плотность: опушки реже, чаща гуще. Плюс запретные зоны — дороги, вода, слишком крутые склоны. Расширим алгоритм двумя функциями: radiusAt возвращает минимальное расстояние в точке, isAllowed говорит, можно ли вообще ставить туда объект.
С переменным радиусом нужно решить, что считать конфликтом двух точек с разными радиусами. Удобное правило — расстояние не меньше большего из двух радиусов. Оно симметричное: результат не зависит от того, какая точка появилась раньше. Из него же следуют размеры сетки: клетка считается по минимальному радиусу (чтобы в ней по-прежнему помещалось не больше одной точки), а соседей приходится просматривать на расстоянии максимального радиуса.
Заодно добавим ещё две возможности. Первая — несколько стартовых точек. Если isAllowed запрещает широкую полосу, например реку, рост от единственной стартовой точки через неё не перешагнёт, и второй берег останется пустым. Поэтому в начале пробуем поставить несколько случайных стартовых точек. Вторая — уже существующие точки-препятствия: они участвуют в проверке расстояния, но не растят распределение. Это понадобится для многослойной расстановки.
using System;
using System.Collections.Generic;
using UnityEngine;
public struct PoissonSettings
{
public Vector2 Size;
public float MinRadius;
public float MaxRadius;
public Func<Vector2, float> RadiusAt; // null — всегда MinRadius
public Func<Vector2, bool> IsAllowed; // null — разрешено везде
public int Seed;
public int Attempts; // обычно 30
public int StartPoints; // сколько стартовых попыток
}
public struct PoissonPoint
{
public Vector2 Position;
public float Radius;
}
public static class PoissonSampler
{
public static List<PoissonPoint> Sample(PoissonSettings s, IReadOnlyList<PoissonPoint> blockers = null)
{
var rng = new System.Random(s.Seed);
int attempts = s.Attempts > 0 ? s.Attempts : 30;
float cellSize = s.MinRadius / Mathf.Sqrt(2f);
int gridW = Mathf.CeilToInt(s.Size.x / cellSize);
int gridH = Mathf.CeilToInt(s.Size.y / cellSize);
int range = Mathf.CeilToInt(s.MaxRadius / cellSize);
var grid = new int[gridW * gridH];
Array.Fill(grid, -1);
// В all лежат и препятствия, и новые точки; в результат идут только новые
var all = new List<PoissonPoint>();
var active = new List<int>();
int firstOwn = 0;
if (blockers != null)
{
foreach (var b in blockers)
{
if (!InBounds(b.Position)) continue;
int index = all.Count;
all.Add(b);
grid[Cell(b.Position)] = index;
}
firstOwn = all.Count;
}
int starts = Mathf.Max(1, s.StartPoints);
for (int i = 0; i < starts * attempts; i++)
{
if (active.Count >= starts) break;
var p = new Vector2(Next() * s.Size.x, Next() * s.Size.y);
TryAdd(p);
}
while (active.Count > 0)
{
int activeIndex = rng.Next(active.Count);
PoissonPoint center = all[active[activeIndex]];
float r2 = center.Radius * center.Radius;
bool found = false;
for (int i = 0; i < attempts && !found; i++)
{
float angle = Next() * Mathf.PI * 2f;
float dist = Mathf.Sqrt(Mathf.Lerp(r2, 4f * r2, Next()));
var candidate = center.Position + new Vector2(Mathf.Cos(angle), Mathf.Sin(angle)) * dist;
found = TryAdd(candidate);
}
if (!found)
{
int last = active.Count - 1;
active[activeIndex] = active[last];
active.RemoveAt(last);
}
}
return all.GetRange(firstOwn, all.Count - firstOwn);
float Next() => (float)rng.NextDouble();
bool InBounds(Vector2 p) =>
p.x >= 0f && p.y >= 0f && p.x < s.Size.x && p.y < s.Size.y;
int Cell(Vector2 p) => (int)(p.y / cellSize) * gridW + (int)(p.x / cellSize);
float RadiusAt(Vector2 p) =>
s.RadiusAt == null
? s.MinRadius
: Mathf.Clamp(s.RadiusAt(p), s.MinRadius, s.MaxRadius);
bool TryAdd(Vector2 p)
{
if (!InBounds(p)) return false;
if (s.IsAllowed != null && !s.IsAllowed(p)) return false;
float radius = RadiusAt(p);
int cx = (int)(p.x / cellSize), cy = (int)(p.y / cellSize);
int x0 = Mathf.Max(cx - range, 0), x1 = Mathf.Min(cx + range, gridW - 1);
int y0 = Mathf.Max(cy - range, 0), y1 = Mathf.Min(cy + range, gridH - 1);
for (int y = y0; y <= y1; y++)
{
for (int x = x0; x <= x1; x++)
{
int other = grid[y * gridW + x];
if (other == -1) continue;
float need = Mathf.Max(radius, all[other].Radius);
if ((all[other].Position - p).sqrMagnitude < need * need)
return false;
}
}
int index = all.Count;
all.Add(new PoissonPoint { Position = p, Radius = radius });
active.Add(index);
grid[cy * gridW + cx] = index;
return true;
}
}
}Важная оговорка про препятствия: их радиус должен быть не меньше MinRadius текущего прохода, иначе две точки могут попасть в одну клетку сетки и одна перезапишет другую. Для многослойной расстановки это естественно выполняется: в препятствия передают крупные объекты с их собственным, большим радиусом.
Обратите внимание и на стоимость: при большом разбросе радиусов (скажем, 1 и 20) окно проверки становится огромным — range клеток в каждую сторону от кандидата. Если разброс нужен действительно широкий, лучше разбить генерацию на несколько слоёв, о чём ниже.
Плотность из шума
Самый частый источник плотности — шум Перлина. Значение шума от 0 до 1 переводим в радиус: где шум высокий, деревья стоят плотно, где низкий — редко.
float noiseScale = 0.015f;
var offset = new Vector2(371.3f, 912.7f); // сдвиг, чтобы разные сиды давали разный рисунок
var settings = new PoissonSettings
{
Size = new Vector2(500f, 500f),
MinRadius = 3f,
MaxRadius = 9f,
RadiusAt = p =>
{
float n = Mathf.PerlinNoise(p.x * noiseScale + offset.x, p.y * noiseScale + offset.y);
return Mathf.Lerp(9f, 3f, n);
},
Seed = 42,
StartPoints = 8,
};Mathf.PerlinNoise выдаёт одно и то же значение для одних и тех же координат, поэтому смещение offset стоит выводить из сида — иначе при смене сида поменяется расстановка, но не рисунок рощ и полян. Кривой отображения тоже можно управлять: если прогнать шум через AnimationCurve, получатся резкие границы между лесом и поляной вместо плавного перехода.
Расстановка по Terrain
Теперь соберём компонент, который ставит префабы на Terrain. Координаты сэмплера — это X и Z локальной плоскости террейна, высоту берём через Terrain.SampleHeight, а крутизну — через TerrainData.GetSteepness. Обратите внимание на единицы: SampleHeight принимает мировую позицию и возвращает высоту относительно позиции самого террейна, поэтому к результату нужно прибавить transform.position.y. GetSteepness принимает нормализованные координаты от 0 до 1 и возвращает угол склона в градусах.
using System.Collections.Generic;
using UnityEngine;
public class PoissonScatter : MonoBehaviour
{
[SerializeField] Terrain terrain;
[SerializeField] GameObject[] prefabs;
[SerializeField] float minRadius = 3f;
[SerializeField] float maxRadius = 9f;
[SerializeField] float noiseScale = 0.015f;
[SerializeField] float maxSlope = 30f;
[SerializeField] float minHeight = 2f;
[SerializeField] int seed = 42;
readonly List<GameObject> spawned = new();
[ContextMenu("Generate")]
public void Generate()
{
Clear();
TerrainData data = terrain.terrainData;
Vector3 origin = terrain.transform.position;
var size = new Vector2(data.size.x, data.size.z);
var rng = new System.Random(seed);
var offset = new Vector2((float)rng.NextDouble() * 10000f, (float)rng.NextDouble() * 10000f);
var settings = new PoissonSettings
{
Size = size,
MinRadius = minRadius,
MaxRadius = maxRadius,
RadiusAt = p => Mathf.Lerp(maxRadius, minRadius,
Mathf.PerlinNoise(p.x * noiseScale + offset.x, p.y * noiseScale + offset.y)),
IsAllowed = p =>
{
float u = p.x / size.x, v = p.y / size.y;
if (data.GetSteepness(u, v) > maxSlope) return false;
return data.GetInterpolatedHeight(u, v) >= minHeight;
},
Seed = seed,
StartPoints = 16,
};
foreach (var point in PoissonSampler.Sample(settings))
{
var world = origin + new Vector3(point.Position.x, 0f, point.Position.y);
world.y = terrain.SampleHeight(world) + origin.y;
var prefab = prefabs[rng.Next(prefabs.Length)];
var rotation = Quaternion.Euler(0f, (float)rng.NextDouble() * 360f, 0f);
var instance = Instantiate(prefab, world, rotation, transform);
instance.transform.localScale *= Mathf.Lerp(0.85f, 1.15f, (float)rng.NextDouble());
spawned.Add(instance);
}
}
[ContextMenu("Clear")]
public void Clear()
{
foreach (var go in spawned)
{
if (go == null) continue;
if (Application.isPlaying) Destroy(go);
else DestroyImmediate(go);
}
spawned.Clear();
}
}Несколько решений в этом коде стоит пояснить.
Фильтр внутри сэмплера, а не после. Соблазнительно сгенерировать точки по всей площади, а затем выкинуть те, что попали на склон или в воду. Но тогда у границ запретных зон остаются пустые полосы шириной до r: точки, которые могли бы встать у самого края, были отвергнуты из-за соседей, оказавшихся в запретной зоне и потом удалённых. Если фильтровать через IsAllowed во время роста, алгоритм заполняет разрешённую область вплотную к границе.
GetInterpolatedHeight вместо SampleHeight в фильтре. Он работает в тех же нормализованных координатах, что и GetSteepness, и не требует собирать мировую позицию. Высота здесь тоже относительно террейна, так что minHeight удобно использовать как уровень воды.
Один генератор на весь проход. Префаб, поворот и масштаб берутся из того же System.Random с тем же сидом, поэтому повторная генерация воспроизводит не только позиции, но и внешний вид. Учтите, что любое изменение параметров сэмплера меняет число точек, а значит, сдвигает и последовательность для префабов. Если нужно, чтобы выбор префаба был стабилен при правке радиусов, выводите его из хэша позиции, а не из общей последовательности.
Список spawned не сериализуется. После перезагрузки сцены компонент забудет о созданных объектах, и Clear их не удалит. В рабочем инструменте проще удалять всех детей transform или пометить список атрибутом [SerializeField]. Для тысяч деревьев на Terrain вообще лучше не создавать GameObject, а добавлять экземпляры через TerrainData.SetTreeInstances или рисовать их через Graphics.RenderMeshInstanced: позиции от этого не меняются, меняется только способ вывода.
Многослойная расстановка: деревья, кусты, трава
Реальная растительность — это несколько слоёв с разными масштабами: деревья на расстоянии 6–10 метров, кусты на 2–3 метра, камни где-то между. Пытаться описать всё одним сэмплером с огромным разбросом радиусов неудобно и медленно. Удобнее делать проходы от крупного к мелкому, передавая результат предыдущих проходов как препятствия.
var trees = PoissonSampler.Sample(new PoissonSettings
{
Size = size, MinRadius = 6f, MaxRadius = 10f, Seed = seed, StartPoints = 16,
IsAllowed = isAllowed,
});
// Кусту нельзя стоять ближе 2,5 м к стволу: передаём деревья с таким радиусом.
// Радиус препятствия не меньше MinRadius кустов — требование сетки соблюдено.
var treeBlockers = new List<PoissonPoint>(trees.Count);
foreach (var t in trees)
treeBlockers.Add(new PoissonPoint { Position = t.Position, Radius = 2.5f });
var bushes = PoissonSampler.Sample(new PoissonSettings
{
Size = size, MinRadius = 2f, MaxRadius = 3f, Seed = seed + 1, StartPoints = 16,
IsAllowed = isAllowed,
}, treeBlockers);Здесь есть тонкость с правилом «больший из двух радиусов». Препятствие с радиусом 2,5 и куст с радиусом 3 разойдутся на 3 метра, а куст с радиусом 2 — на 2,5. Если нужен строгий отступ от ствола независимо от радиуса куста, задайте радиус препятствия равным этому отступу и следите, чтобы он был не меньше MaxRadius кустов.
Сид второго прохода сдвинут на единицу. Если взять тот же сид, первые случайные числа совпадут с первым проходом, и стартовая точка кустов окажется ровно там, где первое дерево, — её отвергнут, но совпадения в последовательности дальше могут дать заметные корреляции.
Бесшовный тайл для больших миров
Для бесконечного или очень большого мира генерировать всю площадь заранее невозможно, а генерировать каждый чанк независимо — значит получить швы: у границы двух чанков точки из разных проходов встанут вплотную, ведь друг о друге они не знают. Один из простых рабочих подходов — сгенерировать один тайлящийся (периодический) набор точек и повторять его по миру.
Для периодичности область считается тором: точка у правого края — соседка точки у левого. В базовом алгоритме меняются три вещи.
- Размер клетки подгоняется так, чтобы в область укладывалось целое число клеток: считаем gridW и gridH как раньше, а затем cellX = size.x / gridW и cellY = size.y / gridH. Клетки становятся чуть меньше r/√2, и гарантия «одна точка на клетку» сохраняется.
- Кандидат за границей не отвергается, а заворачивается внутрь остатком от деления.
- Соседние клетки и расстояния считаются с заворачиванием.
static float Wrap(float v, float max) => ((v % max) + max) % max;
static float ToroidalSqrDistance(Vector2 a, Vector2 b, Vector2 size)
{
float dx = Mathf.Abs(a.x - b.x);
float dy = Mathf.Abs(a.y - b.y);
if (dx > size.x * 0.5f) dx = size.x - dx;
if (dy > size.y * 0.5f) dy = size.y - dy;
return dx * dx + dy * dy;
}
// В IsValid вместо обрезки индексов по краям сетки:
int range = Mathf.CeilToInt(radius / Mathf.Min(cellX, cellY));
for (int oy = -range; oy <= range; oy++)
{
for (int ox = -range; ox <= range; ox++)
{
int x = ((cx + ox) % gridW + gridW) % gridW;
int y = ((cy + oy) % gridH + gridH) % gridH;
int other = grid[y * gridW + x];
if (other != -1 && ToroidalSqrDistance(points[other], p, size) < r2)
return false;
}
}Окно проверки теперь считается от фактического размера клетки: после подгонки клетка может стать заметно меньше, и двух клеток в каждую сторону уже не хватит. Тайл стоит делать не меньше чем в десяток радиусов по стороне — тогда в нём хватает точек, чтобы повтор не бросался в глаза. А чтобы окончательно спрятать повтор, поверх тайла накладывают маску: каждая точка в мире пропускается или получает префаб по шуму и хэшу мировых координат. Позиции повторяются, но рисунок рощ и набор объектов — нет.
Производительность и работа вне главного потока
Алгоритм линейный, и на типичных объёмах — тысячи или десятки тысяч точек — генерация занимает миллисекунды или десятки миллисекунд. Узкие места обычно не в самом алгоритме, а вокруг него.
- Делегаты IsAllowed и RadiusAt вызываются на каждого кандидата, то есть до 30 раз на точку. Тяжёлый код в них (рейкаст, обращение к текстуре через GetPixel) быстро становится главной статьёй расходов. Кэшируйте данные в массивы заранее.
- Instantiate тысяч объектов дороже генерации точек на порядки. Для массовой растительности используйте инстансинг или деревья Terrain.
- Аллокации. Если генерация идёт в рантайме при загрузке чанков, переиспользуйте массивы сетки и списки между вызовами, а не создавайте их заново.
Распараллелить сам алгоритм Бридсона тяжело: каждая новая точка зависит от предыдущих. Но его можно целиком унести в фоновый поток, например через Task.Run, если внутри нет вызовов Unity API. Vector2 и Mathf безопасны, а вот TerrainData и Terrain работают только из главного потока. Поэтому заранее, на главном потоке, снимите карту высот через TerrainData.GetHeights и, если нужно, посчитайте крутизну в свой массив, а в IsAllowed читайте уже их. Для шума в фоновом потоке надёжнее взять функции noise.cnoise или noise.snoise из Unity.Mathematics: это обычный C#-код без обращений к движку, его можно вызывать и из Burst-джобов.
Отладка через Gizmos
Пока подбираете радиусы, удобно видеть сами точки и их радиусы, не создавая объекты. Небольшой компонент рисует их в окне сцены, когда он выделен:
using System.Collections.Generic;
using UnityEngine;
public class PoissonPreview : MonoBehaviour
{
[SerializeField] Vector2 size = new(100f, 100f);
[SerializeField] float minRadius = 2f;
[SerializeField] float maxRadius = 6f;
[SerializeField] float noiseScale = 0.03f;
[SerializeField] int seed = 1;
List<PoissonPoint> cache;
void OnValidate() => cache = null;
void OnDrawGizmosSelected()
{
cache ??= PoissonSampler.Sample(new PoissonSettings
{
Size = size,
MinRadius = minRadius,
MaxRadius = maxRadius,
RadiusAt = p => Mathf.Lerp(maxRadius, minRadius,
Mathf.PerlinNoise(p.x * noiseScale, p.y * noiseScale)),
Seed = seed,
StartPoints = 4,
});
foreach (var point in cache)
{
var pos = transform.position + new Vector3(point.Position.x, 0f, point.Position.y);
Gizmos.color = Color.white;
Gizmos.DrawSphere(pos, 0.15f);
Gizmos.color = new Color(1f, 1f, 1f, 0.15f);
Gizmos.DrawWireSphere(pos, point.Radius * 0.5f);
}
}
}Сферы радиусом в половину минимального расстояния у правильного распределения касаются, но не пересекаются. Если видите пересечения — ошибка в проверке соседей. Если между сферами остаются места, куда явно влезла бы ещё одна, — слишком мало попыток k или стартовых точек.
Типичные ошибки
- Клетка сетки размером r, а не r/√2. Тогда в одну клетку попадают две точки, вторая затирает первую в массиве, и проверка начинает пропускать конфликты. Внешне — редкие пары слишком близких объектов, которые трудно заметить и ещё труднее воспроизвести.
- Окно 3×3 вместо 5×5. С клеткой r/√2 конфликтная точка может оказаться через одну клетку. При переменном радиусе окно должно считаться от максимального радиуса.
- Глобальный UnityEngine.Random. Расстановка «плывёт» между запусками, хотя сид тот же.
- Фильтрация после генерации. Пустые полосы вдоль дорог и берегов.
- Одна стартовая точка при запретных зонах. Острова и участки за рекой остаются пустыми, причём какие именно — зависит от сида.
- Путаница координат. Сэмплер работает в плоскости XY, а мир — в XZ. Удобно держать преобразование в одном месте и не размазывать его по коду.
- Тяжёлые проверки в IsAllowed. Рейкаст на каждого кандидата — это до 30 рейкастов на точку. Сначала дешёвые проверки по массивам, физика — только для финальных точек.
Итог
Poisson Disk Sampling решает задачу «случайно, но аккуратно» лучше, чем случайные координаты или сетка с дрожанием: никакие две точки не стоят ближе заданного радиуса, а свободного места не остаётся. Алгоритм Бридсона делает это за линейное время благодаря двум приёмам — сетке с клеткой r/√2 и росту от активных точек с k попытками в кольце r…2r.
Базовая версия занимает около сотни строк и закрывает большинство задач. Переменный радиус с правилом «больший из двух» даёт естественную плотность, IsAllowed внутри сэмплера — плотное заполнение до самых границ запретных зон, несколько стартовых точек — заполнение разорванных областей, а передача предыдущих слоёв как препятствий — многослойную растительность без пересечений. Держите генератор случайных чисел локальным, проверьте гарантию расстояния тестом, и расстановка будет одинаковой у всех и при каждом запуске.
