Создание случайных точек с заданным минимальным и максимальным расстоянием

Question

Мне нужны идеи алгоритмов для создания точек в 2D пространстве с заданными минимальными и максимально возможными расстояниями между точками.

Bassicaly, я хочу найти хороший способ вставить точку в 2D-пространстве, заполненном точками, таким образом, что точка имеет случайное местоположение, но также больше MINIMUM_DISTANCE_NUM и меньше MAXIMUM_DISTANCE_NUM вдали от ближайших точек.

Мне нужна она для игры, поэтому она должна быть быстрой и не зависящей от случайной вероятности.

Answer 1

Вы можете использовать 2D регулярную сетку точек (P0, P1, P2, P3, ..., P (m * n), когда m - ширина, а n - высота этой сетки)

Каждая точка связана с 1) булевым выражением, если эта точка сетки использовалась или нет, и 2) «сдвиг» из этой сетки чтобы избежать слишком большой регулярности. (или вы можете поместить координаты точки + сдвига в свою сетку allready)

Тогда, когда вам нужна новая точка, просто выберите случайную точку вашей сетки, которая не использовалась, укажите эту точку как «использованную» и используйте Point + shift в вашей игре.

В зависимости от n, m, ширины/высоты вашего 2D-пространства и количества очков, которые вы собираетесь использовать, это может быть очень хорошо.

Answer 2

Сколько раз вы говорили? Если у вас есть верхний предел количества очков, вы можете сгенерировать (предварительно вычислить) массив точек и сохранить их в массиве. Возьмите этот массив и сохраните их в файле.

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

Таким образом, вы можете создать тонну различных карт, а затем произвольно выбрать одну из карт, чтобы сгенерировать свои очки.

Это работает только если у вас есть верхний предел, и вы можете докомпьютерную точки перед игрой нагрузки

Answer 3

Хранить набор точек в Kd tree. Создайте новую точку наугад, затем исследуйте ее ближайших соседей, которые можно быстро найти в дереве Kd. Если точка принята (т. Е. MIN_DIST < ближайший сосед < MAX_DIST), затем добавьте ее в дерево.

Следует отметить, что это будет работать лучше всего в условиях, когда точки не слишком плотно упакованы, т.е. MIN * N < < L где N - количество точек, а L - размер окна, в которое вы помещаете их Если это не так, то большинство новых точек будут отклонены. Но подумайте об этом, в этом пределе, вы упаковываете мрамор в коробку, и расположение не может быть очень «случайным» вообще выше определенной плотности.