Синтез модели

Синтез моделей, также известный как коллапс волновой функции или «wfc», — это названия семейства решения ограничений, алгоритмов обычно используемых в процедурной генерации , особенно в индустрии видеоигр .

Некоторые видеоигры, в которых, как известно, использовались варианты алгоритма, включают Bad North , Townscaper и Caves of Qud .

Первый пример алгоритма этого типа был описан Полом Мерреллом, который впервые назвал его «синтезом модели» в своей статье i3D 2007 года. ^[1] а также представил на конференции SIGGRAPH 2008 года и свою докторскую диссертацию 2009 года. ^[2] Название «коллапс волновой функции» позже стало популярным названием варианта этого алгоритма после того, как реализация Максима Гумина была опубликована в 2016 году в репозитории GitHub с таким названием. ^[3] Реализация Гумина значительно популяризировала этот стиль алгоритма, и в последующие годы он получил широкое распространение и адаптировался техническими художниками и разработчиками игр. ^[3]

Для реализации Гумина было несколько источников вдохновения, в том числе докторская диссертация Меррелла, идеи квантовой механики и передача стиля сверточной нейронной сети . ^[4]^[5] Популярное название алгоритма «коллапс волновой функции» происходит от аналогии, проведенной между методом алгоритма и концепцией суперпозиции и наблюдения в квантовой механике. ^[6]^[7] Некоторые нововведения, присутствующие в реализации Гумина, включали использование перекрывающихся шаблонов, позволяющих использовать одно изображение в качестве входных данных для алгоритма. ^[8]

Некоторые предполагают, что причина, по которой реализация Гумина оказалась более популярной, чем реализация Меррелла, могла быть связана с более низкой доступностью реализации «синтеза модели», ее трехмерной направленностью или, возможно, с вычислительными ограничениями широкой публики в то время. ^[9]

Одно из различий между реализацией Меррелла и Гумина и «коллапсом волновой функции» заключается в решении, какая ячейка «коллапсирует» следующей. Реализация Меррелла использует подход со строками сканирования, тогда как реализация Гумина всегда выбирает в качестве следующей ячейки ту, которая имеет наименьшее количество возможных результатов. ^[10]

Описание

Алгоритм WFC или «синтеза модели» имеет несколько вариантов. ^[6] Реализации Гумина и Меррелла описаны ниже, а также отмечены другие варианты:

реализация Гумина

Входное растровое изображение считывается и подсчитываются шаблоны, присутствующие в нем.
Создается массив с желаемыми размерами выходных данных.
Каждая ячейка массива инициализируется в «ненаблюдаемом» состоянии.
Следующие шаги повторяются:
1. Ячейка с наименьшим количеством возможных выходных состояний расположена
2. «Свернуть» эту ячейку в одно из возможных ее состояний согласно правилам
3. Убедитесь, что все ячейки действительны и соблюдайте правила.
Как только все ячейки «свернутся» в определенное состояние, верните вывод. Если выходные данные незаконны, отбросьте их и повторяйте процесс до тех пор, пока они не станут законными.

Реализация Меррелла

Более ранняя реализация Меррелла по существу такая же, как и реализация Гумина, с некоторыми небольшими отличиями.

(1) В версии Меррелла нет необходимости выбирать для свертывания ячейку с наименьшим количеством возможных выходных состояний. Вместо этого применяется подход, основанный на строке сканирования. По словам Меррелла, это приводит к снижению частоты отказов модели без какого-либо негативного влияния на качество. ^[10] Некоторые комментаторы, однако, отметили, что подход к «схлопыванию» по линиям развертки имеет тенденцию приводить к направленным артефактам. ^[11]

(2) Подход Меррелла реализует алгоритм порциями, а не все сразу. Этот подход значительно снижает частоту отказов для многих больших сложных моделей; особенно в 3D пространстве. ^[10]

События

В апреле 2023 года Шаад Алака и Рафаэль Бидарра из Делфтского университета предложили «коллапс иерархической семантической волновой функции». По сути, алгоритм модифицирован, чтобы работать не только с простыми неструктурированными наборами плиток. До их работы все варианты алгоритма WFC работали с плоским набором вариантов плитки для каждой ячейки. ^[12]

Их обобщенный подход организует наборы плиток в иерархию, состоящую из абстрактных узлов, называемых «мета-тайлами», и завершающих узлов, называемых «листовыми плитками». ^[13] Например, при первом проходе WFC может сделать определенный тайл мета-тайлом типа «замок»; которые при втором проходе будут свернуты в другие плитки в зависимости от правила, например, плитка «стена» или «трава».

Ссылки

^ Меррелл, Пол (апрель 2007 г.). «Синтез модели на основе примеров» (PDF) . I3D '07: Материалы симпозиума 2007 г. по интерактивной 3D-графике и играм : 105–112. дои : 10.1145/1230100.1230119 . ISBN 978-1-59593-628-8 .
^ Меррелл, Пол (2009). Синтез модели (PDF) . Чапел-Хилл. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Jump up to: ^а ^б Алака, Шаад; Бидарра, Рафаэль (2023). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . Основы цифровых игр 2023 (FDG 2023) . п. 2. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . В 2016 году Максим Гумин представил алгоритм WFC, опубликовав репозиторий, содержащий его первоначальную реализацию. С тех пор WFC оказал глубокое влияние на технических художников и разработчиков игр, будучи принятым, адаптированным и использованным в коммерческих и будущих проектах (Caves of Qud, Townscaper, Matrix Awakens).
^ Меррелл, Пол (6 августа 2023 г.). Процедурное моделирование с использованием грамматик графов (Видео). Событие происходит в 3:13.
^ «Реализация коллапса волновой функции и разделения двоичного пространства для процедурной генерации подземелий» . Шаан Хан . 21 марта 2021 г. Проверено 24 марта 2024 г. В случае WFC он основан на трех различных, но функционально схожих алгоритмах и концепциях; Синтез текстур (в частности, дискретный синтез), цепи Маркова и квантовая механика. WFC также был вдохновлен передачей стилей нейронной сети свертки (CNN Style Transfer).
^ Jump up to: ^а ^б Гумин, Максим (сентябрь 2016 г.), Алгоритм коллапса волновой функции , получено 24 марта 2024 г.
^ «Алгоритм коллапса волновой функции объяснен очень ясно» . Роберт Хитон . Проверено 24 марта 2024 г.
^ Гумин, Максим (сентябрь 2016 г.), Алгоритм коллапса волновой функции , получено 25 марта 2024 г.
^ Алака, Шаад (2023). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . Основы цифровых игр 2023 (FDG 2023) . п. 2. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . За несколько лет до этого Меррел опубликовал концептуально идентичный алгоритм синтеза моделей, хотя он не прижился так сильно, как WFC, возможно, из-за его меньшей доступности, основной направленности на 3D и требований к вычислениям на тот момент.
^ Jump up to: ^а ^б ^с Меррелл, Пол (28 июля 2021 г.). «Сравнение синтеза модели и коллапса волновой функции» (PDF) . Первое отличие заключается в том, что мы выбираем ячейку и выбираем метку. Ячейки выбираются в другом порядке. Синтез модели проходит по сетке в порядке развертки. WFC выбирает ячейку с наименьшей энтропией.
^ ДВ Ген (17 апреля 2023 г.). Процедурная генерация с коллапсом волновой функции и синтезом модели | Журнал разработчиков Unity (видео). Событие происходит в 15:13. К сожалению, этот метод может привести к появлению артефактов направленности.
^ Алака, Шаад; Бидарра, Рафаэль (апрель 2023 г.). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . стр. 1–10. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . Однако, насколько нам известно, все такие варианты алгоритма WFC работают с плоским набором вариантов плитки для каждой ячейки.
^ Алака, Шаад; Бидарра, Рафаэль (апрель 2023 г.). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . стр. 1–10. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . Мы предлагаем решение этих недостатков, вводя (i) понятие мета-тайла, абстрактного тайла, который представляет семантическую группу тайлов, а также (ii) графоподобную структуру, которая способна представлять иерархию между ними и ограничения между ними.

Внешние ссылки

https://github.com/mxgmn/WaveFunctionCollapse

Эта о программном обеспечении статья незавершена . Вы можете помочь Википедии, расширив ее .

Эта видеоиграм, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

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

[1] Меррелл, Пол (апрель 2007 г.). «Синтез модели на основе примеров» (PDF) . I3D '07: Материалы симпозиума 2007 г. по интерактивной 3D-графике и играм : 105–112. дои : 10.1145/1230100.1230119 . ISBN 978-1-59593-628-8 .

[2] Меррелл, Пол (2009). Синтез модели (PDF) . Чапел-Хилл. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[:0-3] Jump up to: ^а ^б Алака, Шаад; Бидарра, Рафаэль (2023). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . Основы цифровых игр 2023 (FDG 2023) . п. 2. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . В 2016 году Максим Гумин представил алгоритм WFC, опубликовав репозиторий, содержащий его первоначальную реализацию. С тех пор WFC оказал глубокое влияние на технических художников и разработчиков игр, будучи принятым, адаптированным и использованным в коммерческих и будущих проектах (Caves of Qud, Townscaper, Matrix Awakens).

[4] Меррелл, Пол (6 августа 2023 г.). Процедурное моделирование с использованием грамматик графов (Видео). Событие происходит в 3:13.

[5] «Реализация коллапса волновой функции и разделения двоичного пространства для процедурной генерации подземелий» . Шаан Хан . 21 марта 2021 г. Проверено 24 марта 2024 г. В случае WFC он основан на трех различных, но функционально схожих алгоритмах и концепциях; Синтез текстур (в частности, дискретный синтез), цепи Маркова и квантовая механика. WFC также был вдохновлен передачей стилей нейронной сети свертки (CNN Style Transfer).

[GitHub-Gumin-6] Jump up to: ^а ^б Гумин, Максим (сентябрь 2016 г.), Алгоритм коллапса волновой функции , получено 24 марта 2024 г.

[7] «Алгоритм коллапса волновой функции объяснен очень ясно» . Роберт Хитон . Проверено 24 марта 2024 г.

[8] Гумин, Максим (сентябрь 2016 г.), Алгоритм коллапса волновой функции , получено 25 марта 2024 г.

[9] Алака, Шаад (2023). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . Основы цифровых игр 2023 (FDG 2023) . п. 2. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . За несколько лет до этого Меррел опубликовал концептуально идентичный алгоритм синтеза моделей, хотя он не прижился так сильно, как WFC, возможно, из-за его меньшей доступности, основной направленности на 3D и требований к вычислениям на тот момент.

[Merrell2021-10] Jump up to: ^а ^б ^с Меррелл, Пол (28 июля 2021 г.). «Сравнение синтеза модели и коллапса волновой функции» (PDF) . Первое отличие заключается в том, что мы выбираем ячейку и выбираем метку. Ячейки выбираются в другом порядке. Синтез модели проходит по сетке в порядке развертки. WFC выбирает ячейку с наименьшей энтропией.

[11] ДВ Ген (17 апреля 2023 г.). Процедурная генерация с коллапсом волновой функции и синтезом модели | Журнал разработчиков Unity (видео). Событие происходит в 15:13. К сожалению, этот метод может привести к появлению артефактов направленности.

[12] Алака, Шаад; Бидарра, Рафаэль (апрель 2023 г.). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . стр. 1–10. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . Однако, насколько нам известно, все такие варианты алгоритма WFC работают с плоским набором вариантов плитки для каждой ячейки.

[13] Алака, Шаад; Бидарра, Рафаэль (апрель 2023 г.). «Коллапс иерархической семантической волновой функции» . Материалы 18-й Международной конференции по основам цифровых игр . стр. 1–10. дои : 10.1145/3582437.3587209 . ISBN 978-1-4503-9855-8 . Мы предлагаем решение этих недостатков, вводя (i) понятие мета-тайла, абстрактного тайла, который представляет семантическую группу тайлов, а также (ii) графоподобную структуру, которая способна представлять иерархию между ними и ограничения между ними.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]