подробней про Кластеризацию
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... 