Поиск случайной точки на PolygonCollider2D Unity

Привет, Habr. В данный момент я разрабатываю игру про животных, где они должны беспорядочно бегать по карте. Идеей является то, что есть несколько видов животных, которые могут бегать только по своей территории, например:

1. Кошка, собака - по земле(Ground)

2. Рыбы и утки - по воде

3. и т.д.

В итоге я пришел к выводу, что зону проще всего разграничивать с помощью 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 (сам алгоритм ТЫК).

С этими знаниями я придумал новый алгоритм:

1. Разбиваем многоугольник на треугольники с помощью алгоритма k-j0

2. Выбираем случайный треугольник

3. Ищем точку между двумя случайными две случайные вершинами, выбранного треугольника

4. Ищем центр тяжести треугольника по формуле

5. Находим случайную точку на отрезке ((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

Готовый проект можно скачать ТУТ!

Спасибо за внимание!