На GitHub выложили проект, генерирующий тайловые карты на основе одного фрагмента с применением идей квантовой механики

Вчера на GitHub появился проект, генерирующий битовые (и тайловые) карты, который сразу привлёк значительное внимание пользователей Reddit. Выглядит действительно круто, и мы решили разобраться, что же делает этот проект, и как он работает.

В качестве входных данных для алгоритма используется небольшая картинка, на основе которой создаётся похожее изображение произвольного размера. Самое главное, что привлекает внимание именно к этому проекту — то, насколько разнообразными могут быть итоговые изображения. Показать, что именно происходит, проще, чем рассказывать:

Сходство получаемых изображений с исходными гарантируется всего двумя правилами:

• Каждая область размером N*N пикселей в выходном файле должна хоть раз встречаться в исходном. N задаётся в параметрах генерации, в примерах выше обычно равняется трём.
• Частота, с которой встречается каждая из таких областей в выходном файле, должна быть примерно равна частоте, с которой эта область встречается в исходном. Т. е., другими словами, чем чаще область встречается в образце, тем чаще она будет встречаться и в сгенерированном изображении.

Соблюдение этих условий достигается сложным алгоритмом, основанным на суперпозиции каждой части N*N выходного изображения, прочитать про который можно в Readme проекта на Github. В целом алгоритм можно сравнить с разгадыванием судоку — поле делится на чанки размером N*N и каждый из них определяется в зависимости от своих соседей.

Алгоритм был вдохновлён квантовой механикой, однако по целому ряду причин (например — действительные коэффициенты, вместо комплексных) нельзя считать, что именно квантовые алгоритмы используются для генерации карт. В комментариях на Reddit даже нашёлся PhD (доктор наук) по физике, который предостерёг читателей от изучения квантовой механики на основе этого проекта. С его точки зрения, этот алгоритм было бы правильнее называть Байесовским выводом, чем редукцией фон Неймана (Wave function collapse), как указано в его названии.

На странице проекта так же выложена визуализация процесса генерации:

Алгоритм применим так же для создания изображений в высоком качестве и 3D моделей (однако отличается весьма низкой производительностю, при подобной работе):

Подробнее о проекте можно прочитать на его странице на GitHub.