@JohnMirra

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

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

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

Оригинал карты:
60c4cb1fcd57f547527594.jpeg
  • Вопрос задан
  • 104 просмотра
Пригласить эксперта
Ответы на вопрос 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
Это делают алгоритмы кластеризации. Их очень много. Найдите подходящий вам.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы