9 posts tagged with "Hakoniwa"

前情提要​

• TKOH (The Key Of Huanche) 是我的一個 side project
  • 目前最大的 side project
  • 更多細節請見：文件或是 Wiki
• Hakoniwa 是我的一個 side project
  • TKOH 的子專案
  • 更多細節請見：文件或是 Wiki
• Polis 是我的一個 side project
  • Hakoniwa 的子專案
  • 更多細節請見之前發過的文章
  • 上次的開發日誌（進度與回顧）

進度​

先講結論，今天 (2024-08-31) 我終於把這幾個要素組裝在一起了：

• Three.js
• 後端渲染/無頭 (Headless) 渲染
• ECS (Entity Component System)
• 開發用瀏覽窗口

實作：https://github.com/FlySkyPie/polis-node/commit/aca8f24012848de30bef2b17cd07c1f2b32fc53b

技術選擇與技術堆疊的困難​

3D x Javascript​

不論是在工作上還是 side project，我其實經歷不少機會去使用不熟悉的語言，因此我意識到在原型開發 (Prototyping) 這一目標上，熟悉語言的經驗有時候能夠彌補語言特性帶來的缺陷，舉例來說：使用熟悉的語言因此知道某些需求需要使用特定的實作或是對於某些需求基於語言限制必須要使用某種 by pass；比起使用不熟悉的語言而在未知中摸索甚至踩到語言特性的坑。時間並沒有使用在開發上反而花在學習與試錯。

用 Javascript 來寫 3D 的東西聽起來很反直覺，但是我手上有的卡牌就是：

• 接近 4 年的前端 (Javascript/Typescript) 開發經驗
• 工作或業餘經手過超過 5 個以上的 Three.js 專案

比起重新學習另外一種技術棧 (Tech Stack)，使用熟悉的工具不只可以加速開發，更可以在過程中累積的經驗值回過來貢獻在工作上使用的技能。

不過這是基於我的手牌採取的遊戲策略，並不見得適合其他人。

後端 X 3D (Three.js)​

很明顯的，WebGL 是為了網頁瀏覽器而生的東西，而 Three.js 更是建立在此之上的抽象層，本身並不支援在 Node.js 這樣的後端環境執行。舉例來說，在 Web API 的設計之中 WebGLRenderingContext 是和 <canvas> 元素榜定的，但是後端的環境中根本沒有 DOM 實做 <canvas>。

另外一個問題是後端環境是無頭 (headless) 的，在缺乏視覺反饋的情況下，很難對程式進行 debug，因此一個可以「窺見」程式內 3D 渲染結果的手段是十分必要的。

開發用瀏覽窗口​

「如何窺見 3D 的後端程式」這件事情產生另外一個問題，就是如何實現快速（低延遲）的向外串流？

為了避免開發與維護另外一個讀取並顯示串流的 Client 端，基於 Web 的方案對我而言是相對合理的。於是就得出了「使用 WebRTC 來串流用於 debug 的畫面」這個結論。

ECS x Three.js​

ECS 是我計畫用來管理複雜遊戲環境的架構，不過當它需要跟其他函式庫組合使用就會產生一些問提，諸如：

• Three.js
• Rapier.js

原因在於大部分的 Javascript ECS 實現把重心放在「密集的資料」這個 ECS 特性，因此這些函式庫只能用來儲存諸如浮點數、整數之類的基本資料型別，並不能方便的和其他基於 OOP 邏輯的函式庫組合使用，使用那些 ECS 函式庫的邏輯再現其他函式庫的功能顯得不合乎成本。

回顧​

串流​

串流算是第一個急著解決的問題，畢竟就算我能在後端渲染的東西，只要不能把畫面丟出來我就不能 debug。

在考慮了 FLV (Flash Video), RTMP (Real-Time Messaging Protocol), HLS (HTTP Live Streaming) 和 MPEG-DASH (Dynamic Adaptive Streaming over HTTP) 等方案之後，我選擇使用 WebRTC。

考慮延遲以及瀏覽器支援兩個要素下，WebRTC 都是一個比較合理的方案。

瀏覽器上的 Javascript 並沒有能力建立 TCP Socket，大部分網路連線需求都是由 HTTP 完成，即便是 WebSocket 實際上也是建立在 HTTP 連線之上。而 WebRTC 則是會由瀏覽器實做，實際上會依情況使用 TCP 或 UDP 連線。在這先天特性之下，WebRTC 能夠比其他基於 HTTP 的手段來得低延遲。

去年 (2023) 在我短暫的學習串流相關技術之後，

• Node-Media-Server-ts
  • 學習 RTMP 的中間產物。

我使用 WebRTC 寫了一個小範例。

• WebRTC 學習筆記

後端渲染​

網路上關於如何在後端 (Node.js) 渲染 Three.js 的方案並沒有很多，其中還不乏用重新實做 WebGL 兼容界面然後用 CPU 算圖的方法。甚至一度考慮使用 Deno，不過最後也做罷了，這些細節在我前一篇文章都有紀錄。

在 2023-08-16 的時候我試著用 Electron 實做伺服器，

• Electron 學習筆記 - IPC

不過把資訊從 Browser 在 Node.js 之間轉發是一件很麻煩的事情，大大的提高了程式的複雜度。引此在完成測試之後就沒有什麼進展了。

之後 (~2024-08) 有試著嘗試了這裡提供的範例：

SSR - Three.js Tutorials

它使用 headless-gl 實現後端渲染，不過它的前置作業相對複雜，除了要用 jsdom 補足 DOM 的實作之外，光是安裝套件就要處理 node-gyp 帶來的一些問題，因此沒有完全說服我使用它。

我在網路上瞎逛的時候發現了 node-3d/3d-core-raub，它提供另外一種簡單粗暴的解法：把 GLFW binding 到 Node.js 上去再加上 Three.js 的兼容實作。能夠在 Linux 開啟一個視窗顯示渲染結果更是大大的減少專案初期的阻礙。

跟線有的 WebRTC 實作整合之後，確發現畫面不太正常，起初我以為是延遲的問題，於是想在裡面 Three.js 裡面放個時鐘，沒想到卻是另外一個坑。

Three.js x Text​

在 Three.js 裡面渲染文字並不是一個被非常重視的功能，因為瀏覽器上已經有 HTML + CSS 這樣一個方便顯示文字的方法了。

在經過一番折騰之後，我得到了一個像這樣的問題清單：

• three-bmfont-text
  • 沒有型別定義
  • THREE is not defined
• troika-three-text
  • 仰賴 XMLHttpRequest 和 window.document
• TextGeometry
  • 花費 60ms 建立新的 Geometry
• three-spritetext
  • 仰賴 ctx.measureText
  • TypeError: ctx.measureText is not a function
• three-text2d
  • TypeError: Class constructor Object3D cannot be invoked without 'new'
  • build target 的語法過於老舊造成
  • 仰賴 document
• three-mesh-ui
  • ctx.canvas.width = 1;
  • TypeError: Cannot set properties of undefined (setting 'width')

在電腦圖學中（特別是 3D 遊戲領域），有一門叫做 Texture Atlas 的技術，就是把文字先烘培成貼圖與幾何資訊，在程式中再把這兩者組合起來在顯示卡的 context 中顯示文字。

這個過程需要仰賴額外的工具（例如：Angelcode’s bmfont），或是由遊戲引擎內建的工具承擔（例如：Unity3D, Godot），因此在 Three.js 開發圈更常用的手段是在 runtime 時產生這些貼圖，而過程仰賴瀏覽器的渲染引擎對文字進行運算及排版，而使用這種手段的函式庫會無法在後端 (Node.js) 環境中使用。

這麼一看 three-bmfont-text 似乎是最有潛力的選擇，最後我透過：

• 使用 Typescript 重構
  • https://github.com/FlySkyPie/three-bmfont-text
• 使用 SilenceLeo/snowb-bmf 製作與輸出該 three-bmfont-text 要求的檔案格式（貼圖與幾何資訊）。

解決了問題並且完成一個數位時鐘的實作：

• https://github.com/FlySkyPie/three-digital-clock

ECS​

在正式開始之前，我選擇了一個小題目來練手：

• ECS 學習與 aimAndShoot 重構之旅

其實原本想再練一個題目的，

• https://github.com/FlySkyPie/three-fps-ts

只是從 mohsenheydari/three-fps fork 之後用 Typescript 重構、更新 Ammo.js 之後，發現它的實作邏輯有點複雜（物件互相呼叫的時序），就暫時放棄嘗試把它轉成 ECS 了。

Monorepo​

試著使用 pnpm 提供的 monorepo 功能來整合前後端的專案，大大的提高了開發體驗。沒有使用 nx 的原因是它看起來配置較為複雜，學習成本是一個阻礙。

下一步​

Logger 系統的改善​

在目前的程式碼之中有一些我為了 debug WebRTC 保留下來的 log 點，我想把它們移到 winston 或 pino 之類的專門函式庫去。

畢竟在後端環境中，未來還要面對更複雜的遊戲實作，這樣的機制來紀錄並整理 log 是非常必要的。

自由的觀戰者​

目前觀戰者並沒有移動能力，需要透過 requestPointerLock 之類的手段錨定滑鼠來提供 FPV (First Person View) 的瀏覽體驗。

整合 Voxel 實作​

既然前置作業已經完成，我就可以把我之前 Fork 的 Voxel 實作整合過來了：

• https://github.com/FlySkyPie/MC.js-Alpha

這個問題一直佔用我的大腦資源，然而目前我正在忙於其他 Side Project，無心處理這個問題，所以我想寫一篇文章先把這堆東西倒出去，讓腦根子清靜一點，日後再回頭來處理。

這是 Polis 預計使用的架構：

因為 Canvas 提供一個 captureStream() 方法允許把 Canvas 的畫面轉換成 MediaStream 物件，而 MediaStream 又能夠抽出 MediaStreamTrack 透過 WebRTC 的 API 串流出去。

但是最近我發現一個問題，就是 WebGL (Three.js) 存在一些限制：

一個 WebGLRenderingContext 被綁定到一個 Canvas

而 GL context 之間是無法互通的，因此複數個 Canvas 無法共用同一組 GPU Context。

前情提要​

• Tellus 是環驅之鑰下的子專案，專案目的為「建立儲存 Voxel 世界資料的系統」。
• 2021 年的時候，我受到 MBTiles 的啟發寫了一個基於 SQLite 檔案的 Voxel 儲存格式¹。

背景​

最近 （2024 二月）買了 TerraTech ，玩著玩著、在遊戲內轉著方塊，突然靈光一閃，想要處理旋轉方向的資料格式問題。

原本（2021 年寫的那份格式）我打算採取儲存 Voxel 的格式是用任意無損壓縮的點陣圖檔來儲存，舉例來說一個 16×16×16 Chunk 的資料會長得像這樣：

也就是一個 Pixel 等於一個 Voxel，但是這種方式單純是把一個 Voxel 當成一個像素點紀錄，無法支援像 Minecraft 那樣方塊有方向性的情況。

儲存的哲學​

我無意針對儲存 Voxel 資料去創造一個二進制文件的定義，而是使用一般的點陣圖檔，其原因源自於 Unix 哲學²：

Store data in flat text files.

二維點陣圖檔是一種常見且十分普及的資料格式，不論是透過圖形化界面的軟體還是函式庫，對其進行讀寫都是一件簡單的事情，我認為在這個意義上它與「純文字檔案」無異，而且具有更好的資料密度（壓縮率）。

在這個基礎上，我打算拿 8 個 Pixels 來描述一個 Block，令其中夾帶「方塊方向」的資訊，就結果而言可能過於浪費記憶體，不過作為一個（預計）遊戲的開發者，資料儲存的效率不是我當下最在意的事情，況且不少點陣圖片的檔案格式就有各自的無損壓縮演算法了，這個想法的基礎同樣來自 Unix 哲學²：

Make each program do one thing well.

單位晶胞​

單位晶胞 (Unit cell) 是固態物理學使用的一種概念，與之相對的是另外一個名為晶格 (Crystal Lattice) 的概念：

晶格是討論的結晶材料時候的最小單位，因為我們可以從它的結構與方向去探討這些參數如何影響宏觀特性，但是當我們把它切得更小會得到一個可以透過旋轉而構成晶格的最小不重複單元，那就是單位晶胞。

於是我把原本設計的資料格式再往下切割，用 8 個 Voxels 去構成一個 Block：

透過解析 8 個 Pixels 的排列模式就能定義出一個 Block 不同的旋轉方向。

次生 Voxel​

接下來我會明確的區分這三個用語：

• Pixel
  • 二維空間的色點。
• Voxel
  • 三圍空間的色點，沒有方向性。
• Block
  • 由 8 個 Voxel 構成的方塊，有方向性。

對於一個 3 Bytes 的像素空間而言（RGB 三個頻道個佔 1 個 Byte），能夠表達的 Voxel 種類其實足夠可觀了，即便拿 8 個排列組合來描述一種 Block 也綽綽有餘：

$$\frac{2^8 \times 2^8 \times 2^8 }{8} = \frac{256 \times 256 \times 256}{8} = 2,097,152$$

假定一個 Block 的基礎 Voxel 值為 #000000，為了描述其方向而衍生的 7 個 Voxel 則為次生 Voxel：

• #000001
• #000002
• #000003
• #000004
• #000005
• #000006
• #000007

旋轉模式​

不同旋轉模式所需要的次生 Voxel 數量並不相同，目前我定義了幾種模式：

• 固體 (Solid)
• Y 軸對稱 (XZ-Reflection / Y-Symmetric)
• Y 軸旋轉
• Y 軸旋轉對稱 (Y-Symmetric-Rotation)

固體 (Solid)​

只需要 1 個次生 Voxel，只有 1 種排列組合（方向性），類似 Minecraft 的石頭 (Stone)。

Y 軸對稱 (XZ-Reflection / Y-Symmetric)​

我不確定稱它為「 Y 軸對稱」還是「XZ 平面對稱」比較精確。需要 2 個次生 Voxel，有 2 種排列組合（上與下），類似 Minecraft 的半磚 (Slab)。

Y 軸旋轉​

需要 4 個次生 Voxel，有 4 種排列組合（東南西北），類似 Minecraft 的儲物箱 (Chest)。

Y 軸旋轉對稱 (Y-Symmetric-Rotation)​

需要 8 個次生 Voxel，有 16 種排列組合（東南西北×上下），類似 Minecraft 的階梯角 (Corner Stairs)。

Demo​

為了呈現這個概念，我寫了一個編輯器，因為只是演示作用，不保證可靠性：

• Live Demo
• 程式碼

另外，在這個 Demo 中我試著嘗試了幾個之前沒用過得東西：

• Tailwind
  • 因為有幾個同事很喜歡用，所以我想試試看這東西建構 Prototype 的速度如何。
• PrimeReact
  • MUI 用習慣了，試試其他 Component 庫建構 Prototype 的速度如何。
• React Hook Form
  • 之前寫了一份 React 問卷，發現我沒有用過表單管理套件，趁著這個專案摸摸看。
• Dexie.js (React Hook)
  • 因為前一陣子研究 TiddlyWiki 的時候得知 PouchDB 這類東西，對前端儲存方案有些興趣就趁著這個專案摸摸看了。
• Presite
  • 久違的想試試看預渲染 (pre-render)，不過 react-snap 貌似壞掉了（不支援 React 18），就找了個類似的替代品。

Footnotes​

1. Voxel Terrain Tiles Specification. (FlyPie). Retrieved 2024-03-24, from https://github.com/FlySkyPie/voxtt-spec. ↩

2. Mike Gancarz: The UNIX Philosophy. (n.d.). Retrieved 2024-03-24, from https://en.wikipedia.org/wiki/Unix_philosophy#Mike_Gancarz:_The_UNIX_Philosophy ↩ ↩²

稍微把 Polis 挖坑至今 (2023-08-05) 累積的嘗試做個紀錄。

基本概念​

整個開放世界會被拆分成不同的區域，每個區域由獨立的節點 (Polis Node) 負責運算，節點跟節點之間會構成 P2P 網路，形成一個可以橫向擴展的架構，而 Client 端則會在由 Polis Node 構成的 P2P 網路所運算的開放世界中進行漫遊 (Roaming)。其實這種分散式的架構在 ITUGV 的時宜就令我十分著迷，不過那就是另外一段故事了，在這裡稍微提及只是為了讓讀者理解筆者對分散式架構抱有特別的偏好，並且這種構想早就存在於早期的其他專案之中。

POC (Proof Of Concept)​

雖然 Polis 作為 Hakoniwa 的子專案，目的一樣是為了建造一個程序化生成 Voxel 開放世界，但是 Polis 將會把重點放在兩個目標上：

• 建立 P2P 網路
• 能夠透過 Client 程式連線

因此在 Polis 的第一個原型中，達到這些條件就算成功完成了概念驗證：

2023-05-13 ~ 2023-05-26​

在這個階段我想用 Deno 作為實作 Polis Node 的手段，有幾個原因：

1. Typescript 目前是我最熟練的語言。
2. WebGPU 已經納入 Web API 中，而部份版本的 Deno 已經實作，因此我能使用 Typescript 解決 server side render 的需求，這麼部份是 Node.js 無法達成的。
3. Deno 內建跨平台編譯 (Cross Compiling)，因此寫一次程式我就能把節點佈署到除了 Linux 以外的 Windows 或是 macOS 上。

網路連接技術​

在挖了坑並且對技術棧 (Technology Stack) 有了粗略的方向之後，首先我想先處理 Polis 中最關鍵的問題：

如何建立 Polis 網路 （P2P 網路）？

在 2020-03-22 的時候我就有使用 ZeroMQ 進行過傳輸相關的實驗，也是我在 The Key of Huanche 中一直考慮投入使用的函式庫。直到我因為 Polis 的分散式架構回過頭去翻閱它的官方文件的時候，才發現了一件事：

And this is the world we’re targeting with ZeroMQ. When we talk of “scale”, we don’t mean hundreds of computers, or even thousands. Think of clouds of tiny smart and perhaps self-replicating machines surrounding every person, filling every space, covering every wall, filling the cracks and eventually, becoming so much a part of us that we get them before birth and they follow us to death. ¹

ZeroMQ 在官方文件 Chapter 8 - A Framework for Distributed Computing 中描述了他們那野心勃勃的願景，老實說這非常打動我。

然而調查下來，發現 Deno 在這方面並沒有多少函式庫可以使用、專案的活躍度也都很低：

• https://github.com/jjeffcaii/deno-zeromq
• https://github.com/rracariu/deno-jszmq
• 似乎只有實作 WekSocket
• https://github.com/trs/zmq
  • deno-jszmq 的 fork
• https://github.com/lenkan/deno-amqp
• 兼容 RabbitMQ
• 只支援 Server-Client 模式

資料傳輸載體​

Protobuf (Protocol Buffers) 是另外一個我有意投入 The Key of Huanche 使用的 Technology Stack，第一次知道它的存在是工作上使用 Mapbox 的並因此接觸 Mapbox Vector Tile 的時候發現它所使用的資料格式。簡言之就是一種預先定義資料結構後，把資料壓成密度比較高的格式進行傳輸，到達目的地之後再用預先定義的資料結構進行解碼，比起使用 JSON 傳輸可以省下很多頻寬。

然而在 Deno 的生態戲中依然有類似的問題，能選用的函式庫很少、而且專案活躍路很低：

• https://github.com/soootaleb/ddapps
  • Deno distributed applications framework
• https://deno.land/x/protobuf_ts@v1.2.2
  • https://github.com/dancrumb/protobuf.ts
• https://deno.land/x/deno_google_protobuf@4.0.0-rc.2
  • https://github.com/marcushultman/deno-google-protobuf
• https://pbkit.dev/
  • https://deno.land/x/pbkit@v0.0.61
  • https://github.com/pbkit/pbkit

如何分辨序列化資料 Protobuf 的型別？​

Polis Node 之間的通訊基本上是一個事件系統，而事件的種類千奇百怪，需要的資料結構當然也是五花八門，但是它們之間會使用同一個序列化的通道，接收端街收到一組序列化資料後要怎麼區分 Protobuf 的類型並使用不同的結構來解碼呢？

沒有辦法直接區分，但是可以透過幾個方法解決這個問題²：

• 定義一個 Protobuf 封裝來夾帶型別資訊
  • 用 oneof 封裝 (也被稱作 union)
    • https://stackoverflow.com/a/40040658
    • https://protobuf.dev/programming-guides/proto2/#oneof
    • https://protobuf.dev/programming-guides/proto3/#oneof
  • 將另外一組 proto 封裝成 any 屬性
    • https://protobuf.dev/programming-guides/techniques/#self-description
• 在 buffer 加入幾個 bytes 的前輟作為辨識符

壓垮 Deno （對我的專案而言）的最後一根稻草​

我其實很難找到支援 WebGPU 或是活躍的 WebGL 的 Javascript 函式庫進行 "denolize"。

WebGPU 在那個當下只有 0.04% 的覆蓋率，就算打開先行版 Chrome 的 WebGPU flag 也是充滿破圖，因此鮮少有函式庫有支援 WebGPU。

活躍的 Javascript 3D 繪圖函式庫，諸如：Three.js, Babylon.js，即便當下是基於 WebGL 實作，在 WebGPU 逐漸普及下應該也會逐步支援 WebGPU 才對，但是它們多是基於 Canvas 的繪圖方式，而 Deno 環境下的 WebGPU 實作並不包含 Canvas 相關方法。

加上 WebGPU 的 API 在 1.8 被加入 Deno 之後³，又在 1.32.0 中基於性能考量被移除了⁴。

也就是「在 Deno 中使用 WebGPU」這件是的前景並不樂觀，我可能必須要面對「使用舊版的 Deno 和相對底層的 WebGPU 手刻整個應用」的問題。

Deno 的 Cross Compiling 的能力是真的很吸引我，但是在繪圖跟網路連線兩面不討好的情況下，加上 IDE 在寫 Deno 程式的時候開發體驗並不好，我決定放棄這條路。

2023-05-27 ~ 2023-06-11​

在 2022-10-06 的時候我就已經嘗試過把網頁上渲染的 Canvas 畫面壓成 Webp 並透過 WebSocket 傳送給伺服器播放了⁵，但是當時只是寫了 POC 等級的程式，並不能很好的管理每次連線的 Session，因此良好的串流機制就成了我下一個研究目標。

串流方案​

花了一點時間 (2023-05-27~2023-05-28) 查資料了解有哪些可能的方案能夠實現我的需求：

• Websocket
  • ✅ Web API 十分普及
  • ❌ 需額外處理影像的解碼與渲染，消費更多的運算與延遲
• WebRTC
  • ✅ Web API 十分普及
  • ✅ 原生設計支援低延遲
  • ❌ 協定複雜
  • ❌ P2P 架構，雖然可能可以透過在伺服器實作底層來欺騙 client 端，但是需付出額外開發成本
• WebTransport/QUIC
  • ✅ 支援 UDP，可降低延遲
  • ✅ 次世代 API
  • ❌ Web API 尚未普及
    • 瀏覽器支援覆蓋率低
    • Nodejs 僅實驗性支援 QUIC
    • Deno 尚不支援
• HTML5 video tag
  • ✅ Web API 十分普及
  • ❌ 高延遲
• Video.js
• MPEG-DASH
  • ✅ 開放的標準
  • ❌ 有點複雜
• FLV
  • ✅ 歷史性因素，仍有許多資源
  • ❌ 過時

Node-Media-Server​

之後 (2023-06-04) 發現了 Node-Media-Server 這個專案，透過 RTMP (Real-Time Messaging Protocol) 向 Node-Media-Server 串流影像，接著能夠使用 Node-Media-Server-Admin 打開串流，而且能夠流暢的關閉與重新開啟串流，Session 的管理便是我在 POC 階段所缺失的，並且它能夠使用以 Javascript 撰寫的 code base 對外進行串流，那我只要有辦法用 Javascript 產生 RTMP 流，就能整合成符合我需求的程式。

於是我便試著透過用 Typescript 重構專案的方式理解它是如何實現串流推流的。

2023-06-11 ~ 2023-06-25​

RTMP​

接著我發現單靠程式碼無法理解它解析 RTMP 封包的邏輯，於是我便打開 RTMP 的規範文件並搭配一些教學文章試著理解它，不過大約只讀到 Header 的部份，我就意識到就算我能製造 RTMP 堆流，還是需要把影像做編碼，然而 Javascript 的生態系在做這件事情上有點貧弱，於是我把目光轉而投向 WebRTC。

至於 RTMP 的學習筆記我應該會發到另外一篇獨立的文章去，雖然因為我其實沒有把 Spec 完整看完，發個不完整的筆記感覺怪彆扭的。=w="

2023-06-25 ~ 2023-08-05​

WebRTC​

7 月份因為工作上的壓力比較大，加上充滿了親戚過世、Steam 夏季特賣、COSUP...等等事件，所以學習 WebRTC 的進度可以說是其極緩慢，不過終於在昨天 (2023-08-05) 理解如何使用這個 Web API 並把範例做出來了。

同樣的，關於 WebRTC 的學習筆記我會放在另外一篇獨立的文章。

---

Wei Ji 以創用CC 姓名標示-相同方式分享 4.0 國際 授權條款釋出。

Footnotes​

1. Chapter 8 - A Framework for Distributed Computing. Retrieved 2023-08-05, from https://zguide.zeromq.org/docs/chapter8 ↩

2. c# - Protocol buffers detect type from raw message - Stack Overflow. Retrieved 2023-08-06, from https://stackoverflow.com/a/9125119 ↩

3. Deno 1.8 Release Notes. Retrieved 2023-08-05, from https://deno.com/blog/v1.8 ↩

4. Release v1.32.0 · denoland/deno. Retrieved 2023-08-05, from https://github.com/denoland/deno/releases/tag/v1.32.0 ↩

5. Day 22 Streaming POC - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天. Retrieved 2023-08-05, from https://ithelp.ithome.com.tw/articles/10305097 ↩

• 一種去中心化叢集運算架構，用以建構運算 Hakoniwa 的網路。
• Polis 是「古希臘城邦」的意思。

基本概念 Concept​

技術痛點​

具我所知 Minecraft 在軟體層面有兩個瓶頸：

• 複雜的 OOP 結構
• 伺服器端使用單執行緒

以前我試著寫 Minecraft 插件的時候，因為有使用到 NMS (net.minecraft.server) 的 API，因此大概知道 Minecraft 的程式碼大量使用了多層繼承 (Multilevel Inheritance)，然而這種 OOP 模式不只增加了開發者的負擔（本人認為多層繼承是一種反模式），更會造成在處理 Minecraft 這樣複雜的遊戲內容時，狀態的管理不容易控制而造成 bug 並且難以排除。

於是我打算使用 ECS (Entity Component System) 架構來解決，其概念就是單純化資料容器 (Entity 與 Component)，由 System 執行邏輯運算，透過分離資料和邏輯達到更清晰的程式碼，並且複數 System 有序執行的方式讓狀態管理單純化。然而這個架構有個問題，就是 System 有序執行的特性讓我不知道如何搭配多執行緒來提高軟體對硬體資源的利用率。

遊戲運算平行化​

其中一個合理的解方是以地圖的 Chunk 為單位切割最小的運算區塊 (Game Block)，一個 Game Block 由一個執行緒處理運算，Game Block 之間（也就是執行緒之間）的通訊則由事件驅動。

舉例來說，有一支箭矢飛越運算區塊的邊界：

來源 Game Block 會把箭矢的資訊包裝成一個事件，發送給目標 Game Block，並且從資料集中移除。目標 Game Block 則是根據事件創建一個箭矢實體並繼續運算。兩個 Game Block 使用獨立的執行緒，並且運算週期並不同步，因此不會凍結彼此。

何不乾脆 P2P?​

不知道為什麼，我直覺覺得比起寫成一個 APP 管理一堆 Game Block，不如乾脆全部做成微服務，讓它們自己構成一個叢集比較好。於是一個新的坑 (Polis) 就產生了。

---

Wei Ji 以創用CC 姓名標示-相同方式分享 4.0 國際 授權條款釋出。

未採用的幾何方案​

原本我打算從波函數中尋找用來描述仿星環的函數，比如電子軌域或是電磁波：

但是這些模型的產物都是張量，要另外設定條件把線（面）畫出來是很困難的。

摸索的過程中也有朋友建議一個接近的函數：腎形線，可惜它中間不是貫穿的。

幾何參數​

最後採用尺規作圖直接刻的方式，簡單暴力。

接著計算 Voxel 平面的長度，也就是經度線H(紅)

$$\begin{align} H &= 0.5(2\pi \cdot 0.5R) + 2\pi R\cdot 0.25 + 2 \pi (2R) \cdot 0.25 + 0.5(2\pi \cdot 0.5R) \\ &= 2.5 \pi R \end{align}$$

與 Voxel 平面的寬度；緯度線W（藍），取小圓周與大園周的平均值：

$$\begin{align} W &= \frac{2 \pi (R) + 2 \pi (2R)}{2} \\ &=3 \pi R \end{align}$$

因此平面面積為

$$A = H \cdot W = 7.5 \pi^2 R^2$$

等效仿星環​

一個球體行星的表面積為：

$$S = 4\pi {R_s}^{2}$$

若要將仿星環近似已知行星的表面積；如地球，則可透過下述關係達成：

$$\begin{align} S &= A \\ 4\pi {R_s}^{2} &= 7.5 \pi^2 R^2 \\ \sqrt{\frac{1}{1.875 \pi}} R_s &= R \end{align}$$

地球的半徑為 6,371 km，因此等效仿星環的 R 為 2,625 km

A Technique to Quilting Gradient Noise

目的​

我想在一個 torus 的空間中使用演算法生成地形 (Procedural generation)，因此演算法必須使地圖邊界無接縫 (Seamless)。

被排除的方案​

The image quilting​

該算法的原理是在兩張貼圖的交界處做重疊 (overlay)，並使用 error 值尋找最短路徑而達到縫合的目的。^{1 2}

但是該算法的目的是從原始貼圖中抽出拼貼塊 (patches)，並用拼貼塊重新製作圖片，並不適合用於兩個固定邊界的縫合。

當我試著用這個算法處理 noise map 的交界會變成這樣：

Periodic Perlin Noise​

Perlin Noise 的產生是透過在網格中指定隨機的向量來創造梯度，再透過內插來生成最終的 noise map。

因此只要兩個邊界使用同一組向量，就能生成無接縫的 noise map。³

不過我個人不太想重新實做 noise 生成層級的演算法；加上雖然我的目標是生成無接縫的 noise map，但是很有可能實際上會需要縫合兩張算法完全不同的 noise map，再加上交界處很有可能不具有完整的網格（貼圖的大小不是 lattice 的整數倍），所以最終不考慮這個方案。

演算法​

其實就是做線性內插：

$$f(x) = \begin{cases} g(x), & x < x_a \\ v(x), & x_a \leq x \leq x_b \\ h(x), & x_b < x \end{cases} \\ v(x)=g(x) \cdot (1-r) + h(x) \cdot r \\ r(x)=\frac{x-x_a}{x_b-x_a}$$

只是線性內插本質上就是加權平均數，這會使 noise map 變得模糊，因此加上一個修飾：

$$v_s(x) = \text{smoothstep}(v) \cdot r_s + v(x) \cdot (1-r_s ) \\ r_s(x) = \begin{cases} r, & r \leq 0.5 \\ (1-r), & r > 0.5 \end{cases}$$

smoothstep 函數能夠增加 noise 的對比來修復部份因為線性插值造成銳利度降低（模糊）的區域。

沒有 smoothstep：

加上 smoothstep：

Footnotes​

1. Image Quilting for Texture Synthesis and Transfer. (Alexei A. Efros). Retrieved 2022-06-04, from https://people.eecs.berkeley.edu/~efros/research/quilting/quilting.pdf ↩

2. Image Quilting for Texture Synthesis & Transfer. (Alexei Efros). Retrieved 2022-06-04, from https://people.eecs.berkeley.edu/~efros/research/quilting/efros-siggraph01.ppt ↩

3. tiles - How do you generate tileable Perlin noise? (Boojum). Retrieved 2022-06-04, from https://gamedev.stackexchange.com/questions/23625 ↩

Evaluate resources​

We can evaluate scarcity of resources intuitively; the more rare it is, the more value it is. But scarcity of economics are measured by supply and demand, it can't be a unit which had clearly definition. We can get probability of resources generated on map, but the probability wasn't enough to measured agent, it needed been processed additionally.

Shannon Entropy and Shannon Information​

The nature of Shannon entropy is mathematics quantity which well known "uncertainty of phenomenon".¹

$$\mathrm H (X) = \mathrm{E}[\mathrm{I}(X)] = \mathrm{E}[-\ln(\mathrm{P}(X))]$$

and $I$ is Shannon Information, it be defined as:

$$I(X) = - \log_2 \mathrm{P}(X)$$

We can noted the meaning of $-\log_2 p_i$ is "the lower the probability of an event, the greater the information carried when the event occurs", so Shannon entropy is expected value of Shannon information, can be express by:

$$\mathrm H (X) = - \sum_i p_i \log_2 p_i$$

Formula of Crafting​

To describe pattern of items changes easily, which caused by crafting or another mechanism in the game, I borrow the form of chemical equation:

$$aX + bY \xrightarrow[P]{} cZ$$

$a,b,c$：amount of materials or products $X,Y$：materials, items would vanished after crafting process $Z$：products $P$：the path of crafting, item(s) won't vanished after crafting process

Information of Items​

The nature of Minecraft World are a bunch of digital data, so were reasonably considered it as a string of information, and quantify it as Shannon Entropy or Information. For a block which status was uncertain, the value is:

$$\mathrm H (X) = \mathrm{E} ( \mathrm{I}) = - \sum_i p_i \log_2 p_i$$

and $p_i$ is probability of (some type of) block generated in map, therefore we can get information of block of certain type by:

$$I_x = -\log_2 p_x$$

Information of Crafting​

It could calculation entropy of nature resources by probability of generated in the map, but most of items are obtained by crafting in Minecraft, when I mention "crafting" are meaning "the mechanism can be expressed by formula of crafting in the game". Need to gain entropy of non-nature items through calculation.

Let do a crafting example:

$$X + Y \xrightarrow[W]{} Z$$

$X,Y,W$ represents three different types of blocks, can be treated as three randomly independently event, and their probability of exists in map are $p_X, p_Y, p_W$, so we can get probability of event $Z$ happened was multiplied by probabilities, also was summing by information of probabilities:

$$\begin{align} I_Z &= -\log_2(p_X p_Y p_W) \\ &= -\log_2 p_X -\log_2 p_Y -\log_2 p_W \\ &= I_X + I_Y + I_W \end{align}$$

The Ratio Between Material(s) and Product(s)​

When the ratio isn't 1, total number of items would changed.

$$mX \xrightarrow[P]{} nY$$

and:

$$H_Y = \frac{m}{n}H_X$$

Crafting Path​

The item(s) won't vanished as crafting path in the process, so:

$$\begin{array}{l} X \xrightarrow[W]{} Y & \Delta I = I_W \end{array}$$

Multiple Crafting Path​

When there are multiple path to gain item(s), it can been treats as a parallel system, therefore, the information of products can be expressed by:

$$I = -\log_2 [1 - \prod_i(1-p_i)]$$

The Items with Zero Entropy​

The probability of items dropped by monster, are affected by probability of monster generation, and its not related space, but time, so:

$$H |_{\Delta t = 0}= -\lim_{p \rightarrow0^+} p\log p = 0$$

or consider it could been generated in infinity time, the probability of generation is 1, therefor:

$$H |_{t \rightarrow \infty} = -\log(1) = 0$$

Information of Environment​

We must define "system", when quantified information of system, so need to defined a range of space and how many blocks or items contained in the space.There are 3 kind of definition of system which common been used under below:

1. Complete System
   • Blocks, items in inventory block, item entity dropped and items in player inventory, which contained in a limited space.
2. Block System
   • Blocks and items in inventory block, which contained in a limited space.
3. Player System
   • Items in the player inventory.

We can quantify entropy of system through rules has been created, and intervening variables can been gain by making statistics on map. We can expect the entropy of environment would changed through behavior of agent, therefore those changes could be one of index of evaluated the agent.

Table of Items Information​

The following information evaluation value is for reference only, there are not included every items in the game, and process are not very rigorous. The goal is demonstrated the theory of this article, anyone are interested can finished the table by self.

Natual Resource​

Using Cuberite 1.7.X-linux64² to generate map and making statistics by plugin³. There were sampling 10 times, and remove map file to generate new seed every time. To simplify data, I merged yellow flower and red flower, removed flowing water, flowing lava, cobblestone, torch, flame, monster spawner, chest and dead bush, replace them by air.

Block	Count	Probability	Information	Entropy
Air	151464079	0.7506049	0.4138744	0.3106562
Bedrock	788224	0.0039062	8.0000287	0.0312495
Brown Mushroom	648	0.0000032	18.2484248	0.0000586
Cactus	11	0.0000001	24.1288432	0.0000013
Clay	8790	0.0000436	14.4866274	0.0006310
Coal Ore	345962	0.0017145	9.1880208	0.0157526
Cobweb	1998	0.0000099	16.6239340	0.0001646
Diamond Ore	19629	0.0000973	13.3275758	0.0012964
Dirt	2347857	0.0116352	6.4253617	0.0747603
Double Plant	14242	0.0000706	13.7904107	0.0009733
Fence	8543	0.0000423	14.5277478	0.0006151
Flower	4014	0.0000199	15.6174499	0.0003107
Gold Ore	43697	0.0002165	12.1730282	0.0026360
Grass	471646	0.0023373	8.7409299	0.0204303
Gravel	534501	0.0026488	8.5604417	0.0226750
Iron Ore	395336	0.0019592	8.9955550	0.0176237
Lapis Lazuli Ore	17690	0.0000877	13.4776284	0.0011815
Leaves	382779	0.0018969	9.0421227	0.0171522
Lily Pad	122	0.0000006	20.6575375	0.0000125
Obsidian	2390	0.0000118	16.3654799	0.0001938
Rail	2528	0.0000125	16.2844941	0.0002040
Red Mushroom	974	0.0000048	17.6604969	0.0000852
Redstone Ore	160117	0.0007935	10.2995079	0.0081725
Sand	272220	0.0013490	9.5338613	0.0128615
Sandstone	109888	0.0005446	10.8426005	0.0059045
Snow	3033	0.0000150	16.0217451	0.0002408
Still Lava	158088	0.0007834	10.3179065	0.0080834
Still Water	3281908	0.0162640	5.9421715	0.0966437
Stone	40812030	0.2022507	2.3057837	0.4663463
Sugar Canes	41	0.0000002	22.2307228	0.0000045
Tallgrass	66818	0.0003311	11.5603257	0.0038279
Vines	1179	0.0000058	17.3849268	0.0001016
Wood Plank	12762	0.0000632	13.9487080	0.0008822
Wood	55614	0.0002756	11.8251144	0.0032591

Products​

Wood Plank​

$$\text{Wood} \xrightarrow[]{} 4 \text{ Wood Plank}$$ $$\begin{align} I_{WP} &= \frac1{4} I_{W} = 0.25 \cdot 11.8\\ &= 2.95 \end{align}$$

Crafting Table​

$$4 \text{ Wood Plank} \xrightarrow[]{} \text{Crafting Table}$$ $$\begin{align} I_{CT} &= 4 I_{WP} = 4 \cdot 2.95 \\ &= 11.8 \end{align}$$

Stick​

$$2 \text{ Wood Plank} \xrightarrow[]{} 4 \text{ Stick}$$ $$\begin{align} I_{S} &= \frac{2}{4} I_{WP} = 0.5 \cdot 2.95 \\ &= 1.475 \end{align}$$

Wooden Pickaxe​

$$3 \text{ Wood Plank} + 2 \text{ Stick} \xrightarrow[\text{Crafting Table}]{} \text{ Wooden Pickaxe}$$ $$\begin{align} I_{\text{WPickaxe}} &= 3 I_{\text{WPlank}} + 2 I_{S} + I_{CT}\\ &= 3 \cdot 2.95 + 2 \cdot 1.475 + 11.8\\ &= 23.6 \end{align}$$

Cobblestone​

To simplify calculation, there's not consider crafting path with another type of pickaxe except wooden one.

$$\text{ Stone } \xrightarrow[\text{Wooden Pickaxe}]{} \text{ Cobblestone}$$ $$\begin{align} I_{C} &= I_{S} + I_{WP} \\ &= 2.31 + 23.6 \\ &= 25.91 \end{align}$$

Furnace​

$$8\text{ Cobblestone } \xrightarrow[\text{Crafting Table}]{} \text{ Furnace}$$ $$\begin{align} I_{F} &= 8I_{C} + I_{CT} \\ &= 8 \cdot 25.91 + 11.8 \\ &= 219.08 \end{align}$$

Stone Pickaxe​

$$3 \text{ Cobblestone} + 2 \text{ Stick} \xrightarrow[\text{Crafting Table}]{} \text{ Stone Pickaxe}$$ $$\begin{align} I_{\text{SP}} &= 3 I_{\text{C}} + 2 I_{S} + I_{CT}\\ &= 3 \cdot 25.91 + 2 \cdot 1.475 + 11.8\\ &= 92.48 \end{align}$$

Iron Ore Item​

To simplify calculation, there's not consider crafting path with another type of pickaxe except stone one.

$$\text{ Iron Ore } \xrightarrow[\text{Stone Pickaxe}]{} \text{ Iron Ore Item}$$ $$\begin{align} I_{IOI} &= I_{IO} + I_{SP} \\ &= 9.00 + 92.48 \\ &= 101.48 \end{align}$$

Coal​

To demonstrate calculation of parallel system, there's consider crafting path with wooden and stone pickaxe.

$$\text{ Coal Ore } \xrightarrow[\text{Wooden(Stone) Pickaxe}]{} \text{ Coal}$$ $$\begin{align} I_{C1} &= I_{CO} + I_{WP} \\ &= 9.18 + 23.6 \\ &= 32.78 \end{align}$$ $$\begin{align} I_{C2} &= I_{CO} + I_{SP} \\ &= 9.18 + 92.48 \\ &= 101.66 \end{align}$$ $$p_1 = 2^{-I_1} = 2^{-32.78} = 1.35592835311 \cdot 10^{-10} \\ p_2 = 2^{-I_2} = 2^{-101.66} = 2.49626473127 \cdot 10^{-31} \\ p = 1 - (1-p_1)(1-p_2) = 1.355928702651 \cdot 10^{-10}$$ $$I_C = -\log_2 p = 32.78$$

Iron Ingot​

$$\text{ Iron Ore Item} + \frac1{8} \text{ Coal} \xrightarrow[\text{Furnace}]{} \text{ Iron Ingot}$$ $$\begin{align} I_{II} &= I_{IOI} + \frac1{8} I_{C} + I_{F} \\ &= 101.48 + 0.125 \cdot 32.78 + 219.08\\ &= 324.6575 \end{align}$$

The Table​

It is summary those value are calculated or mention in this article, and just as I said, this article didn't calculated all information of items in the game, therefore the table are unfinished:

Block/Item	Information (bit)	Block/Item	Information (bit)
Iron Ingot	324.66	Lapis Lazuli Ore	13.48
Furnace	219.08	Diamond Ore	13.33
Iron Ore Item	101.48	Gold Ore	12.17
Stone Pickaxe	92.48	Wood	11.83
Coal	32.78	Crafting Table	11.80
Cobblestone	25.91	Tallgrass	11.56
Cactus	24.13	Sandstone	10.84
Wooden Pickaxe	23.60	Still Lava	10.32
Sugar Canes	22.23	Redstone Ore	10.30
Lily Pad	20.66	Sand	9.53
Brown Mushroom	18.25	Coal Ore	9.19
Red Mushroom	17.66	Leaves	9.04
Vines	17.38	Iron Ore	9.00
Cobweb	16.62	Grass	8.74
Obsidian	16.37	Gravel	8.56
Rail	16.28	Bedrock	8.00
Snow	16.02	Dirt	6.43
Flower	15.62	Still Water	5.94
Fence	14.53	Wood Plank	2.95
Clay	14.49	Stone	2.31
Wood Plank	13.95	Stick	1.48
Double Plant	13.79	Air	0.41

Conclusion​

Just like James Lovelock said⁴:

I’d look for an entropy reduction, since this must be a general characteristic of life.

We can quantify extropy which agent created by reform the environment, to measue the policy:

$$\Delta H_{\pi,t} = H_o - H_{\pi,t} \\ \pi^* = \arg \min_{\pi} \Delta H_{\pi,t}$$

tags: The Key Of Huanche​

Footnotes​

1. 信息熵是什么？ - 知乎. (返朴). Retrieved 2020-05-31, from https://www.zhihu.com/question/22178202/answer/667876061 ↩

2. Releases · cuberite/cuberite. (cuberite). Retrieved 2020-05-31, from https://github.com/cuberite/cuberite/releases/download/1.7EOL/Cuberite-linux64.tar.gz ↩

3. FlySkyPie/cuberite-block-counter: To make statistics of blocks. Retrieved 2020-05-31, from https://github.com/FlySkyPie/cuberite-block-counter ↩

4. Lovelock, James (1979). GAIA – A New Look at Life on Earth. Oxford University Press. ISBN 978-0-19-286218-1. ↩

評價資源​

我們能夠直觀的以資源的稀有程度去抽象的衡量資源的價值；越稀有的資源越有價值，反之亦然。但是經濟學上的價值是透過供需市場產生的，並不能作為有明確定義的綱量。我們能獲得的是資源生成在地圖上的機率，但是僅有資源機率並不能夠適當直接作為 agent 的評價手段，需要一些額外的處理。

夏農熵與夏農資訊 (Shannon Entropy and Information)​

夏農熵本質上是對我們司空見慣的「不確定現象」的數學化度量。¹

$$\mathrm H (X) = \mathrm{E}[\mathrm{I}(X)] = \mathrm{E}[-\ln(\mathrm{P}(X))]$$

其中 $I$ 為夏農資訊，被定義為：

$$I(X) = - \log_2 \mathrm{P}(X)$$

我們可以注意到當中的 $-\log_2 p_i$ 所描述的意義為：「事件發生的機率越低，則當該事件發生時所夾帶的資訊越大」，因此夏農熵也是對不確定的夏農資訊的期望值，亦可寫作：

$$\mathrm H (X) = - \sum_i p_i \log_2 p_i$$

合成式 (Formular of Crafting)​

為了方便描述合成或其他遊戲機制使資源 (items) 發生變化的過程，我借用了化學反應式的形式來表達：

$$aX + bY \xrightarrow[P]{} cZ$$

$a,b,c$：原料或產物的數量 $X,Y$：原料，合成過程會被消耗的物品 $Z$：產物 $P$：合成途徑，參與合成但是不會被消耗的物品。

資源的資訊量 (Information of Items)​

Minecraft 世界在本質上就是一團數位資料，因此將其視作一串由方塊構成的資訊，並用夏農熵或夏農資訊去衡量其資訊量是十分合理的作法。對於一個不確定狀態的方塊來說，其值為：

$$\mathrm H (X) = \mathrm{E} ( \mathrm{I}) = - \sum_i p_i \log_2 p_i$$

其 中$p_i$ 為某種類型的方塊出現在地圖中的機率，換句話說我們可以得知特定種類方塊其資訊量為：

$$I_x = -\log_2 p_x$$

合成的資訊量 (Information of Crafting)​

天然資源能夠以其在地圖生成的機率來計算熵，但是 Minecraft 中的大部分物品需透過合成途徑獲得，當我提到合成是指：「能夠被合成式所表示的所有遊戲機制」，這些非天然物品的熵需透過計算取得。

以一個合成為例：

$$X + Y \xrightarrow[W]{} Z$$

$X,Y,W$ 分別代表三種不同類型的方塊，我們可以視作三個隨機事件，而這三者出現在地圖的機率分別為 $p_X, p_Y, p_W$ 並且互為獨立事件，因此我們可以得知事件 $Z$ 發生的機率為三者的機率相乘，也就是三者資訊量的加總：

$$\begin{align} I_Z &= -\log_2(p_X p_Y p_W) \\ &= -\log_2 p_X -\log_2 p_Y -\log_2 p_W \\ &= I_X + I_Y + I_W \end{align}$$

數量的變化 (The ratio between resource and product)​

當原料與產物的比值不為 1 時，物品的總數量發生了變化。

$$mX \xrightarrow[P]{} nY$$

則：

$$H_Y = \frac{m}{n}H_X$$

合成途徑 (Crafting Path)​

作為合成途徑的物品不會被消耗，因此：

$$\begin{array}{l} X \xrightarrow[W]{} Y & \Delta I = I_W \end{array}$$

多重途徑 (Multiple Crafting Path)​

當一個物品有多種取得途徑時可以視作一個並聯系統 (parallel systems)，因此該物品的資訊量可以寫作：

$$I = -\log_2 [1 - \prod_i(1-p_i)]$$

零資訊的資源 (The Items with Zero Entropy)​

怪物掉落物仰賴怪物的生成，但是怪物生成的機率並不是與空間關聯，而是與時間關聯的，以空間機率考慮：

$$H |_{\Delta t = 0}= -\lim_{p \rightarrow0^+} p\log p = 0$$

若或是考慮其在無窮的時間中能夠被無限生成，事件發生的機率為 1，因此：

$$H |_{t \rightarrow \infty} = -\log(1) = 0$$

環境的資訊量 (Information of Environment)​

當我們要量化系統的資訊量時，必須先界定所謂的「系統」。要定義一個系統，我們要給定一個範圍（空間大小）以及具體包含了多少方塊或物品。以下有三種定義應該是我們比較常用的系統類型：

1. 完整系統
   • 在一劃定的範圍內，所包含的方塊、收納方塊內容物、掉落物與玩家物品欄（裝備欄）內容物。
2. 方塊系統
   • 在一劃定的範圍內，所包含的方塊與收納方塊內容物。
3. 玩家系統
   • 玩家物品欄（裝備欄）內容物。

透過到目前為止建立的規則，我們可以量化一個系統的熵，而該值能透過統計地圖中的方塊與實體取得。隨著 agent 在環境中活動，我們可以預期環境的熵會因此發生改變，這個變化量便可做為評量 agent 的指標之一。

資訊量表 (Table of Items Information)​

以下的資訊量評估值僅供參考，過程並不嚴謹並且沒有對所有的物品進行計算。目的只是透過實做示範如何實踐本文建構的理論，有興趣的人可以自行用更嚴謹的方式建構完整的遊戲物件資訊量表。

天然資源 (Natual Resource)​

使用 Cuberite 1.7.X-linux64² 生成地圖並搭配插件³統計方塊數量。總共抽樣 10 次，每次都會將地圖檔案刪除以生成新的種子。為了簡化數據，將紅花與黃花視為同樣的東西，並將流動水、流動岩漿、鵝卵石、火把、火焰、生怪磚、箱子與枯萎灌木移除並用空氣取代。統計資料如下表：

方塊	數量	生成機率	資訊量	熵
Air	151464079	0.7506049	0.4138744	0.3106562
Bedrock	788224	0.0039062	8.0000287	0.0312495
Brown Mushroom	648	0.0000032	18.2484248	0.0000586
Cactus	11	0.0000001	24.1288432	0.0000013
Clay	8790	0.0000436	14.4866274	0.0006310
Coal Ore	345962	0.0017145	9.1880208	0.0157526
Cobweb	1998	0.0000099	16.6239340	0.0001646
Diamond Ore	19629	0.0000973	13.3275758	0.0012964
Dirt	2347857	0.0116352	6.4253617	0.0747603
Double Plant	14242	0.0000706	13.7904107	0.0009733
Fence	8543	0.0000423	14.5277478	0.0006151
Flower	4014	0.0000199	15.6174499	0.0003107
Gold Ore	43697	0.0002165	12.1730282	0.0026360
Grass	471646	0.0023373	8.7409299	0.0204303
Gravel	534501	0.0026488	8.5604417	0.0226750
Iron Ore	395336	0.0019592	8.9955550	0.0176237
Lapis Lazuli Ore	17690	0.0000877	13.4776284	0.0011815
Leaves	382779	0.0018969	9.0421227	0.0171522
Lily Pad	122	0.0000006	20.6575375	0.0000125
Obsidian	2390	0.0000118	16.3654799	0.0001938
Rail	2528	0.0000125	16.2844941	0.0002040
Red Mushroom	974	0.0000048	17.6604969	0.0000852
Redstone Ore	160117	0.0007935	10.2995079	0.0081725
Sand	272220	0.0013490	9.5338613	0.0128615
Sandstone	109888	0.0005446	10.8426005	0.0059045
Snow	3033	0.0000150	16.0217451	0.0002408
Still Lava	158088	0.0007834	10.3179065	0.0080834
Still Water	3281908	0.0162640	5.9421715	0.0966437
Stone	40812030	0.2022507	2.3057837	0.4663463
Sugar Canes	41	0.0000002	22.2307228	0.0000045
Tallgrass	66818	0.0003311	11.5603257	0.0038279
Vines	1179	0.0000058	17.3849268	0.0001016
Wood Plank	12762	0.0000632	13.9487080	0.0008822
Wood	55614	0.0002756	11.8251144	0.0032591

加工品 (Products)​

木板​

$$\text{Wood} \xrightarrow[]{} 4 \text{ Wood Plank}$$ $$\begin{align} I_{WP} &= \frac1{4} I_{W} = 0.25 \cdot 11.8\\ &= 2.95 \end{align}$$

工作台​

$$4 \text{ Wood Plank} \xrightarrow[]{} \text{Crafting Table}$$ $$\begin{align} I_{CT} &= 4 I_{WP} = 4 \cdot 2.95 \\ &= 11.8 \end{align}$$

木棒​

$$2 \text{ Wood Plank} \xrightarrow[]{} 4 \text{ Stick}$$ $$\begin{align} I_{S} &= \frac{2}{4} I_{WP} = 0.5 \cdot 2.95 \\ &= 1.475 \end{align}$$

木鎬​

$$3 \text{ Wood Plank} + 2 \text{ Stick} \xrightarrow[\text{Crafting Table}]{} \text{ Wooden Pickaxe}$$ $$\begin{align} I_{\text{WPickaxe}} &= 3 I_{\text{WPlank}} + 2 I_{S} + I_{CT}\\ &= 3 \cdot 2.95 + 2 \cdot 1.475 + 11.8\\ &= 23.6 \end{align}$$

鵝卵石​

為了簡化計算，下列過程不考慮其他材質的鎬挖掘的情況。

$$\text{ Stone } \xrightarrow[\text{Wooden Pickaxe}]{} \text{ Cobblestone}$$ $$\begin{align} I_{C} &= I_{S} + I_{WP} \\ &= 2.31 + 23.6 \\ &= 25.91 \end{align}$$

熔爐​

$$8\text{ Cobblestone } \xrightarrow[\text{Crafting Table}]{} \text{ Furnace}$$ $$\begin{align} I_{F} &= 8I_{C} + I_{CT} \\ &= 8 \cdot 25.91 + 11.8 \\ &= 219.08 \end{align}$$

石鎬​

$$3 \text{ Cobblestone} + 2 \text{ Stick} \xrightarrow[\text{Crafting Table}]{} \text{ Stone Pickaxe}$$ $$\begin{align} I_{\text{SP}} &= 3 I_{\text{C}} + 2 I_{S} + I_{CT}\\ &= 3 \cdot 25.91 + 2 \cdot 1.475 + 11.8\\ &= 92.48 \end{align}$$

鐵礦​

為了簡化計算，下列過程不考慮其他材質的鎬挖掘的情況。

$$\text{ Iron Ore } \xrightarrow[\text{Stone Pickaxe}]{} \text{ Iron Ore Item}$$ $$\begin{align} I_{IOI} &= I_{IO} + I_{SP} \\ &= 9.00 + 92.48 \\ &= 101.48 \end{align}$$

煤​

為了示範並聯系統的計算，以下僅考慮木鎬與石鎬的挖掘途徑。

$$\text{ Coal Ore } \xrightarrow[\text{Wooden(Stone) Pickaxe}]{} \text{ Coal}$$ $$\begin{align} I_{C1} &= I_{CO} + I_{WP} \\ &= 9.18 + 23.6 \\ &= 32.78 \end{align}$$ $$\begin{align} I_{C2} &= I_{CO} + I_{SP} \\ &= 9.18 + 92.48 \\ &= 101.66 \end{align}$$ $$\begin{align} p_1 = 2^{-I_1} = 2^{-32.78} = 1.35592835311 \cdot 10^{-10} \\ p_2 = 2^{-I_2} = 2^{-101.66} = 2.49626473127 \cdot 10^{-31} \\ p = 1 - (1-p_1)(1-p_2) = 1.355928702651 \cdot 10^{-10} \end{align}$$ $$I_C = -\log_2 p = 32.78$$

鐵錠​

$$\text{ Iron Ore Item} + \frac1{8} \text{ Coal} \xrightarrow[\text{Furnace}]{} \text{ Iron Ingot}$$ $$\begin{align} I_{II} &= I_{IOI} + \frac1{8} I_{C} + I_{F} \\ &= 101.48 + 0.125 \cdot 32.78 + 219.08\\ &= 324.6575 \end{align}$$

資訊量總表 (The Table)​

正如我提過得，本文並沒有計算所有物品的資訊量，僅是將先前統計或計算得到的數值做個整理，因此這個表並不完整。

方塊/物品	資訊量	方塊/物品	資訊量
Iron Ingot	324.66	Lapis Lazuli Ore	13.48
Furnace	219.08	Diamond Ore	13.33
Iron Ore Item	101.48	Gold Ore	12.17
Stone Pickaxe	92.48	Wood	11.83
Coal	32.78	Crafting Table	11.80
Cobblestone	25.91	Tallgrass	11.56
Cactus	24.13	Sandstone	10.84
Wooden Pickaxe	23.60	Still Lava	10.32
Sugar Canes	22.23	Redstone Ore	10.30
Lily Pad	20.66	Sand	9.53
Brown Mushroom	18.25	Coal Ore	9.19
Red Mushroom	17.66	Leaves	9.04
Vines	17.38	Iron Ore	9.00
Cobweb	16.62	Grass	8.74
Obsidian	16.37	Gravel	8.56
Rail	16.28	Bedrock	8.00
Snow	16.02	Dirt	6.43
Flower	15.62	Still Water	5.94
Fence	14.53	Wood Plank	2.95
Clay	14.49	Stone	2.31
Wood Plank	13.95	Stick	1.48
Double Plant	13.79	Air	0.41

結語​

就如像詹姆斯·拉夫洛克(James Lovelock)所說的⁴：

I’d look for an entropy reduction, since this must be a general characteristic of life.

我們可以透過 agent 對環境進行改造從而造成的熵減量，作為衡量策略的方法：

$$\Delta S_{\pi,t} = S_o - S_{\pi,t} \\ \pi^* = \arg \min_{\pi} \Delta S_{\pi,t}$$

Footnotes​

1. 信息熵是什么？ - 知乎. (返朴). Retrieved 2020-05-31, from https://www.zhihu.com/question/22178202/answer/667876061 ↩

2. Releases · cuberite/cuberite. (cuberite). Retrieved 2020-05-31, from https://github.com/cuberite/cuberite/releases/download/1.7EOL/Cuberite-linux64.tar.gz ↩

3. FlySkyPie/cuberite-block-counter: To make statistics of blocks. Retrieved 2020-05-31, from https://github.com/FlySkyPie/cuberite-block-counter ↩

4. Lovelock, James (1979). GAIA – A New Look at Life on Earth. Oxford University Press. ISBN 978-0-19-286218-1. ↩