Алгоритм автоматического распределения объектов по области?

Question

[Lopus]

Задана прямоугольная область определенной ширины и высоты. Например, 300х200 ячеек. В коде это двумерный массив map[x][y].
Так же заданы несколько объектов с меньшей площадью. 5х3, 2х2, 10х7 и т.д.
Необходимо их расположить в случайном месте на прямоугольнике. Из серии стол, стул, шкаф в комнате.
Подскажите, какие алгоритмы для этого понадобятся?
Подойдет любой самый простой для понимания. Пусть даже медленный с точки зрения оптимизации и неуклюжий.
Хочу для начала саму идею реализации понять.

Comments

[Антон Р.]

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

[Сергей Водаков]

Из серии стол, стул, шкаф в комнате.

Алгоритм может стать сильно сложнее, если на расположение объектов есть определенные ограничения, как то: шкаф всегда вдоль стены, стул, возле стола и т.п.
А так, самый медленный и неуклюжий, это делаем обход матрицы, и смотрим, есть ли достаточное количество свободных мест для размещения объекта, если есть - размещаем, т.е. помечаем места как занятые.

[Lopus]

Алгоритм может стать сильно сложнее, если на расположение объектов есть определенные ограничения, как то: шкаф всегда вдоль стены, стул, возле стола и т.п.

я это понимаю. на данном этапе это не так важно

делаем обход матрицы, и смотрим, есть ли достаточное количество свободных мест для размещения объекта

получается, надо так же хранить копию матрицы, но с занятыми ячейками? а при добавлении объекта искать случайную пустую ячейку и проверять каждую последующую в цикле (позиция X+1) на всю ширину объекта и так по всей высоте объекта (позиция Y+1) ?

[dollar]

Lopus, да

Answer 1

[dmshar]

Все элементарно.
Цикл в цикле.
Внешний цикл генерируете произвольную точку на плоскости (ну, например, генерируя случайное число в диапазоне размеров вашей плоскости по ширине и высоте)
Пробуете поместить центр очередного объекта в эту точку.
Получилось - отлично, продолжаем внешний цикли.
Не получилось (из-за того, что либо вышли за пределы плоскости, либо перекрылись с ранее размещенной фигурой) - тут два варианта вам на выбор. Либо сдвиг текущего объекта (и снова проверка возможности), либо возвращаемся к пункту случайной генерации позиции.
И так, пока не переберете все объекты.
Не удалось разместить все объекты - возвращаетесь на несколько объектов назад (или на все) и повторяете основной процесс.

Это самый тривиальный алгоритм. Разберетесь с ним - потом можно будет переходить к всякого рода оптимизациям - начиная с того, что бы объекты для размещения брать от самого большого к самому малому.

Answer 2

[xmoonlight]

Самый простой алгоритм:
1. По кругу, начиная с углов, от максимальной площади к минимальной.
2. При появлении "ямы" - проверка на её замощение фигурой с той же площадью: есть - замощение ею, нет - переход к следующей фигуре в п.1 с меньшей площадью.