Шта??
Помнится, когда-то я изучал исходники MP3-кодека и мало что в них понял, потому что там одна математика, а с математикой у меня плохо. Но одна деталь врезалась в память – там оперировали термином "энергия", то есть буквально обрабатывали физическую звуковую энергию.
Эта связь с настоящей физикой меня довольно-таки удивила. И вот настал второй такой момент.
Что такое волновая функция?
Я не знаю точного определения, и даже не буду искать его в википедии. Но насколько я понимаю, волновая функция описывает состояние квантовой частицы. Так как квантовый мир запутан и необычен, это состояние, пока мы о нём ничего не знаем, представляется как суперпозиция всех возможных состояний. То есть частица может одновременно быть и здесь, и там, и двигаться туда, и сюда.
Что такое коллапс волновой функции?
Как только у нас появляется хотя бы часть информации о частице, её волновая функция изменяется. Теперь это не все возможные состояния, а только те, которые возможны при наличии вот этой частичной информации. Скажем, если есть информация, что частица движется вправо, то в её возможных состояниях уже не может быть движения влево.
Таким образом, чем больше мы получаем информации о частице и среде, в которую она помещена, тем меньше у неё остаётся возможных состояний.
В конце концов, наиболее точная информация соответствует ровно одному состоянию частицы. Все остальные возможные состояния исчезают. Происходит коллапс, или схлопывание.
Что такое процедурная генерация?
В программировании часто возникают задачи вроде создать лабиринт, нарисовать дерево, построить город и т.д. Это можно сделать вручную, но потребуется много времени и усилий.
Но можно написать алгоритм, который сам построит лабиринт или нарисует крону дерева. То есть генерация контента происходит с помощью какой-то процедуры.
Например, вот так генерируется ландшафт:
Для этого используют генераторы шума, то есть случайных чисел. Результаты получаются также случайными. В случае с ландшафтом это прокатывает, но что, если нужно сгенерировать что-то более похожее на творение разума?
Скажем, нельзя с помощью шума сгенерировать лабиринт: он просто не будет похож на лабиринт в нашем представлении.
Очевидно, нужна некая специальная логика, которая будет подправлять случайные результаты таким образом, чтобы они стали нормальным лабиринтом.
Можно применять эту логику, исходя из знаний о том, как должен быть устроен лабиринт, но тогда она будет работать только для лабиринтов.
Чтобы генерировать различные структуры, не применяя специальной логики, нужен более универсальный подход.
Коллапсируй это!
Оказывается, мы можем универсально применять для практически любых задач коллапс волновой функции.
Рассмотрим вариант лабиринта со стенками. Мы можем построить лабиринт, используя 9 вариантов стенок, включая пустой квадрат:
Если мы попытаемся сгенерировать стенки случайным образом, то получим просто несостыкованные между собой, хаотично расположенные куски.
Но можно применить к этим кускам принцип волновой функции.
Каждую клетку в карте мы будем считать частицей. А у неё может быть 9 возможных состояний. Первоначально карта лабиринта пуста. Это значит, что каждая клетка карты одновременно находится в 9 возможных состояниях.
Мы можем взять произвольную клетку и схлопнуть её состояние, случайно выбрав одно из 9. Например, это будет такое состояние:
Сама по себе эта клетка уже получила единственно возможное состояние, но в то же время она повлияла на соседние клетки: слева от неё теперь может быть не любая клетка, а такая:
или такая:
То есть, клетка слева всё ещё находится в суперпозиции состояний, но количество этих состояний уменьшилось.
То же самое можно сказать про клетку сверху.
Теперь мы можем взять клетку слева или сверху, взять те состояния, которые остались в них возможны, и тоже схлопнуть их, выбрав случайное состояние.
Это приведёт к тому, что соседние с ними клетки также получат ограничение возможных состояний.
Таким образом, схлопывая клетки по одной и повторяя этот процесс с ещё не схлопнувшимися клетками, мы схлопнем всю карту и получим набор случайных клеток, но случайность каждой клетки будет зависеть от того, какие у неё соседи.
Я написал программу генерации. Вообще говоря, их уже написанных много, и саму идею я почерпнул на ютубе. Но мне не хочется ни копипастить, ни вникать в готовый код, поэтому я просто пытаюсь делать это сам, имея только общее представление.
Пока у меня получилось вот так:
Сразу скажу, что это некорректный вариант. В моём решении есть ошибки. В продолжении этого материала я приведу код программы и опишу процесс разработки.
Читайте дальше: