Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 29
Напомнило www.youtube.com/watch?v=-IcFDwygw-o
Ну и до кучи www.youtube.com/watch?v=eo4u4JJAPGk
Вариантов много. Если здание многоэтажное или создаётся от большего масштаба к меньшему, то окна скорее всего уже есть. Тогда можно насоздавать комнат, а потом просто сдвинуть стены, чтобы они не упирались в центр окон. Либо убирать перекрытые окна. Про окна здесь неплохо написано.
С дверями поступают по-всякому. Либо дырявят каждую стену, потом закрывают лишние и проверяют связность с помощью A*. Либо изначально создают иерархию комнат и ставят двери только между нодами дерева. Например ветвь может выглядеть так: лифт — коридор — прихожая — ванная. Тогда все комнаты гарантированно будут доступны.
С дверями поступают по-всякому. Либо дырявят каждую стену, потом закрывают лишние и проверяют связность с помощью A*. Либо изначально создают иерархию комнат и ставят двери только между нодами дерева. Например ветвь может выглядеть так: лифт — коридор — прихожая — ванная. Тогда все комнаты гарантированно будут доступны.
Давайте прикинем. Для простоты пусть двери будут двусторонними. У вас есть полигоны с прямыми углами. Каждый отрезок на краю полигона может быть либо окном, либо дверью. Причём окно всегда идёт наружу, а между двумя комнатами может быть только дверь (пусть даже только одна). С учётом условия на отступ между окнами и дверьми (но не вместе) и неперекрытия окон дверьми, осталось только пройтись по каждому краю полигонов.
Двери и окна — это всё цветочки. Вы лучше подумайте, как весело там мебель процедурно расставлять.
Двери и окна — это всё цветочки. Вы лучше подумайте, как весело там мебель процедурно расставлять.
Одна из гифок напомнила змейку
В первой гифке в чем логика закрашивания правого нижнего угла именно таким образом?
Чёрт, заметили-таки) Включился рост угловых сегментов у двух комнат сразу, и они начали есть друг друга. Теоретически, чтобы такого не было, должна расти только одна комната за раз, а это ошибка, но я её ещё не отловил, сегодня буду допиливать генератор и разберусь.
Напоминает «В чем смысл прихода Бодхидхармы с запада»?
На анимации про поиск оболочки — рисуется невыпуклая, а ссылка ведёт на википедию о выпуклой оболочке.
Неувязочка?
Неувязочка?
Ссылка на вики это лишь отправная точка. Алгоритмы поиска выпуклых оболочек значительно проще, к тому же подобной статьи на википедии для впуклых оболочек нету. Про них можно попробовать поискать по запросу «alpha shape», это близкая тема.
Стоит об этом написать прямо в статье.
Немножко граммар-нацизма: не «впуклая», а «вогнутая» хотя бы. Ну или уже упомянутая «невыпуклая».
И всё равно, анимация не соответствует «простенькому алгоритму».
Из пятой по счёту точки, если перебирать направления вправо-вниз-влево, мы сразу же найдём восьмую по счёту точку (вправо). Но вместо этого, почему-то, полезли вниз.
Или ищется ближайшая точка? Какая метрика — манхеттенская, евклидова?
Что делать, если ближайшая точка находится не строго справа, например, а справа и чуть вверх? Где будет ступенька?
Или же алгоритм построения оболочки выдуман, а на самом деле, используется другой подход?
Вот лично я бы не парился с оболочками, а взял описывающий прямоугольник и пооткусывал из него с краёв и с углов.
Или наоборот: нашлёпал бы в пределах прямоугольной области достаточное количество прямоугольников, пока их объединение не стало бы односвязным.
Немножко граммар-нацизма: не «впуклая», а «вогнутая» хотя бы. Ну или уже упомянутая «невыпуклая».
И всё равно, анимация не соответствует «простенькому алгоритму».
Из пятой по счёту точки, если перебирать направления вправо-вниз-влево, мы сразу же найдём восьмую по счёту точку (вправо). Но вместо этого, почему-то, полезли вниз.
Или ищется ближайшая точка? Какая метрика — манхеттенская, евклидова?
Что делать, если ближайшая точка находится не строго справа, например, а справа и чуть вверх? Где будет ступенька?
Или же алгоритм построения оболочки выдуман, а на самом деле, используется другой подход?
Вот лично я бы не парился с оболочками, а взял описывающий прямоугольник и пооткусывал из него с краёв и с углов.
Или наоборот: нашлёпал бы в пределах прямоугольной области достаточное количество прямоугольников, пока их объединение не стало бы односвязным.
Я пробовал искать оболочки классическими алгоритмами, но на выходе получались непредсказуемые результаты. Поэтому я придумал свой, он описан в статье. Только первая точка ищется во все стороны, просто на всякий случай, этот код на самом деле можно удалить.
В коде есть переменная, которая в цикле направляет «поисковую бригаду» либо вверх и вниз, либо вправо и влево, в зависимости от предыдущей точки. Пятая по счёту точка была найдена при движении по оси икс, следовательно шестую точку можно найти, если двигаться по оси игрек. Никакие косые стены алгоритмом не учитываются, все углы должны быть прямые как в подавляющем большинстве комнат в реальном мире.
Расскажите поподробнее про откусывание с краёв и с углов?
запоминаем, что нашли стену, которая параллельна Y, значит следующая стена должна быть параллельна X.
В коде есть переменная, которая в цикле направляет «поисковую бригаду» либо вверх и вниз, либо вправо и влево, в зависимости от предыдущей точки. Пятая по счёту точка была найдена при движении по оси икс, следовательно шестую точку можно найти, если двигаться по оси игрек. Никакие косые стены алгоритмом не учитываются, все углы должны быть прямые как в подавляющем большинстве комнат в реальном мире.
Расскажите поподробнее про откусывание с краёв и с углов?
Углы-то пусть будут прямые, но что, если ближайшие точки — те, до которых мы интуитивно бы построили стену — находятся немного наискось?
Тут есть несколько вариантов:
— Проложить ломаную стену, — так, как это делают ортогональные соединительные линии в Visio, например; при этом надо уточнить, где именно мы будем стену ломать: с одного края, с другого, посередине, случайно…
— Просто не рассматривать эти точки. С риском не замкнуть контур или замкнуть преждевременно.
— Не рассматривать точки, но продолжить существующую стену по прямой, до тех пор, пока на перпендикулярном направлении не обнаружим точку. Естественно, тут дьявол в деталях, всякие эвристики, потому что так мы можем случайно замкнуть контур раньше времени. Например, будем обходить фигуру по часовой стрелке (как на анимации) — и рассматривать только точки по левую руку.
В отличие от алгоритмов выпуклой оболочки, которые хорошо формализованы, тут слишком много всяких выдумок и оговорок, — и это мне не нравится.
Про откусывание: ну это очень просто.
Есть два способа. Первый — это взять замкнутую ломаную (контур прямоугольника) и случайным образом наломать её, так, чтобы не возникло самопересечений. Второй — залить прямоугольник чёрным цветом и накидать на него с боков случайные белые прямоугольники меньшего размера, так, чтобы сохранилась односвязность чёрной фигуры.
Тут есть несколько вариантов:
— Проложить ломаную стену, — так, как это делают ортогональные соединительные линии в Visio, например; при этом надо уточнить, где именно мы будем стену ломать: с одного края, с другого, посередине, случайно…
— Просто не рассматривать эти точки. С риском не замкнуть контур или замкнуть преждевременно.
— Не рассматривать точки, но продолжить существующую стену по прямой, до тех пор, пока на перпендикулярном направлении не обнаружим точку. Естественно, тут дьявол в деталях, всякие эвристики, потому что так мы можем случайно замкнуть контур раньше времени. Например, будем обходить фигуру по часовой стрелке (как на анимации) — и рассматривать только точки по левую руку.
В отличие от алгоритмов выпуклой оболочки, которые хорошо формализованы, тут слишком много всяких выдумок и оговорок, — и это мне не нравится.
Про откусывание: ну это очень просто.
Есть два способа. Первый — это взять замкнутую ломаную (контур прямоугольника) и случайным образом наломать её, так, чтобы не возникло самопересечений. Второй — залить прямоугольник чёрным цветом и накидать на него с боков случайные белые прямоугольники меньшего размера, так, чтобы сохранилась односвязность чёрной фигуры.
Для пользователей Linux: Сделайте файл ProceduralExperiments.x86 исполняемым с помощью «chmod +x ProceduralExperiments.x86» и запускайте.
Подскажите, а почему бы не запаковать linux-версию в какой-нибудь формат архива, поддерживающий сохранение прав — тот же tar.gz / tar.bz2?
Дак я же всё равно на винде компилирую и запаковываю, разве там есть чему сохраняться? Вообще мне не без разницы, щас перепакую.
Упс, опечатался. Перезалил
github.com/BasmanovDaniil/ProceduralExperiments/releases/download/v0.1/ProceduralExperiments.Linux.tar.gz
github.com/BasmanovDaniil/ProceduralExperiments/releases/download/v0.1/ProceduralExperiments.Linux.tar.gz
Ну, так оно пакует все файлы с правами "-rwxrwxrwx", что тоже неидеально, но, по крайней мере, не требует дополнительных телодвижений со стороны пользователя для запуска. Я попробую спросить, как создавать на Windows tarball'ы с более правильными правами на файлах внутри — если ответят чего-нибудь хорошее — отпишу.
вот за статьи спасибо! будет что почитать ))
Вот такая картинка приводит к остановке алгоритма и 100% загрузке проца юнити плеером
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Процедурная генерация планов помещений