Расстановка позиций с расстоянием
Есть планета построенная из шестиугольных тайлов, последовательность которых хранится как одномерный массив a[n].
Задача выбрать список рандомных тайлов, удалённых друг от друга на расстояние не менее заданного расстояния X, ну или так чтобы они оказались рандомно расположены по миру, но не слишком близко друг к другу, для того чтобы поставить там поселения.
Из общего списка тайлов, используя linq я выбираю те что мне подходят (те которые не вода), с этим списком пытаюсь работать...
Пробовал рандомно расставлять каждый, проверяя расстояния между ним и всеми остальными уже отмеченными, но такой подход мне кажется костылем, да и при большом количестве время на это дело может быть очень не маленьким.
Ещё пробовал генерировать точки шумом, а после перебирать каждый на расстояние ко всем оставшимся кроме уже вошедших. Но такой подход хоть и немного легче, но все ещё какой то костыль.
Подскажите, какие ещё могут быть решения
Ответы (1 шт):
Можно конечно дать хексагоном свойство широты и долготы и иметь возможность считать расстояние между ними на сфере, но в поиске путей это не сильно поможет, да и считать расстояние между всеми, перебирая все элементы затратное дело.
Тут нужен граф. Добавь информацию о соседних хексагонах, их индексах
int[] neighborings;.
У хексагона есть тип, сделав таблицу проходимостей для разных типов, позволит строить пути не самыми короткими, а самыми быстрыми, не пытаясь идти по воде с коэффициентом
0 и обходя горы, болота и леса с низким коэффициентом при возможности, как на карте RimWorld.
Используя граф, можно искать хексагоны не только волновым способом, но и поиск пути A*.