網格沉思-遊戲中的網格系統

介紹

Amit Patel 撰寫過一系列有關遊戲演算法的可交互教程。本文為其六角網格系列中的一篇。

引言

用網格系統來呈現與區域相關的要素的例子在電子遊戲中不勝枚舉。

具體來說：譬如有文明系列與魔獸爭霸系列中的地圖；撞球、撞球和德州撲克中的遊戲界面；一些球類遊戲中的交互範圍；象棋，大富翁和四聯消除遊戲中的遊戲面板，抑或俄羅斯方塊用方格表示的抽象空間。

這篇文章里，我將與大家分享一些關於網格系統的思考：我將盡量避免談及實現細節（這樣就可以少來點不易理解的代碼），著力表述概念與演算法。我曾在策略類遊戲和模擬類遊戲中實現過基於網格的地圖系統，儘管網格系統能夠在遊戲的諸多方面大顯神威，但本文中只涉及我感興趣的那一部分內容。

常見的網格系統

方格

圖1. 方形網格

正方形網格自然最為常見。它直觀易用，也非常適合顯示在計算機屏幕上。當然，使用它最大的好處還在於簡單：用軸正交的 (x, y) 坐標系就能表示出每個網格的位置。即使在遊戲畫面中，網格以等軸斜視的形式呈現，也還是使用相同的坐標軸系統。

六角網格

圖2. 六角網格

有時我們也會使用六角網格（尤其是某些桌面遊戲和策略類遊戲）。相比正方形網格它有一個明顯的優勢，由於六角網格對角方向與鄰邊方向的格子等距，因此不會造成各方向的移動間出現距離偏差。此外，六角網格的樣式優雅美觀，自然界中的蜂巢就是六角網格的形狀。

三角網格

圖3. 三角網格

3d建模中會用到三角網格，但很少有人將它們用於遊戲地圖：最主要的原因是，這樣的網格系統邊很多，但每一格面積卻很少：而格子過小意味著難以完整地呈現遊戲素材。3d建模則主要使用三角網格，這是由於三角網格的每一格能保證處於同一平面中，而正方形網格與六角網格可能會扭曲成自然界不可能出現的樣子。為方便計算，本文中涉及到三角網格的數學演繹都默認三角形以某條中垂線豎直的方式放置，對於某條中垂線水平的情況則同理可證。

網格的組成要素

圖4. 網格的要素

網格有三大組成要素：面，邊與頂點。

面是由邊圍成的閉合平面；邊是以頂為端點的線段；頂點則就是零維的點。

具體到遊戲，則往往只側重於其中的某一方面：一些西方的遊戲，以國際象棋和國際跳棋為例，使用了網格中的面，而一些東方的遊戲，例如圍棋和跳棋，則使用網格中的頂。而某些遊戲，比方說俄羅斯輪盤賭博，則使用了所有這三種要素。

面，邊與頂也能呈現在多邊形地圖中。即使沒有網格坐標系統，也能對其運用相關的演算法：

圖4b. 多邊形網格依然包含三大要素

用節點表示每個面，節點連線表示鄰邊，我們就能將網格與多邊形地圖轉換為圖形拓撲結構。這樣一來，一些適用於圖的演算法（例如最小路徑演算法）就可以用於網格地圖了。

遊戲中的應用

電子遊戲對這三種要素都有所應用，其中面的應用最為普遍。

面常被用於表示建築物和地形地塊（草地，沙漠，沙礫等等），也經常被用於表示玩家所有的領地範圍；

邊常用來表示領地邊境，有時也會用在一些模擬水流，人流和貨物運輸的演算法中；

頂常用來表示海拔高度和水深等信息。

道路與鐵路網路有時會使用面來實現（以模擬人生系列遊戲為例），有時也會考慮使用邊（例如我曾實現過的這個機車系統：Road Building Applet）。

相關計算

我們來計算一下需要多少面，邊與頂點才能構成網格。

基本的思路是觀察相鄰的要素，考慮共用的情況。

先來計算相對簡單的三角網格（參見圖4）相關數據。三角形有三個邊，因此，假如不考慮共用的情況，邊的數量會是面的三倍，但每條邊都會由兩個面分享，所以每有三個邊就有兩個面；同理，三角形的頂點由六個面分享，所以每2個頂點就對應一個面。這些關係在設計坐標系統時非常重要。正方形網格中一個面對應一個頂點。六角網格中頂點則比面多。

相關的數據參見下表：

為方便起見，我們用 FEV 來表示這組數據。方形網格的 FEV 為 1，2，1；六角網格為 1，3，2；三角網格則為 2，3，1。注意，六角網格與三角網格數據很類似，只是面與頂點的數據是反過來的。這是因為六角網格與三角網格存在對耦關係：如果你在三角網格每個面的中心增加一個頂點就能得到一個六角網格，反之亦然。類似的，我們會發現方形網格與自身對耦。如果在方形網格每個面的中心增加頂點會得到另一個方形網格。相關知識可以參見：http://en.wikipedia.org/wiki/List_of_uniform_planar_tilings

六角網格與三角網格的衍生方法

可以使用方形網格來衍生六角網格或者三角網格。

你可以先嘗試一下 demo：原文。

方形網格的坐標系統非常直觀，而下面的方法則將演示如何設計六角網格與三角網格的坐標軸。

用方形網格衍生六角網格

將方形網格轉換為六角網格需要歷經兩個步驟：第一步，使方形網格豎直邊長度加倍，然後偏移某些列（當然行也可以）；第二步，劃分方形網格的邊，並將格子變形成六邊形。

圖5. 方形網格的偏移方法

這裡給出兩種偏移列的方法(參見圖5)：比如我們可以用代碼來判別列數的奇偶性，遇偶數列就將其向上偏移半格。更簡單的方法是讓每一列都相比前一列向上偏移半格，這樣坐標的計算方法能夠相對保持一致，但地圖形狀會顯得沒有那麼四四方方，略有不便，儘管如此，在本文中我還是選擇使用這套方案。它更容易實現，而且也能用於三角網格中（未來也許我也會撰寫關於第一種方案實現的教程）。

圖6. 方形網格變形為六角網格

接著，我們將原方形網格豎直方形的邊都一分為二，並以分割點為頂點彎折它們。當角度由180度達到120度時我們會得到一個正六邊形的網格。這種分割方式會增加兩條邊（平均到每個面則多了一條邊）與兩個點（平均到每個面則多了一個點），因此，FEV 由 1，2，1 變為 1，3，2。

用方形網格衍生三角網格

圖7. 方形網格轉換為三角網格

將方形網格轉換為三角網格也需經歷兩步：首先，「擠壓」方形網格讓每個格子變為菱形。接著，將菱形一分為二得到兩個三角形，分割面意味著面數會加倍，邊數平均到每個面則增加了一條，頂點數沒有變化。因此，FEV 由 1，2，1 變為 2，3，1。

坐標軸系統

我們需要用坐標來表示網格的各個要素。我先使用簡單的數字坐標來表示網格的軸，而 FEV 則能告訴我們有多少網格要素會使用相同的坐標表示。如果數字坐標數字完全相同，為會在後面加上代表方向的字母（W：西；E：東；N：北；S：南；L：左；R：右）作為補充信息。

方形網格

圖8. 方形網格的坐標系統：面，邊與頂點

方形網格非常簡單，它的 FEV 為 1，2，1，這意味著只有在表示邊時才會用到作為補充信息的字母。對於每一個面，我們可以用面的某個頂點坐標來表示它的位置，我選用了西南角的頂點坐標作為面坐標：讀者可以對比面坐標圖與頂點坐標圖來查看它們的關係。而對於每一個邊，我們都可以指定用它某一側的面的坐標來表示它的位置，我選用了西面和南面的邊，並分別用字母 W 和字母 S 表示坐標的補充信息：讀者也可以對比面坐標圖和邊坐標圖來查看它們的關係。這樣下來，有一個面，兩條邊和一個頂點使用同一坐標數字，恰好對應方形網格的要素向量 FEV。

六角網格

圖9. 六角網格的坐標系統：面，邊與頂點

我們的六角網格是基於方形網格創建的。因此六角網格的面坐標同轉換前的方形網格保持一致。對比圖8與圖9你能夠看出轉換前後的面坐標關係。我們選取三條邊與兩個頂點與面分享一樣的坐標。我選取的是 NW，N，NE 三條邊，並分別用 W，N，E 作為坐標補充信息。至於頂點，則使用 L,R 來區分是面左邊的頂點還是面右側的頂點。其他選擇方案當然也是可行的。

三角網格

圖10. 三角網格的坐標系統：面，邊與頂點

我們的三角網格也是基於方形網格創建的，並且我們把方形網格的面劃分為了兩個三角網格的面。這意味著我們需要在面坐標後加上 L，R 作為補充信息區別左右兩個面。邊的坐標與方形網格中保持一致，新增的邊則採用左下角的頂點坐標，並用字母 E 作為補充信息。由於三角網格並沒有新增頂點，所以頂點坐標與方形網格保持一致即可。

網格要素之間的關係

三大網格要素兩兩之間可以建立9組關係。還有許多其他的關係可以建立，但本文中就只研究這9組關係。我不是很熟悉該用什麼標準的術語，因此這裡可能杜撰了一些名詞(譯者按，此處的中譯也使用的是杜撰的名詞，如果有更合適的稱呼，煩請讀者告知，不勝感激)。

演算法在遊戲設計中，你實際使用的可能是上述變種之一。比方說，接壤與鄰點這兩種關係也可能會將對角線包含在內。而連續關係也可能涵蓋兩個邊不在一條直線上的情況。我有選擇性地列舉了最簡單的關係。

如下表所示，根據我列出的這9種關係，每一種都能夠寫出一組由某一要素坐標向相鄰要素坐標轉換的演算法關係(A -> B), 我簡單地將其表示為了坐標映射關係，方便讀者選擇用自己喜歡的編程語言來實現它們。由於在某些形狀的格子中，被轉換的要素可能處於不同的位置（即有多種 A 的情況），因此我將所有可能的類型都列舉了出來。例如，三角格子會有居左(L)或者(居右)兩種情況：

關係對

(本節內容可以跳過*)

上面列出了網格要素關係自身之間也存在關係。例如，由面到邊的圍邊(borders)關係與由邊到面的連接(joins)關係互為逆反。假如邊B是面A的一個相鄰邊，那麼面A也是邊B的一個相鄰面。因此，這9種關係實則可以精簡為6種關係對。(*本節內容允許跳過)

如果你為這些坐標建立了資料庫，則可以直接表示出這些關係對。比如，在1X2的方形網格中，面邊坐標關係對如下所示：

給定關係對後，查看對應的列即可。比如在上表中，坐標為 (0, 0) 的面對應著4條邊，符合圍邊(border)關係的公式表達的結果。而坐標為 (1, 0, W) 對應2個面，也符合連接(join)關係公式的結果。關係對的含義更寬泛，包含許多種對應關係；而具體到某一種關係，則會有特定的數學表達式。

既然有6種關係對，理應有12種關係才對啊，為什麼我們只列出了9種關係呢？理由是面/面關係，邊/邊關係與頂點/頂點關係是對稱的，所以其逆反就是本身，因此，12種關係中有三種關係是冗餘的，我們一共有9種要素關係。

實現

上面列出的演算法非常直觀。那麼我們如何在具體的代碼中實現它們呢？首先，你需要從三種要素坐標中選出一種來創建數據結構。我推薦選用最為簡潔透明的方式。無論哪種要素，我都會使用用整數向量 (u, v) 來表示其坐標，必要時包含L 或者 W 這樣的輔助記號。

像這樣的數據結構，如果用 Ruby 可以表示為附帶 public attrs 的類；用 lisp 的話可以表示為 list；若用 C 則struct 正好合用; 使用 Java 則可以表示為包含 public fields 的類；而假如使用的是 Python ，則表示為一個簡單的對象或者字典就好。輔助標記的畫， lisp 和 Ruby 中可以考慮用 symbol(L/:L)；C中用字元(L)或者枚舉變數(L);Java中用字元;Python中則可以用長度為1的字元串。

接下來實現我們的演算法。最簡單的當然是寫一個以 A 為參數返回值為 B 的列表的函數（或者方法）。如果 A 的情況不唯一，用 switch/case 分別處理即可。這種方法最簡單，但並不是最快的辦法。想要進一步優化，還可以考慮在調用時預先分配可能返回的列表，或者提供內聯的回調函數（比如 C++ 的 STL 函數對象）。在某些情況下，你可能會需要一次查看多個A對應的關係，這時你可能會需要設計一種能夠以A的列表為參數，返回B的列表的演算法。

我盡量避免給出具體的實現，因為這取決於每個遊戲的具體需要，但我還是在下表中列出了使用 ruby 編寫的三角網格轉換的一種範例。為選擇使用 list 作為最基本的數據結構，並且使用 Ruby symbol(:L) 來表示附帶記號。

就是這麼容易。每一個變種使用一種分支情況處理即可。

坐標轉換

無論是 2D 還是 3D 的圖形系統，我們都需要在「世界」坐標與「屏幕」坐標間相互轉換。使用網格系統後也不例外。這一節我們就來處理這個問題。從網格坐標往世界坐標轉換時，我們選取頂點或者面的中心；從世界坐標往網格坐標轉換時，我們則選取包含坐標點的面坐標，離坐標點最近的邊坐標或頂點坐標。

方形網格

方形網格的情形比較容易處理。假設方格邊長為s，且方格邊緣與x, y軸對齊，那麼只需要將網格坐標乘以s就能得到對應的世界坐標。

如果是其他情況(坐標軸沒有與網格對齊)，我們則需要確定哪個頂點是距離世界坐標最近的。只需要將世界坐標除以s再圓整(round)就能得到最近的頂點坐標。若你希望得到的不是頂點坐標而是面坐標，使用向下取整(floor)即可。

六角網格

圖11. 六角網格度量

六角網格的情形只稍微比方形網格複雜一點。計算面心很容易，參見圖11，右下角標有矢量i與矢量j。從六角網格坐標向世界坐標轉換，只需要做簡單的矩陣乘法即可，關係如下：

展開後即表示為：

x = ix * u + jx * vny = iy * u + jy * vn

如圖所示，i 即 (hexagon_narrow_width, 0.5*hexagon_height) 而 j 即 (0, hexagon_height), 將其帶入公式，結果為：

# 面心nx = hexagon_narrow_width * uny = hexagon_height * (u * 0.5 + v)n

計算頂點也相當簡單。在下文中，我會用L或R標記六邊形的頂點。這兩個頂點位於從六邊形面心往左或往右橫跨半個六邊形的寬處（具體可參見圖9），因此我們只需要加上或者減去一個 hexagon_wide_width * 0.5就能得到x坐標:

# 如果面心坐標為 (x, y), 則頂點坐標為：ncase siden when :Ln x -= hexagon_wide_width * 0.5n when :Rn x += hexagon_wide_width * 0.5nendn

在處理六角網格時，以面心坐標作為主要坐標，頂點坐標則放在相對次要的位置。

從六角網格坐標(u, v)轉換為世界坐標(x, y)也需要做一次矩陣乘法（即之前的矩陣乘法的逆運算）。這裡我直接給出計算結果：

u = x / hexagon_narrow_widthnv = y / hexagon_height - u * 0.5n

要使以上公式成立，需要將(x, y)落在面心位置上。如果(x, y)處於任意位置，還需要一點額外費一點功夫。最簡單（但並不是最高效）的方案是算出浮點坐標(u, v)後比較與其相鄰的整點坐標，看哪一個距離原來的世界坐標最近。這種方法適用於所有類型的坐標系統。用這種演算法來實現滑鼠點選，速度是足夠滿足要求的。通過查找最近的多邊形，它還能再進一步地優化。

三角網格

三角網格是經過擠壓和分割的方形網格。

將三角網格的頂點坐標轉換為世界坐標只需乘上一個軸矢量(即坐標軸的單位向量)，正如六角網格中提到的公式：

將三角網格的面坐標轉換為世界坐標則需要做一點調整。居於左下，標記為L的三角網格面心為(0.25*i, 0.25*j)，而居於右上，標記為R的三角網格面心則為(0.75*i, 0.75*j)。

由世界坐標轉換為三角頂點坐標很容易。用代數知識算出(u, v)即可。可以通過劃分左右三角網格的邊(標註為E的那條)的位置來判斷世界坐標落在了哪一個面中。如果點位於邊的左側，則點落在L面中，否則落在R面中。位於R面時，frac(u) + frac(v) >= 0.5將成立，也可以利用這個性質來判斷點在哪一側(譯註：frac(...)函數用來可以取得浮點數的小數部分)。

處理三角網格時，著重於處理頂點，面心坐標相對次要。這和六角網格中的處理方式恰好相反。

相關內容

這篇文檔是否還有什麼需要補充的內容呢？有什麼解釋得不清楚的地方嗎？還不夠完善？有謬誤之處？請反饋給我吧(原作者郵箱：redblobgames@gmail.com)。

文中使用的圖表(此處指原文)是我先用ruby寫好演算法，通過程序生成SVG格式文件，最後再使用inkscape轉換成PNG格式的。我還使用inkscape手動往某些圖表中添加了標註。我使用的ruby代碼可以在這裡找到。在原文中，你可以通過將圖片的url地址中的.png後綴改為.svg後綴來找到svg格式的文件。如果需要在其他地方使用它們，請給我發郵件（郵箱地址參見上一段）。

文章的最後，再列出一些我頗感興趣，但一時想不到用途的東西：

比如 2D 空間中的網格有五種類系，分別是：方形，三角，六角，長方形與平行四邊形，然而只有方形，三角和六角是正多邊形。漩渦蜂巢鑲嵌圖(Spiral Honeycomb Mosaic，此處鏈接為原鏈接，已損壞，這裡再提供一份鏡像鏈接)是一種有趣的為六角網格標數方式。它具有一些頗為奇特的屬性。

原文鏈接與版權說明

對原文感興趣的可以查看這裡。

indienova 獲得原作者授權同意，將陸續為大家翻譯他的其他教程，相關反饋可以提交到indienova 的遊戲開發資源小組，希望大家能給予支持和鼓勵。

推薦閱讀：