
Привет, Habr. В данный момент я разрабатываю игру про животных, где они должны беспорядочно бегать по карте. Идеей является то, что есть несколько видов животных, которые могут бегать только по своей территории, например:
Кошка, собака - по земле(Ground)
Рыбы и утки - по воде
и т.д.
В итоге я пришел к выводу, что зону проще всего разграничивать с помощью PolygoneCollider2D, как это реализовано в Cinemachine

Реализация №1(Медленный способ)
Я решил реализовать, что-то подобное, но только так, чтобы бралась на поверхности случайная точка и животное шло к ней. Поискав решение данной проблемы, я нашел лишь единственное решение:
public Vector3 PointInArea() {
var bounds = collider.bounds;
var center = bounds.center;
float x = 0;
float y = 0;
do {
x = UnityEngine.Random.Range(center.x - bounds.extents.x, center.x + bounds.extents.x);
y = UnityEngine.Random.Range(center.y - bounds.extents.y, center.y + bounds.extents.y);
} while (Physics2D.OverlapPoint(new Vector2(x, y), LayerMask.NameToLayer("Area")) == null);
return new Vector3(x, y, 0);
}
// https://forum.unity.com/threads/how-can-i-choose-random-points-inside-a-polygon-collider-2d.264985/
Оно основано на взятии случайной точки по границам polygonCollider2D и проверка, что эта точка попадает на поверхность PolygonCollider2D.OverlapPoint();

Минус данного подхода, что он если polygonCollider2D сильно искажен, то while будет выполнятся долго. Но для моей игры нужны именно искаженная поверхность.
Я проверил, и даже вывел метод нахождения точки в отдельный поток, но все равно скорость поиска меня не устраивала, тем более имелись проблемы со синхронизацией List с параллельными потоками.
Вывод по методу:
Плюсы:
Быстрый в реализации
Минусы:
Медленный в бою
Нельзя использовать со сложными геометриями
Реализация №2
Далее я решил уже пораскинуть мозгами и попробовать решить задачу математическим путем:
если выбрать 2 соседние вершины у многоугольника
найти случайную точку между ними
найти центр многоугольника
polygonCollider2D.bounds.center
и выбрать случайную точку между координатами центра и случайной точки между вершинами.

Как можно увидеть на втором примере, отрезок, образованный случайной точкой между двумя соседними вершинами и центром может выходить за пределы площади, а это мне не нужно.
Я порыскал по просторам интернета и нашел интересную статью: Generating Random Points within a Polygon in Unity. В ней автор пишет свою реализацию поиска точки в многоугольнике, но решает это для трехмерного пространства, а меня интересует 2D, но из этой статьи я узнал о методе разбиения многоугольника на треугольники(Delaunay triangulation).
Pеализацию этого алгоритма я нашел на C# в GitHub у k-j0 (сам алгоритм ТЫК).
С этими знаниями я придумал новый алгоритм:
Разбиваем многоугольник на треугольники с помощью алгоритма k-j0
Выбираем случайный треугольник
Ищем точку между двумя случайными две случайные вершинами, выбранного треугольника
Ищем центр тяжести треугольника по формуле
Находим случайную точку на отрезке ((3 пункт) и (4 пункт))
Вуаля, теперь точка попадает со 100% шансом на площадь многоугольника.
Переносим в Unity
Разбиваем polygonCollider2D на треугольники методом Triangulator.Triangulate
List<Triangulator.Triangle> _triangles =
Triangulator.Triangulate(polygonCollider2D.points.ToList());
Triangulator.Triangle triangle = _triangles[Random.Range(0, _triangles.Count)];
Ищем две случайные вершины треугольника
Vector2 onePoint = Vector2.zero;
Vector2 twoPoint = Vector2.zero;
switch (Random.Range(0, 3))
{
case 0:
onePoint = triangle.a;
twoPoint = triangle.b;
break;
case 1:
onePoint = triangle.b;
twoPoint = triangle.c;
break;
case 2:
onePoint = triangle.a;
twoPoint = triangle.c;
break;
}
Находим центр тяжести треугольника
Vector2 center = triangle.centerOfMass();
Далее нам нужно находить случайную точку между двумя точками. Для этого реализуем метод RandomPointBetween2Points
, который возвращает Vector2
private static Vector3 RandomPointBetween2Points(Vector3 start, Vector3 end){
return (start + Random.Range(0f, 1f) * (end - start));
}
Находим случайную точку между вершинами
Vector2 randomBetween2Vector = RandomPointBetween2Points(onePoint, twoPoint);
И в итоге генерируем готовую точку
Vector2 randomPoint = RandomPointBetween2Points(center, randomBetween2Vector);
Теперь метод можно вызывать легко и просто:
Vector2 point = RandomPoint.GetRandomPoint(polygonCollider2D);
Протестируем функцию на poligonCollider2D и найдем 100 точек

А 10000?

ВАЖНО! Нужно учесть, что точки генерируются относительно PolygonCollider2D, поэтому их потом следует приводить к Мировым координатам
Все ссылки и источники:
Исходники: https://github.com/LivelyPuer/RandomPoint
Haze Triangulator: https://github.com/k-j0/haze-triangulator
Готовый проект можно скачать ТУТ!
Спасибо за внимание!