случайное размещение прямоугольников без перекрытий

Question

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

Я вижу два способа сделать это:

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

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

любые лучшие способы сделать это? «лучше» означает более эффективный или более визуально «случайный», чем сетка. лучше в любом отношении.

Answer 1

Простая эвристика. Он будет неперекрывающимся и случайным.

Поместите прямоугольник случайным образом. Затем вычислите пересечения расширений двух параллельных ребер первого прямоугольника с краями холста. Вы получите четыре выпуклых пустых области. Поместите другие прямоугольники в эти пустые области один за другим независимо и вычислите аналогичные подразделения для мест размещения. И попробуйте поместить оставшиеся прямоугольники в пустые области.

Вы можете попробовать различные стратегии. Вы можете попытаться поместить прямоугольники близко к углам. Или вы можете разместить их по центру регионов. Мы не можем обсуждать оптимальность, потому что вы вводили случайность.

Answer 2

Возможно, вы найдете Quadtrees или R-trees для вашей цели.

Answer 3

Я создаю внутренние комнаты, подобные темницам, используя следующий метод.

1) Разбросайте N точек произвольно, но не в нескольких пикселах друг от друга. 2) Для каждой точки, в свою очередь, раскройте, если возможно, во всех четырех направлениях. Прекратите расширение , если вы нажмете еще один прямоугольник. 3) Прекратите использование алгоритма, когда номера не могут расширяться.

В результате N прямоугольников с несколькими прямоугольными небольшими пространствами.

код в двоичной библиотеке изображений

https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/dungeongenerator3.c #