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

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

上一部分講了隨機數發生器，接下來的幾部分我們來談談Minecraft是如何產生真實的生物群系邊界的。

Minecraft里目前一共有38種生物群系（數據來自Minecraft中文Wiki），每種生物群系都有自己獨特的海拔高度、表面方塊、表面植被等特徵。而如果你做為Minecraft這個遊戲的開發者，你肯定希望這些生物群系的邊界劃分是這樣的：

而不是這樣的：

生硬的地形邊界會讓玩家感覺非常不自然，讓遊戲失去可玩性（有些時候我會覺得我玩Minecraft就是圖個風景好）。

那麼問題就來了：如何生成這樣的真實生物群系邊界？Mojang的員工拿筆畫嗎？（可憐的Mojang員工）

當然不是。

一些計算機演算法可以代替可憐的Mojang員工（現在興許是微軟員工）完成這項工作。例如，Voronoi圖。它的構造過程如下：

1. 在平面上隨機取n個點，稱這些點為根，為每個點i製造一個集合Si，初始集合為空
2. 對於平面上每一個點j，找到剛才那n個點中離它距離最近的點i，將這j加入到Si裡面。（嚴密一點，若有了多個點與j距離相等，選擇編號最小的那個）
3. 經過以上步驟後，我們已經把平面劃分為了n個部分。

這n個部分看上去長這樣（你可以把每種顏色理解成不同的生物群系）：

等等，這個邊界看上去依舊筆直而僵硬啊！而且我們上一部分中提到了「隨機一定要跟著種子走」，這裡隨機取點怎麼看著那麼任性呢？

我們先來解決第二個問題。

設定一個單位長度u，將平面按照長和寬都為u的正方形劃分成小塊。我們規定，每小塊里只能有一個根點。如何決定這些根點的位置呢？我們上部分中提到了，地圖生成器的許多模塊都接受一個種子和一個坐標作為輸入。對於每個小塊k，我們同樣可以指定坐標——把每個小塊的左下角那個點的坐標兩個分量分別除以u就可以了。我們對接收到的世界種子和k的坐標做一系列確定的代數運算（注意只要是確定的，做什麼運算隨開發者心情而定，這裡只是為了讓新的種子和原來的種子儘可能不同）。根據新的種子進行兩次偽隨機生成，生成[0, u)之間的隨機數，把這兩個數作為該小塊中根點距離其左下角點的偏移。這樣我們就為每個小塊指定了一個在其內部（或邊界上）隨機位置的根點了。

注意世界種子在創建世界時是確定的，每個小塊的橫縱坐標是確定的，隨機發生器是確定的，那麼每個小塊內部根點的位置也是確定的了。同理可以進行第三次甚至更多次隨機生成，產生該根點所對應區域的顏色（生物群系）以及更多數據。

這樣其實還順便帶來一條額外的好處：所有生物群系都差不多是u*u大小的，不必擔心生物群系大小不均勻（什麼？你問我為什麼Minecraft裡面海要比陸地大很多？呃……這不是本部分的內容，以後會提到）。

不多說廢話，上代碼！(Unity3D + C#)

using System;using System.Collections.Generic;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 SimpleVoronoiRenderer : MonoBehaviour { //注意這裡的Unit代表單位長度u是2的多少次方。u是2的整數次冪算起來會比較方便 [SerializeField] private int seed_, unit_, width_, height_; private void Start() { GetComponent<RawImage>().texture = RenderVoronoiGraph(width_, height_); } //畫一張Voronoi圖 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, GetClosestColor(x, y)); } } tex.Apply(); return tex; } //獲取該點所在區域的顏色 private Color GetClosestColor(int x, int y) { int cx = x >> unit_, cy = y >> unit_, 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 dist = GetDistanceSqrFromCellRoot(x, y, ax, ay); if (dist < min_dist) { min_dist = dist; ret = GetColorOfCellRoot(ax, ay); } } } return ret; } //獲取某一個小塊的根是什麼顏色的 private Color GetColorOfCellRoot(int cell_x, int cell_y) { var rand = new Random(cell_x ^ cell_y * 0x123456 + (seed_ << 2) + 66666); return new Color((float)rand.NextDouble(), (float)rand.NextDouble(), (float)rand.NextDouble()); } //獲取圖上某一點到某一小塊的根的距離平方（沒必要開方了，我們現在只是比比大小而已） private int GetDistanceSqrFromCellRoot(int x, int y, int cell_x, int cell_y) { var rand = new Random(cell_x * cell_y + seed_ + 23333); int ox = rand.Next(1 << unit_), oy = rand.Next(1 << unit_); int dx = (cell_x << unit_) + ox - x, dy = (cell_y << unit_) + oy - y; return dx * dx + dy * dy; } }}

上圖設置參數跑出的結果：

現在的生物群系邊界看上去開始筆直的，下一部分我們介紹如何讓它們更加自然。

不過讀者們可以先自己思考一下哦！提示：多用幾次Voronoi圖。