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

Question

[JohnMirra]

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

Извиняюсь, что если мутновато читается… Пример того как хочу поделить карту:

R - Это большой регион который подразделяется внутри себя на субрегионы
r - субрегионы в пределах которых возможно перемещаться по прямой

Оригинал карты:

Answer 1

[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...

Answer 2

[Griboks]

Это делают алгоритмы кластеризации. Их очень много. Найдите подходящий вам.

Comments

[JohnMirra]

Спасибо!
Не много почитал пару вариантов и не нашёл, как они решат мою проблему... Но в любом случае инфа любопытная... буду думать как она сможет мне хоть чутка помочь