我在這里問的是一個演算法問題。我不是在詢問如何用我正在使用的編程語言或我目前正在使用的框架和庫來做這件事的細節。我想知道原則上如何做到這一點。
作為愛好，我正在開發 1992 年第一人稱射擊游戲 Wolfenstein 3D 的開源虛擬現實重制版。我的程式將支持以 90 年代原始格式制作的 WOLF3D 的經典模組和地圖包。這意味著我的程式不會提前知道地圖將是什么。它們在運行時從用戶提供的檔案中加載。
Wolfenstein 3D 地圖是通常為 64x64 瓦片的 2D 方形網格。假設我有一個 2D 布爾陣列，如果玩家可以遍歷特定的圖塊，則回傳 true；如果無論游戲中發生什么，該圖塊將永遠不可遍歷，則回傳 false。
我想為現代游戲引擎生成矩形碰撞物件，以防止碰撞到地圖上的不可穿越的瓷磚。現在，我在每個墻磚的每個表面上都有一個小的碰撞物件，旁邊有一個可移動的磚，這是非常低效的，因為它產生的碰撞物件比需要的要多。相反，我應該擁有較少數量的大矩形，它們填充網格上的所有正方形，其中我提到的 2D 陣列具有錯誤值以指示不可遍歷。
當我搜索任何可能針對類似問題進行的演算法或研究時，我發現了很多關于矩形打包的資訊，用于制作游戲的紋理圖集，將矩形打包成正方形，但我還沒有找到任何試圖將最少數量的矩形打包到任意一組選定/標記的方形瓷磚中的東西。
我想到的幼稚方法是首先制作代表 64 行的 64 個矩形，然后切掉任何可遍歷的正方形。但我懷疑一定有一種演算法可以做得更好，這意味著它可以用較少數量的矩形填充相同的空間。也許從我的幼稚方法開始，然后檢查每個矩形是否有可以合并的相鄰矩形？但我不確定采用這種方法能走多遠，或者它是否會真正減少矩形的數量。
結果不一定是完美的。我只是在這里釣魚，看看是否有人有任何魔術可以讓我超越天真的方法。
有沒有人這樣做過？這叫什么？只要知道我什至需要談論的一些詞匯是有幫助的。謝謝！
（稍后編輯）
這是一些以逗號分隔的值的示例輸入。1 表示必須用矩形填充的區域，而 0 表示不應用矩形填充的區域。
我希望結果將是一個包含 4 個整數的集合串列，其中每個集合代表一個矩形，如下所示：
- 第一個整數是矩形左/西邊緣的 x 坐標。
- 第二個整數將是矩形頂部/北部邊緣的 y 坐標。
- 第三個整數是矩形的寬度。
- 第四個整數是矩形的深度。
我的程式是用 C# 撰寫的，但我確信我可以用普通的主流通用編程語言或偽代碼翻譯任何東西。
uj5u.com熱心網友回復：
Mark all tiles as not visited
For each tile:
skip if the tile is not a top-left corner or was visited before
# now, the tile is a top-left corner
expand right until top-right corner is found
expand down
save the rectangle
mark all tiles in the rectangle as visited
不管它看起來多么簡單，它可能會生成最少數量的矩形——這僅僅是因為我們每對頂角至少需要一個矩形。
為了更快地向下擴展，預先計算一個表格，該表格包含所有元素頂部和左側的總和（也稱為積分影像）。
對于不重疊的矩形，n x n“影像”的最壞情況復雜度不應超過O(n^3). 如果矩形可以重疊（會導致它們的數量減少），則不適用積分影像優化，最壞的情況是O(n^4).
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409374.html
標籤：
下一篇：Julia中的合并排序實作