DOOM engine blockmap解析筆記
blockmap是附屬在map data裡面的一個資料結構，blockmap存放的位置和長度都是紀錄在WAD最前面的lump目錄裡。他和碰撞檢測相關，概念是用grid(網格)把地圖切割成小block，只有在同一個block的物體和牆壁會進行檢測。根據1994釋出的一份unofficial doom spec文件block上限是113*113個，在遊戲的automap模式開啟grid，可以看到實際被分割的樣子。
blockmap結構分三塊：header、offset、blocklist，數值格式都是 I16 (int short)，可以在doom wiki找到的表格就不放，僅紀錄我的筆記。
header是第0～7byte， 0～3紀錄的是grid起點座標，通常是負值，如果使用的系統只能繪製在第一象限就要作平移，這在所有automap繪製相關的座標都要注意。4~7是blockmap的水平和垂直格數，相乘即總block (N)，所以doom1的E1M1有36*23＝824個block。
Offset是第8～8+2*(N-1) byte，紀錄每個block在blockmap資料結構裡的位置(byte offset)。每兩個byte是一個block的起始位置，例如E1M1的第一個block位置(也就是blocklist的起點)在第832byte。
blocklist存放N個block的資訊，block的資料結構有兩種，Tool格式開頭是兩個0x00 (int short 0)結尾是兩個0xFF (int short -1)，executable格式少了開頭兩個0x00，直接從wad解出來的是前者。所以直接搜尋blocklist資料裡-1的數量會等於block數量。0和-1之間會存放block內包含的line，並不是直接紀錄相關資訊，而是每2byte對應linedef裡的一筆資料，像E1M1最後一個linedef編號474，blocklist能找到的最大編號也是474。
#Blockmap structure####header###x coordinate of grid originy coordinate of grid originNumber of columnsNumber of rows###offsets###Offset to block 0...Offset to block N - 1###blocklist####block 00, line_a0, ..., line_an, -1#block 1
0, line_b0, ..., line_bn, -1... ... ...#block n-1
0, line_x0, ..., line_xn, -1#########
Block裡面有可能不含任何linedef，E1M1一開始的十幾個block都在地圖外，資料解出來是一串連續的0,-1，以為是blocklist資料格式弄錯，多花了好幾天查資料。所以特別把彙整所有資料的結果記錄下來。
即將進入廣告，捲動後可繼續閱讀
為什麼會看到廣告
留言0
查看全部
你可能也想看
Google News 追蹤
這篇內容，將會講解什麼是資料型態，以及與資料型態相關的知識。包括資料型態的簡介、實數、布林值、 字串、陣列。
Minimum Path Sum
給定一個矩陣，每個格子點代表經過的對應成本。
每回合可以往右移動一格或往下移動一格。
請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?
輸入給定一個已經從小到大排序好，而且彼此互質的整數陣列，
請問任取兩數分別當作分子、分母，第k小的分數是多少?
輸出請以 [分子，分母] 的形式回傳答案。
完成了Debug.log()的測試，接著還是要跟各位簡單講一下C#的一些規則，之後看程式會(比較)看得懂。
又講到變數？
在Unity中，變數是重要的工具，用來儲存和管理資料。讓開發者能夠靈活調整遊戲的行為和性能，減少代碼的重複性，使得遊戲開發更加高效和簡潔。透過使用變數，開發者可以輕鬆修改資料
這篇文章，會帶著大家複習以前學過的二進位DP框架，
並且以0~N的整數有幾個bit1，有幾個bit0的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
常見的考法
請問整數k有幾個bit1? 有幾個bit0?
請問整數0到整數N分別各有幾個bit1? 有幾個
最近會試著寫一些統整類的文章，
幫助讀者、觀眾整理、吸收、複習已經學習到的演算法框架。
找零錢框架
在以前學過的題目中，我們已經學會了考零錢的抽象思考邏輯與框架，就是試著用每一種銅板去湊出n元(也就是找零錢的過程)
寫成虛擬碼或演算法，找零錢用了幾枚銅板可以這樣表達
# 銅板數目累加
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧，時間複雜度為O(n)，空間複雜度為O(n)。
題目敘述
題目會給定一個鏈結串列的起始點，要求我們把其中區間總和為0的部分刪除掉。
例如
1→ 2 → -2 → 3 → 4
裡面有一段是2 → -2 區間總和為零，所以簡化刪除後變成
1→ 3 → 4
題目的原文敘述
測試範例
Example 1:
Input: head
題目敘述
題目會給定我們一個n值，要求我們列出從0 ~ n 之間，每個整數有幾個bit1，以陣列的形式返回答案。
例如n=3時
因為
0 = 0b 0
1 = 0b 1
2 = 0b 10
3 = 0b 11
輸出答案為[0, 1, 1, 2]
題目的原文敘述
測試範例
E
題目敘述
題目的情境是設計並且實現一個包含所有正整數的數據流，以set集合的方式存在。
數據流 = {1, 2, 3, 4, ..., ∞}
要求我們去實現定義好的function介面:
SmallestInfiniteSet()建構子，初始化這個包含所有正整數的數據流。
int po
這篇內容，將會講解什麼是資料型態，以及與資料型態相關的知識。包括資料型態的簡介、實數、布林值、 字串、陣列。
Minimum Path Sum
給定一個矩陣，每個格子點代表經過的對應成本。
每回合可以往右移動一格或往下移動一格。
請問從起點左上角 走到 終點右下角的最小路徑成本總和是多少?
輸入給定一個已經從小到大排序好，而且彼此互質的整數陣列，
請問任取兩數分別當作分子、分母，第k小的分數是多少?
輸出請以 [分子，分母] 的形式回傳答案。
完成了Debug.log()的測試，接著還是要跟各位簡單講一下C#的一些規則，之後看程式會(比較)看得懂。
又講到變數？
在Unity中，變數是重要的工具，用來儲存和管理資料。讓開發者能夠靈活調整遊戲的行為和性能，減少代碼的重複性，使得遊戲開發更加高效和簡潔。透過使用變數，開發者可以輕鬆修改資料
這篇文章，會帶著大家複習以前學過的二進位DP框架，
並且以0~N的整數有幾個bit1，有幾個bit0的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
常見的考法
請問整數k有幾個bit1? 有幾個bit0?
請問整數0到整數N分別各有幾個bit1? 有幾個
最近會試著寫一些統整類的文章，
幫助讀者、觀眾整理、吸收、複習已經學習到的演算法框架。
找零錢框架
在以前學過的題目中，我們已經學會了考零錢的抽象思考邏輯與框架，就是試著用每一種銅板去湊出n元(也就是找零錢的過程)
寫成虛擬碼或演算法，找零錢用了幾枚銅板可以這樣表達
# 銅板數目累加
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧，時間複雜度為O(n)，空間複雜度為O(n)。
題目敘述
題目會給定一個鏈結串列的起始點，要求我們把其中區間總和為0的部分刪除掉。
例如
1→ 2 → -2 → 3 → 4
裡面有一段是2 → -2 區間總和為零，所以簡化刪除後變成
1→ 3 → 4
題目的原文敘述
測試範例
Example 1:
Input: head
題目敘述
題目會給定我們一個n值，要求我們列出從0 ~ n 之間，每個整數有幾個bit1，以陣列的形式返回答案。
例如n=3時
因為
0 = 0b 0
1 = 0b 1
2 = 0b 10
3 = 0b 11
輸出答案為[0, 1, 1, 2]
題目的原文敘述
測試範例
E
題目敘述
題目的情境是設計並且實現一個包含所有正整數的數據流，以set集合的方式存在。
數據流 = {1, 2, 3, 4, ..., ∞}
要求我們去實現定義好的function介面:
SmallestInfiniteSet()建構子，初始化這個包含所有正整數的數據流。
int po