Minecraft地圖生成原理剖析（三）

來自專欄 Unity3D從入門到放棄14 人贊了文章

上一部分介紹了Voronoi圖的使用，並且在文章最後我希望大家思考一下如何使用多張Voronoi圖來製造更加自然的地形邊界。本部分將揭曉這個問題的答案。

讓我們從最簡單的情況開始：兩張Voronoi圖。

在上圖中，黑色的邊使用尺寸大（即根點較為稀疏的）Voronoi圖A，將平面分為了不同的部分（圖中只展示了三部分）。紅線使用了尺寸更小（即根點更加稠密的）的Voronoi圖B，而這張Voronoi圖上的根點我們採用紅點標出。

接下來，我們做如下操作：判斷B中每一個根點在A中的顏色，並把B圖中這個根點對應的區域染成該顏色。說著有點拗口，上圖：

設想一下，我們重複上面的過程，用更小劃分的Voronoi圖繼續處理上圖，就可以得到更加細緻的邊界。事實上，大的Voronoi圖圈定了生物群系所覆蓋的大致範圍，而小的Voronoi圖則可以帶來更多邊界細節。

接下來上代碼（Unity + C#）

using System;using System.Collections.Generic;using System.IO;using System.Linq;using System.Text;using System.Threading.Tasks;using UnityEngine;using UnityEngine.UI;using Random = System.Random;namespace Assets.Scripts{ [RequireComponent(typeof(RawImage))] public class ChainedVoronoiRenderer : MonoBehaviour { //注意這裡的Unit代表單位長度u是2的多少次方。u是2的整數次冪算起來會比較方便 [SerializeField] private int seed_, width_, height_; [SerializeField] private int[] units_; private void Start() { GetComponent<RawImage>().texture = RenderVoronoiGraph(width_, height_); } private static int DistanceSqr(Vector2Int a, Vector2Int b) { return (a - b).sqrMagnitude; } //把地圖h渲染到材質上 private Texture2D RenderVoronoiGraph(int width, int height) { var tex = new Texture2D(width, height) { filterMode = FilterMode.Point }; for (var x = 0; x < width; ++x) { for (var y = 0; y < height; ++y) { tex.SetPixel(x, y, GetTextureColorAt(x, y)); } } tex.Apply(); return tex; } //獲取該點所在區域的顏色 private Color GetTextureColorAt(int x, int y) { return GetTextureColorAt(0, x, y); } private Color GetTextureColorAt(int level, int x, int y) { if (level == units_.Length - 1) { return GetClosestRootColorFrom(level, x, y); } var next = GetClosestRootPositionFrom(level, x, y); return GetTextureColorAt(level + 1, next.x, next.y); } //獲取某一個Cell的根是什麼顏色的 private Color GetColorOfCellRoot(int level, int cell_x, int cell_y) { var rand = new Random(cell_x ^ cell_y * 0x123456 + level + (seed_ << 2) + 66666); return new Color((float)rand.NextDouble(), (float)rand.NextDouble(), (float)rand.NextDouble()); } private Vector2Int GetCellRootPosition(int level, int cell_x, int cell_y) { var rand = new Random((((level ^ 0xe12345) * cell_x + cell_y) ^ 0xabcdef) + level * level + seed_ + 23333); return new Vector2Int( (cell_x << units_[level]) + rand.Next(1 << units_[level]), (cell_y << units_[level]) + rand.Next(1 << units_[level])); } private Vector2Int GetClosestRootPositionFrom(int level, int x, int y) { int cx = x >> units_[level], cy = y >> units_[level]; var min_dist = int.MaxValue; var ret = Vector2Int.zero; for (var i = -1; i <= 1; ++i) { for (var j = -1; j <= 1; ++j) { int ax = cx + i, ay = cy + j; var pos = GetCellRootPosition(level, ax, ay); var dist = DistanceSqr(pos, new Vector2Int(x, y)); if (dist < min_dist) { min_dist = dist; ret = pos; } } } return ret; } private Color GetClosestRootColorFrom(int level, int x, int y) { int cx = x >> units_[level], cy = y >> units_[level]; var min_dist = int.MaxValue; var ret = Color.red; for (var i = -1; i <= 1; ++i) { for (var j = -1; j <= 1; ++j) { int ax = cx + i, ay = cy + j; var pos = GetCellRootPosition(level, ax, ay); var color = GetColorOfCellRoot(level, ax, ay); var dist = DistanceSqr(pos, new Vector2Int(x, y)); if (dist < min_dist) { min_dist = dist; ret = color; } } } return ret; } }}

可以看出，疊加越多層Voronoi圖，邊界細節就越好。然而，這樣的演算法還是有一個很嚴重的問題：慢。如果你試一下我給的腳本配置，會發現生成一張材質需要挺久的。如果疊加層數更多，時間消耗可能會無法接受。這意味著我們在地圖生成演算法中最多用1~2張Voronoi圖疊加。剩下的部分，需要另尋他法。至於這個「他法」是什麼，我會在下一部分中講解。

通往第一部分和第二部分的傳送門：