游戏地图是怎么搭起来的？

什么是波函数坍缩

《城市叠叠乐》中，玩家可以点击地图上的地块，然后地块上就会出现各式各样的小房子。每当你放置一个新的小房子，地图中某些小房子的形态会根据其周围房子的形态和位置发生变化，最终，游戏地图中的每个房子都和周围的房子形成良好的连接，这样玩家仅仅点击地块就可以很轻易的搭建一个漂亮的建筑而完全不需要注意自己将要在这一格放置什么种类的房子。

2024-06-1622-03-15-ezgif.com-video-to-gif-converter

如果我们将玩家点击地图地块的过程改为程序随机”点击“地块，每次使程序启动，我们都能获得一个不同的建筑。现在我们就得到了一种随机地图生成的方式，这种方法称为波函数坍缩（wave function collapse）。

波函数坍缩算法的原理

波函数坍缩是一个量子力学的概念，我查了一些资料，大概意思是，微观粒子的状态（位置、动量等）是不确定的，而波函数用来表示微观粒子的状态，此时微观粒子可能的出现的状态越多，称为熵越大，而波函数坍塌的过程就是粒子可能状态减少的过程，也是熵减少的过程。

上文看个乐就得了，我们游戏开发领域的波函数坍缩算法只是借用了量子力学中这个概念的思想。现在我来举个例子让我们更好的理解波函数坍缩生成随机地图的原理。

数独图片来源于Superpositions, Sudoku, the Wave Function Collapse algorithm. (youtube.com)

玩过数独吗？这是一个益智游戏，规则是，我们需要在一个9x9大小的网格中填入1~9中的某个数字，每个纵列，横行和9个3x3大格中不能出现相同的数字。我们获得胜利的方式是按规则将所有的格子填上数字。

image-20240616220043139

在一个空白的地图中，每个小格子都可能填入1~9的任意数字，也就是每个小格有可能的9种状态。

image-20240616220108550

当然，数独的地图在开始时通常不是空的，而是已经按照规则填入了一些数字，现在，一些格子的状态确定了，一些格子的状态减少了，也就是熵减少了。

image-20240616220124948

通常我们做数独的方式是选取一个熵最小的格子，填入一个可能的数尝试逐步找出可能的答案。选取熵最小的格子是因为它的状态最少，说明我们犯错的可能性和犯错后的代价最小。当我们为这个格子填入数字，这个格子的状态确定了，地图的中某些其他格子的状态也会发生相应的变化。我们不断的重复这个过程，最终就可以找到符合规则的“一个解”。

image-20240616220228180

我说我们能找到“一个解”，是因为按照规则，9x9数独地图的数字排列有6,670,903,752,021,072,936,960种方式，所以一个数独题目很有可能有多个解。

现在，把数独地图想象成游戏中的2D地图，数字想象成地图中的地块，这些地块需要以某种规则排列，比如，每个纵列，横行和3x3大格中不能出现相同的地块。我们做完了一个数独，也就生成了一张随机地图。

程序实现

然后我们就可以将这个方法运用在游戏的随机地图生成中，我用Unity来做一下具体的实现。

我们这里仅考虑简单的实现方法，也就是二维地图且地块不可旋转的情况，三围地图且允许地块旋转的情况可以在此基础上做拓展

准备素材

首先我们打开绘图软件绘制一些地块的精灵素材

Snipaste_2024-06-16_17-42-06

这里我准备了共六张精灵

image-20240616204713531

定义数据

我使用ScriptableObject作为地块的配置文件,并定义GridInfo用于传递地块信息,这里GridInfo仅存储了id，在某些情况下也可能用于存储地块的方向等，这里不做讨论

请注意GridInfo是record类型，这是C#中一种特殊的引用类型，我在这里希望使用其值相等性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using System;
using System.Collections.Generic;
using UnityEngine;

namespace Data
{
    [Serializable]
    public record GridInfo 
    {
        public int id;

        public GridInfo(int id)
        {
            this.id = id;
        }
    }
    
    [CreateAssetMenu(fileName = "Grid", menuName = "Grid")]
    public class GridData : ScriptableObject
    {
        [SerializeField] private int id;
        [SerializeField] private List<GridInfo> upNeighbours;
        [SerializeField] private List<GridInfo> downNeighbours;
        [SerializeField] private List<GridInfo> leftNeighbours;
        [SerializeField] private List<GridInfo> rightNeighbours;
        [SerializeField] private Sprite sprite;

        public int ID => id;
        public List<GridInfo> UpNeighbours => upNeighbours;
        public List<GridInfo> DownNeighbours => downNeighbours;
        public List<GridInfo> LeftNeighbours => leftNeighbours;
        public List<GridInfo> RightNeighbours => rightNeighbours;
        public Sprite Sprite => sprite;
    }
}

然后我们就可以制定地块的相邻规则，例如，草地1号上方只能是柱子、空气，左边可以是包括草地1号在内的所有的地块

image-20240616210522052

请务必注意规则一定要制定完全且正确

然后我们定义DataManager用以提供数据的全局引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

namespace Data
{
    public class DataManager : MonoBehaviour
    {
        public static DataManager Instance;
        private void Awake()
        {
            if (Instance is not null) return;
            Instance = this;
        }

        [SerializeField] private List<GridData> grids;

        public List<GridData> Grids => grids;

        public GridData GetGridDataWithID(int id)
        {
            return grids.Find(g => g.ID == id);
        }

        public List<GridInfo> GetAllInfo()
        {
            return grids.Select(grid => new GridInfo(grid.ID)).ToList();
        }
    }
}

定义地块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using System.Collections.Generic;
using System.Linq;
using Data;
using UnityEngine;

namespace Map
{
    public class Grid : MonoBehaviour
    {
        private GridInfo _info; // 即地块的确定状态，为空时说明状态未确定
        private List<GridInfo> _states;
        
        [SerializeField] private float width;
        [SerializeField] private float height;
        
        public GridInfo Info => _info;
        public List<GridInfo> States => _states;
        public SpriteRenderer TheSpriteRenderer => GetComponent<SpriteRenderer>();
        
        /// <summary>
        /// 调整地块位置，初始化状态列表
        /// </summary>
        public void Init(int x,int y)
        {
            transform.position = new Vector3(x * width, y * height);
            _states = DataManager.Instance.GetAllInfo();
        }

        /// <summary>
        /// 确定地块状态
        /// </summary>
        public void WaveFunctionCollapse()
        {
            _info = _states[Random.Range(0, _states.Count)];
            _states.Clear();
            UpdateSprite();
        }
        
        /// <summary>
        /// 更新状态列表为原列表与输入列表的交集，如果此时状态列表仅有一个状态，则地块的状态确定
        /// </summary>
        public void WaveFunctionCollapse(List<GridInfo> infos)
        {
            _states = _states.Intersect(infos).ToList();
            if(_states.Count == 1)WaveFunctionCollapse();
        }
        
        private void UpdateSprite()
        {
            if (_info is null) return;
            TheSpriteRenderer.sprite = DataManager.Instance.GetGridDataWithID(_info.id).Sprite;
        }

        public void Destroy()
        {
            Destroy(gameObject);
        }
    }
}

波函数坍缩

现在我们什么都准备好了，我们还需要定义一个类用于管理地图并调用波函数坍缩的逻辑，我在这里将此类命名为MapManager

首先，我们需要在MapManager中存储一些基本信息和数据缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using System.Collections.Generic;
using Data;
using UnityEngine;

namespace Map
{
    public class MapManager : MonoBehaviour
    {
        private Grid[,] _map; // 当前地图数据
        private readonly List<Grid> _inCollapsedGrids = new(); // 未坍缩的地块
        
        [SerializeField] private int width;
        [SerializeField] private int height;
        [SerializeField] private Grid gridPrototype; // 地块的预制体原型
        
        .../
    }
}

游戏开始时初始化地图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void Start()
{
    _map = new Grid[width, height];
    Init();
}

private void Init()
{
    _inCollapsedGrids.Clear();
    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            if(_map[i,j] is not null)
                _map[i,j].Destroy();
            var theGrid = Instantiate(gridPrototype,transform).GetComponent<Grid>();
            theGrid.Init(i,j);
            _map[i, j] = theGrid;
            _inCollapsedGrids.Add(theGrid);
        }
    }
}

进行波函数坍塌的第一步是选取目前熵最小的地块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public void CheckEntropy()
{
    if (_inCollapsedGrids.Count == 0) return;
    List<Grid> tempGrid = new(_inCollapsedGrids);

    // 将剩余的未坍缩的地块按熵大小排列，熵最小的在前
    tempGrid.Sort((a, b) => { return a.States.Count - b.States.Count; }); 

    int arrLength = tempGrid[0].States.Count;
    int stopIndex = default;

    // 将熵大于最小值的地块去除
    for (int i = 1; i < tempGrid.Count; i++)
    {
        if (tempGrid[i].States.Count > arrLength)
        {
            stopIndex = i;
            break;
        }
    }
    if (stopIndex > 0)
    {
        tempGrid.RemoveRange(stopIndex, tempGrid.Count - stopIndex);
    }
    
    //输入目前熵最小的地块
    WaveFunctionCollapse(tempGrid);
    
    //更新所有地块的状态
    UpdateState();
}

然后选取一个地块进行坍塌，并更新所有地块的剩余状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/// <summary>
/// 选取熵最小的地块进行坍塌
/// </summary>
private void WaveFunctionCollapse(List<Grid> grids)
{
    var gridToCollapse = grids[Random.Range(0, grids.Count)];
    gridToCollapse.WaveFunctionCollapse();
}

/// <summary>
/// 更新所有地块的状态，此时地块的状态有可能确定，需要更新未坍塌地块列表
/// </summary>
private void UpdateState()
{
    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            if(_map[i,j].Info is null)continue;
            
            if(i>0)
                _map[i-1,j].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).LeftNeighbours);
            if(i<width-1)
                _map[i+1,j].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).RightNeighbours);
            if(j>0)
                _map[i,j-1].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).DownNeighbours);
            if(j<height-1)
                _map[i,j+1].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).UpNeighbours);
        }
    }
    _inCollapsedGrids.RemoveAll(c => c.Info is not null);
}
}

最后提供一个用于生成调用随机地图生成算法的方法

1
2
3
4
5
6
7
8
public void CreateMap()
{
    Init();
    for (int i = 0; i < width*height; i++)
    {
        CheckEntropy();
    }
}

大功告成了，完整的MapManager定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using System.Collections.Generic;
using Data;
using UnityEngine;

namespace Map
{
    public class MapManager : MonoBehaviour
    {
        private Grid[,] _map; // 当前地图数据
        private readonly List<Grid> _inCollapsedGrids = new(); // 未坍缩的地块
        
        [SerializeField] private int width;
        [SerializeField] private int height;
        [SerializeField] private Grid gridPrototype; // 地块的预制体原型
        
        private void Start()
        {
            _map = new Grid[width, height];
            Init();
        }

        private void Init()
        {
            _inCollapsedGrids.Clear();
            for (int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    if(_map[i,j] is not null)
                        _map[i,j].Destroy();
                    var theGrid = Instantiate(gridPrototype,transform).GetComponent<Grid>();
                    theGrid.Init(i,j);
                    _map[i, j] = theGrid;
                    _inCollapsedGrids.Add(theGrid);
                }
            }
        }

        public void CreateMap()
        {
            Init();
            for (int i = 0; i < width*height; i++)
            {
                CheckEntropy();
            }
        }
        
        public void CheckEntropy()
        {
            if (_inCollapsedGrids.Count == 0) return;
            List<Grid> tempGrid = new(_inCollapsedGrids);

            // 将剩余的未坍缩的地块按熵大小排列，熵最小的在前
            tempGrid.Sort((a, b) => { return a.States.Count - b.States.Count; }); 

            int arrLength = tempGrid[0].States.Count;
            int stopIndex = default;

            // 将熵大于最小值的地块去除
            for (int i = 1; i < tempGrid.Count; i++)
            {
                if (tempGrid[i].States.Count > arrLength)
                {
                    stopIndex = i;
                    break;
                }
            }
            if (stopIndex > 0)
            {
                tempGrid.RemoveRange(stopIndex, tempGrid.Count - stopIndex);
            }
            
            //输入目前熵最小的地块
            WaveFunctionCollapse(tempGrid);
            
            //更新所有地块的状态
            UpdateState();
        }

        /// <summary>
        /// 选取熵最小的地块进行坍塌
        /// </summary>
        private void WaveFunctionCollapse(List<Grid> grids)
        {
            var gridToCollapse = grids[Random.Range(0, grids.Count)];
            gridToCollapse.WaveFunctionCollapse();
        }
        
        /// <summary>
        /// 更新所有地块的状态，此时地块的状态有可能确定，需要更新未坍塌地块列表
        /// </summary>
        private void UpdateState()
        {
            for (int i = 0; i < width; i++)
            {
                for (int j = 0; j < height; j++)
                {
                    if(_map[i,j].Info is null)continue;
                    
                    if(i>0)
                        _map[i-1,j].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).LeftNeighbours);
                    if(i<width-1)
                        _map[i+1,j].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).RightNeighbours);
                    if(j>0)
                        _map[i,j-1].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).DownNeighbours);
                    if(j<height-1)
                        _map[i,j+1].WaveFunctionCollapse(DataManager.Instance.GetGridDataWithID(_map[i,j].Info.id).UpNeighbours);
                }
            }
            _inCollapsedGrids.RemoveAll(c => c.Info is not null);
        }
    }
}

效果展示

WFC-ezgif.com-video-to-gif-converter