@JohnMirra

Находил ли кто-нибудь алгоритм разделения рандомной карты на различные регионы?

Ищу алгоритм или решения для создания регионов в рандомно генерирующейся карте. Ищу подобное решения для увеличения продуктивности алгоритмов поиска пути. Находил ли кто-нибудь подобный алгоритм? Который, просматривая новую карту, делит её на регионы из больших пространств, в пределах которых возможно перемещаться по прямой, а если требуется свернуть при перемещении из каких-либо точек A и B, то рассчитывался бы новый регион…

Извиняюсь, что если мутновато читается… Пример того как хочу поделить карту:
60c4cafe76124026614896.jpeg
R - Это большой регион который подразделяется внутри себя на субрегионы
r - субрегионы в пределах которых возможно перемещаться по прямой

Оригинал карты:
60c4cb1fcd57f547527594.jpeg
  • Вопрос задан
  • 123 просмотра
Пригласить эксперта
Ответы на вопрос 2
@AlexHell
подробней про Кластеризацию
https://habr.com/ru/post/101338/

Ищу подобное решения для увеличения продуктивности алгоритмов поиска пути.

вы можете провести все ваши предварительные расчеты в оффлайне (т.е. на этапе генерации карты, а не во время "битвы")

как алгоритм - вводите любое правило (эвристику), которое показывает хорошие результаты, нужные вам (а никто не скажет, думайте, пробуйте)

например
- первым проходом - циклом итерируете все клетки одинакового типа (синие на карте например, допустим это "вода"), проверяете тип их соседей, выбираете границы, скажем зеленые\желтые (допустим "суша"), по результату этапа у вас есть большие области одного "цвета" с их границами (для описания можете заюзать bounding box или convex hull или что угодно такого рода)
- вторым проходом - можно поделить крупные области, на более мелкие, например получить r1, r2, r3 с вашего скриншота, из исходного (на вашем скриншоте нету, но считайте что он сумма r1+r2+r3).. с помощью определения макс удаленности, скажем берете границу любую случайно - и от нее далее ведете по границе, пока не превышен лимит, или еще как-нибудь во время итерации ваших точек внутри региона проверяете лимит длины до первоначально выбранной границы

p.s. а еще для той же цели оптимизации поиска почитайте
https://www.redblobgames.com/pathfinding/grids/alg...
Ответ написан
Комментировать
Griboks
@Griboks Куратор тега Unity
Это делают алгоритмы кластеризации. Их очень много. Найдите подходящий вам.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
19 мар. 2024, в 11:54
3000 руб./за проект
19 мар. 2024, в 11:52
3000 руб./за проект
19 мар. 2024, в 11:49
10000 руб./за проект