4 posts tagged with "Polis"

前情提要​

• 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。

稍微把 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 國際 授權條款釋出。