Синтез моделей, также известный как коллапс волновой функции или «wfc», — это названия семейства алгоритмов решения ограничений, обычно используемых в процедурной генерации , особенно в индустрии видеоигр .
Некоторые видеоигры, в которых, как известно, использовались варианты алгоритма, включают Bad North , Townscaper и Caves of Qud .
Первый пример такого типа алгоритма был описан Полом Мерреллом, который назвал его «модельным синтезом» в своей статье 2007 года i3D [1] , а также представил его на конференции SIGGRAPH 2008 года и в своей докторской диссертации 2009 года. [2] Название «коллапс волновой функции» позже стало популярным названием для варианта этого алгоритма после того, как реализация Максима Гумина была опубликована в 2016 году в репозитории GitHub под этим названием. [3] Реализация Гумина значительно популяризировала этот стиль алгоритма, и в последующие годы он стал широко использоваться и адаптироваться техническими художниками и разработчиками игр. [3]
Реализация Гумина имела ряд источников вдохновения, включая докторскую диссертацию Меррелла, идеи из квантовой механики и перенос в стиле сверточной нейронной сети . [4] [5] Популярное название алгоритма «коллапс волновой функции» происходит от аналогии, проведенной между методом алгоритма и концепцией суперпозиции и наблюдения в квантовой механике. [6] [7] Некоторые инновации, представленные в реализации Гумина, включали использование перекрывающихся шаблонов, что позволяло использовать одно изображение в качестве входных данных для алгоритма. [8]
Некоторые предполагают, что причина, по которой реализация Гумина оказалась более популярной, чем реализация Меррелла, могла быть связана с меньшей доступностью реализации «синтеза моделей», ее трехмерной направленностью или, возможно, с ограничениями вычислительных возможностей широкой публики в то время. [9]
Одно из различий между реализацией Меррелла и Гумина и «коллапсом волновой функции» заключается в решении, какая ячейка «коллапсирует» следующей. Реализация Меррелла использует подход сканирующей линии, тогда как реализация Гумина всегда выбирает в качестве следующей ячейки ту, у которой наименьшее количество возможных результатов. [10]
Алгоритм WFC или «синтеза модели» имеет несколько вариантов. [6] Реализации Гумина и Меррелла описаны ниже, а также отмечены другие варианты:
Более ранняя реализация Меррелла по сути такая же, как у Гумина, за исключением некоторых незначительных отличий.
(1) В версии Меррелла нет необходимости выбирать ячейку с наименьшим числом возможных выходных состояний для коллапса. Вместо этого принят подход сканлайн. По словам Меррелла, это приводит к более низкой частоте отказов модели без какого-либо отрицательного влияния на качество. [10] Однако некоторые комментаторы отметили, что подход сканлайн к «коллапсу» имеет тенденцию приводить к направленным артефактам. [11]
(2) Подход Меррелла выполняет алгоритм по частям, а не все сразу. Такой подход значительно снижает частоту отказов для многих больших сложных моделей; особенно в трехмерном пространстве. [10]
В апреле 2023 года Шаад Алака и Рафаэль Бидарра из Делфтского университета предложили «коллапс иерархической семантической волновой функции». По сути, алгоритм модифицирован для работы за пределами простых, неструктурированных наборов плиток. До их работы все варианты алгоритма WFC работали с плоским набором вариантов плиток на ячейку. [12]
Их обобщенный подход организует наборы плиток в иерархию, состоящую из абстрактных узлов, называемых «мета-плитками», и конечных узлов, называемых «листовыми плитками». [13] Например, на первом проходе WFC может сделать определенную плитку мета-плиткой типа «замок»; которая на втором проходе будет свернута в другие плитки на основе правила, например, плитку «стена» или «трава».
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )В 2016 году Максим Гумин представил алгоритм WFC, опубликовав репозиторий, содержащий его первоначальную реализацию. С тех пор WFC оказал глубокое влияние на технических художников и разработчиков игр, будучи принятым, адаптированным и используемым в коммерчески опубликованных и будущих проектах (Caves of Qud, Townscaper, Matrix Awakens).
В случае WFC он вдохновлен тремя отличительными, но функционально схожими алгоритмами и концепциями: синтез текстур (в частности, дискретный синтез), цепи Маркова и квантовая механика. WFC также был дополнительно вдохновлен передачей стиля сверточной нейронной сети (передача стиля CNN).
За несколько лет до этого Меррел опубликовал концептуально идентичный алгоритм синтеза моделей, хотя он не завоевал такой популярности, как WFC, возможно, из-за его меньшей доступности, сосредоточенности в основном на 3D и вычислительных требований на тот момент.
Первое отличие заключается в шаге, на котором мы выбираем ячейку и метку. Ячейки выбираются в разном порядке. Синтез модели проходит по сетке в порядке скан-линий. WFC выбирает ячейку с самой низкой энтропией.
К сожалению, этот метод может вносить направленные артефакты.
Однако, насколько нам известно, все подобные варианты алгоритма WFC работают с плоским набором вариантов плиток на ячейку.
Мы предлагаем решение этих недостатков путем введения (i) понятия мета-плитки, абстрактной плитки, которая представляет собой семантическую группу плиток, а также (ii) графоподобной структуры, которая способна представлять иерархию среди них и ограничения между ними.