前言
??《我的世界》(英文名：Minecraft, 簡(jiǎn)稱: MC) 相信大多數(shù)人并不陌生糠睡，它是一款沙盒游戲，最初由瑞典游戲設(shè)計(jì)師馬庫(kù)斯·阿列克謝·泊松（別名Notch）單獨(dú)開發(fā)含友，隨后由2009年成立的瑞典公司Mojang開發(fā)并發(fā)行凳谦。玩家可以在一個(gè)隨機(jī)生成的3D(世界內(nèi)，以帶材質(zhì)貼圖的立方體為基礎(chǔ)進(jìn)行游戲挎扰。游戲中的其他特色包括探索世界囚霸、采集資源腰根、合成物品及生存冒險(xiǎn)等。（來(lái)自維基百科）
??方塊是MC的靈魂拓型。玩家的創(chuàng)意通過(guò)方塊的形式表現(xiàn)出來(lái)额嘿，游戲內(nèi)容通過(guò)方塊進(jìn)行呈現(xiàn)，方塊是組成這個(gè)世界的最小單位劣挫。玩家通過(guò)多樣化的方塊可以構(gòu)建出任何自己想構(gòu)建出的東西册养，甚至有大神已經(jīng)嘗試在MC中構(gòu)建計(jì)算機(jī)，這充分地體現(xiàn)出《我的世界》高自由度压固、高真實(shí)性的特點(diǎn)球拦。本文主要就MC中方塊存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行簡(jiǎn)要介紹，并討論其設(shè)計(jì)上的值得學(xué)習(xí)的思想和精妙之處帐我。
方塊的存儲(chǔ)
重要結(jié)構(gòu)
??方塊的存儲(chǔ)中有兩個(gè)重要的結(jié)構(gòu)坎炼，即分區(qū) (Section, 又名Chunk Section)和區(qū)塊 (Chunk, 又名Chunk Column)。一個(gè)分區(qū)是由16*16*16個(gè)方塊構(gòu)成的大立方體拦键，而一個(gè)區(qū)塊由16個(gè)分區(qū)堆疊而成谣光，方塊、分區(qū)和區(qū)塊三者的關(guān)系如圖2所示芬为√呀穑可以看到蟀悦，一個(gè)區(qū)塊共包含16*256*16個(gè) (共65536個(gè))方塊。(Chunk其實(shí)有兩重含義氧敢，MC玩家所說(shuō)的Chunk一般指的是Chunk Column日戈，也就是本文中所說(shuō)的區(qū)塊，而Mojang公司所說(shuō)的Chunk一般指的是Chunk Section).
分區(qū)
??分區(qū)中的4096個(gè)方塊每個(gè)都可能為空。如果一個(gè)分區(qū)中所有方塊都為空瑞侮，那么這個(gè)分區(qū)將被視為空分區(qū)的圆，這個(gè)分區(qū)的數(shù)據(jù)將不會(huì)被發(fā)送到客戶端。如果這個(gè)分區(qū)至少有一個(gè)方塊不為空半火，則該分區(qū)將被視為活躍分區(qū)越妈，分區(qū)的所有數(shù)據(jù)都會(huì)被發(fā)送到客戶端。分區(qū)在數(shù)據(jù)傳輸中具有不可分割的性質(zhì)钮糖。
??分區(qū)中存儲(chǔ)了4096個(gè)方塊的數(shù)據(jù)梅掠，按照方塊在分區(qū)中的相對(duì)位置存儲(chǔ)在數(shù)組中。分區(qū)的絕對(duì)位置由其所在的區(qū)塊來(lái)確定店归，也就是說(shuō)分區(qū)本身不包含該分區(qū)的絕對(duì)位置阎抒。
區(qū)塊
??分區(qū)的數(shù)據(jù)被封裝在區(qū)塊中進(jìn)行傳輸。區(qū)塊的頭部包含了區(qū)塊的和
坐標(biāo)消痛，但沒有
坐標(biāo)且叁。舉一個(gè)例子，一個(gè)區(qū)塊可以看作一棟高為256秩伞，長(zhǎng)和寬均為1的大樓逞带，
和
確定了大樓所在的地址，不存在
數(shù)據(jù)是因?yàn)榇髽潜仨毥ㄔ诘孛嫔希?img class="math-inline" src="https://math.jianshu.com/math?formula=y" alt="y" mathimg="1">默認(rèn)為0纱新，且不允許從
不為0的地方開始“建造”這棟大樓展氓，這也就解釋了為什么早期版本的MC的高度限制為256。確定了區(qū)塊的
和
也就確定了區(qū)塊中所有方塊的
和
.
??區(qū)塊需要對(duì)分區(qū)進(jìn)行組織脸爱，使分區(qū)在區(qū)塊內(nèi)的位置是可以確定的遇汞，即確定區(qū)塊中所有方塊的. 一種最簡(jiǎn)單的方案就是參考分區(qū)對(duì)方塊的做法，使用長(zhǎng)度為16的數(shù)組來(lái)存儲(chǔ)分區(qū)簿废，然而這種做法有一個(gè)缺陷勺疼，空分區(qū)也需要占用存儲(chǔ)空間。以圖3為例捏鱼，但如果直接去掉這6個(gè)空分區(qū)执庐，將所有活躍分區(qū)連續(xù)地存儲(chǔ)在長(zhǎng)度為10的數(shù)組中，那么每個(gè)活躍分區(qū)的
就被改變了导梆，雖然節(jié)約了空間轨淌，但數(shù)據(jù)都被篡改了迂烁，顯然不可行。
??開發(fā)者在區(qū)塊中增加了一個(gè)位掩碼 (bitmask)來(lái)解決這個(gè)問(wèn)題递鹉。以圖3為例盟步，首先將空分區(qū)去掉，將所有活躍分區(qū)存儲(chǔ)在長(zhǎng)度為10的數(shù)組中躏结，然后按照該區(qū)塊中分區(qū)是否為空來(lái)設(shè)置16位掩碼却盘，第個(gè)區(qū)塊為空則將掩碼的第
為置為0，反之則置為1媳拴，則圖三所示區(qū)塊的位掩碼應(yīng)為 1001101101110101. 通過(guò)位掩碼可以還原各分區(qū)在分區(qū)中的
位置黄橘，例如，掩碼中的第3個(gè)1位于掩碼的第5位屈溉，因此數(shù)組中第3個(gè)分區(qū)的真實(shí)
值為5. 這樣一來(lái)既節(jié)省了存儲(chǔ)空間塞关，又防止了數(shù)據(jù)的丟失。
調(diào)色板機(jī)制
??對(duì)于MC中的場(chǎng)景子巾，通常存在大量相同的方塊帆赢。圖1所示的場(chǎng)景便是一個(gè)最好的例子，大量的樹葉使用的是同一種方塊线梗。試想椰于，如果每個(gè)樹葉方塊都包含材質(zhì)、光線仪搔、功能等信息廉羔，這些信息就會(huì)被重復(fù)存儲(chǔ)多次。最簡(jiǎn)單的解決方案就是只存儲(chǔ)方塊的ID僻造，并將ID與方塊建立一對(duì)一的關(guān)系表憋他，這個(gè)關(guān)系表就被稱為調(diào)色板 (palette)。好比涂色游戲髓削，將一幅圖劃分為多個(gè)區(qū)域竹挡，每個(gè)區(qū)域標(biāo)記上一個(gè)數(shù)字代表該區(qū)域應(yīng)該涂上什么顏色，玩家根據(jù)數(shù)字和顏色的對(duì)應(yīng)關(guān)系完成上色立膛，其中數(shù)字和顏色的對(duì)應(yīng)關(guān)系就是調(diào)色板揪罕。
??假設(shè)樹葉方塊的大小為bytes，圖中共有
個(gè)樹葉方塊宝泵，不使用調(diào)色板進(jìn)行存儲(chǔ)需要
bytes的存儲(chǔ)空間好啰。方塊ID為long類型整數(shù)，所占空間為8 bytes儿奶，調(diào)色板中的一條記錄包含ID和方塊框往，共需
bytes，因此存儲(chǔ)
個(gè)樹葉方塊需要
bytes的存儲(chǔ)空間闯捎。使用調(diào)色板能節(jié)省的存儲(chǔ)空間為
椰弊，
時(shí)為
. 一個(gè)方塊所占的存儲(chǔ)空間遠(yuǎn)大于一個(gè)long類型整數(shù)许溅。
對(duì)比實(shí)驗(yàn)
??選用線性存儲(chǔ)和哈希存儲(chǔ)的方式與上述區(qū)塊存儲(chǔ)進(jìn)行對(duì)比。線性存儲(chǔ)即最簡(jiǎn)單粗暴的方法秉版，將每個(gè)方塊直接存儲(chǔ)在列表中贤重，方塊中包含了該方塊的位置信息. 哈希存儲(chǔ)是根據(jù)哈希函數(shù)
計(jì)算出位置的哈希值，然后將方塊存儲(chǔ)到哈希表的指定位置清焕。對(duì)比了三種存儲(chǔ)方式插入方塊并蝗、查找方塊、從磁盤讀取方塊和將方塊寫入磁盤的時(shí)間秸妥，實(shí)驗(yàn)結(jié)果如圖6所示滚停。實(shí)驗(yàn)源代碼在作者的GitHub倉(cāng)庫(kù)。
