地图程序化生成探究——波函数坍缩算法

type

status

date

slug

summary

摘要

本文主要介绍了如何在Unity引擎中使用C#脚本语言，实现了波函数坍缩算法，并在此基础上借助于部分Unity引擎中自带的预设模型资源，应用波函数坍缩算法完成了“随机生成地图”这一功能的实现。

关键字：波函数坍缩算法；随机生成；局部信息生成图案

一、引言

在游戏中，地图作为玩家游玩的场景，是游戏的核心组成要素之一。一般情况下，为了确保玩家的游戏体验，游戏的地图都是由制作团队精心设计的；但有时为了特殊的需求——例如地图随玩家的移动不断延伸、每次游玩生成不同的场景提供复玩性等——我们需要程序化地随机生成地图。面对这一需求，大多数游戏都采用了波函数坍缩算法来实现。

二、介绍用到的算法的主要思想

波函数坍缩算法本质上是一种利用利用已知的部分信息，通过一定的规则来生成图案的算法，主要分为两个核心思想：对“已知信息”的处理——即最小单元“原型（Prototypes）”的建立；和通过全局中已经确定的信息和信息之间的组合关系来限制剩下位置上信息的可能性——即“坍缩”的过程。

（1）原型的建立

为了生成图案，我们需要知道原型之间的连接关系，因此在算法的开始，我们对所有原型的每个方向表上不同标记，并通过标记的对比得到不同原型的相邻连接关系表，建立原型表。一个原型的信息包括原型的编号、所使用的模型（图片）资源、不同方向的接口标记、不同方向的可连接原型表。

（2）“坍缩”

初始状态下，因为所有位置为空，没有限制条件，每个位置都有成为任何一个原型的可能性，整个图案保持一个平稳且模糊的状态。该状态在部分位置已经确定，但剩下的位置依然都抱有一种以上可能性时也会出现。

为了打破这种模糊的平稳状态，使图案向准确的方向迭代，我们在所有未确定的位置中找到熵最低（可能性最少）的位置，随机选择其可能性中的一种原型，使该位置的可能性“坍缩”为1。因为所选位置的可能性减少，相邻的位置因为受到其限制可能性同时也减少，同时相邻的位置也会再使相邻的位置可能性减少，不断依此迭代下去，直到重新回到平稳且模糊的状态。通过不断重复此流程，我们就能获得一个平稳且准确的状态作为最终结果。

“坍缩”的作用一是在于打破平稳的中间状态，使得算法继续运行下去，得到结果；二是通过已确定的原型来限制未确定的位置，使未确定位置的可能性坍缩减少，排除错误的可能性，减少运算损耗。