很讚的遊戲編輯器

Wang Tiles ---------------- 在研究關於可用於地圖生成的 波函數坍縮 演算法(Wave Function Collapse，底下簡寫WFC)的時候，又看到關於 王式磚 的資料(Wang Tiles，底下簡寫WT)。跟WFC比起來，WT比較容易理解和實作，所以我就先根據WT的原理實作了一個無限隨機地圖生成的測試。 關於WT，這個 網站 有詳細的介紹，同時也有許多tilesets可以用來作為測試資源。WT是數學家發明的遊戲，主要概念是邊緣匹配的tile連通拚接。每一個矩形tile有4個邊和4個角，所以有2種拼法，一種是邊匹配的拼法，一種是角匹配的拼法。 邊匹配 2Edge --------------------- 以邊匹配的拼法為例，每一個矩形tile的4個邊裡面，每個邊如果用0或1表示不同顏色，則總共有2x2x2x2共16種不同的tile。如下圖，生成tilemap時，如果一個tileA的上方的tileB的下邊是1，則tileA的上邊必須也是1，才能連通。同理，右方的tileC的左邊是1的話tileA的右邊也要是1，等等。整個tilemap的每一個tile都符合這個規則，就是一個符合WT的tilemap。 生成隨機tilemap的方式不只一種，一個簡單的方法是從左到右從上到下，一個一個tile生成。每一個新tile生成時，針對它的上方及左方2個己生成的tile的邊建立連通狀態(上方tile的下邊是1則新tile的上邊也需為1，左方tile的右邊為1則新tile的左邊也需為1)，而新tile的右方及下方的邊則隨機選擇0或1。 如下圖，針對tileX的4個邊依序上右下左以2進制編碼為1,2,4,8，這樣在生成tilemap時可以使用bit運算操作方便判斷。 這樣16種tile的編號也同時是它的編碼。如tile0表示4個邊都是0，tile8表示左邊是1其餘3邊是0，tile13表示上左下邊是1右邊是0，等等。底下是生成邊匹配的tilemap的虛擬碼。 void gen2EdgeWangTilesmap(cx, cy) {   foreach tile i of tilemap {     tile = 0;     if (tilemap[upper] & 4) {   ...

最開始的時候，good的繪圖管線為了簡化設計和實作，物件在繪製時是一個一個畫。每個物件都是以一個 glDrawArray 畫出來，也就是說花費一個draw call畫出來。 一開始針對繪圖最佳化的規劃除了 貼圖合併 之外，另一個主要的功能是批次繪製功能作最佳化。現在終於實作了這個功能，可以大幅減少draw calls。 原來繪製物件的方式是透過glVertexPointer傳入長寬各為1的單位矩形，再使用 glDrawArray 畫出物件。底下是簡單的記錄，一步步將原本的繪製物件的管線轉換為批次繪圖方式。 1，第一步就是先把glTranslate、glScale及glRotate等方法替換掉。首先弄個可以計算4*4矩陣的工具，把這些方法都透過矩陣運算，得到一個轉換矩陣。再使用glLoadMatrix載入這個自行計算得到的轉換矩陣，然後看看是不是結果和原來一樣，如果和原來的結果是一樣的話，表示這個轉換矩陣的計算是正確的。 使用glLoadMatrix載入轉換矩陣時，如果結果不對，可以試試對轉換矩陣作一次transpose轉換，看是不是因為使用的矩陣定義和OpenGL相反。 2，第二步要利用上面求出且驗證正確的轉換矩陣，來再進一步替換掉glLoadMatrix。也就是將傳入glVertexPointer的矩形的4個點，用轉換矩陣轉換成最終結果的座標，並且不需要使用glLoadMatrix將轉換矩陣傳遞給OpenGL，因為我們已經自己作了座標的轉換。再來驗證看看結果是否正確，沒有問的話就可以進入到下一步。 3，以上兩個步驟已經將OpendGL轉換矩陣的部份都替換掉，由我們自已的底層計算得到。將來再作進一步最佳化時，還可以把這個預先計算得到的轉換矩陣cache起來，只在狀態變動及需要時再重新計算，如此還可以進一步提高繪圖速度。 接下來就是要將每一個繪製物件的動作儘可能的合併起來批次處理。基本原則是準備大一點的buffer，針對vertex、texture coord及color，分別使用glVertextPointer、glTexCoordPointer及glColorPointer餵給OpendGL，在最後使用 glDrawArray 繪出時再指定實際繪出的數量即可，這樣就能夠大符減少draw call。 使用 glDrawArray 批次...

我現在要作一個實驗，模擬一個虛擬的世界，這個世界的構造很簡單，是一張10乘10的地圖，總共100個格子所組成。在這個世界裡面，會隨機產生金幣，機率是一半一半，也就是說大約在這100個格子裡面，平均會有50個金幣。還要模擬某種生物，這種生物的生存目的很簡單，就是儘可能的吃金幣，因為這個世界的食物只有金幣。能夠吃愈多金幣的生物就愈能夠生存下來並把它的基因繼續傳播下去。生活在這個世界的生物就把它命名為吃金幣的人...吃金幣的人在這個世界能作的事情很有限，除了吃金幣外，他只能作上下左右四種方向的移動，每次只能移動一個格子。 這個實驗的目的是想辨法找到一個最佳的路徑搜尋方法，讓吃金幣的人儘可能吃愈到愈多的金幣。為了評估吃金幣的人的路徑搜尋方法有多好，需要有一個可以量化的方法。所以就很簡單的設定，如果吃金幣的人每吃到一個金幣就能獲得10分，分數愈高就表示它的路徑搜尋方法愈好。當然也不能讓吃金幣的人任意的作無限次移動，因為這樣一來就沒有意義了，因為吃金幣的人一定可以吃光世界上所有金幣。所以我們要限制移動次數，比如說200次，每200次移動後再來作評分。 我們將會使用基因算法(genetic algorithm)，讓吃金幣的人自行進化，得到一個認為最棒的路徑搜尋方法。 基因算法的主要精神是，對於所要解決的問題以模擬生物界物競天擇適者生存的自然法則，讓所摸擬的人工生物自行進化出在模擬世界中的優勢物種，也就是得到所求的最佳解。不過這裡講到的進化這二個字有誤導的嫌疑，實際上這也是大多數人對於進化及演化之間的誤解。進化這二字裡面隱含了方向性，而事實上演化是沒有方向性的，演化是生物對生存環境的適應。生物會演化成什麼樣子，沒有任何的目的性和方向性，這裡面帶有隨機性，主要取決於環境變因。 自然選擇和變異再加上時間是演化的基本原則，所以我們將要模擬的程式也是使用到這幾個基本原則。雖然實際上的細節，和真實世界生物界的演化並不相同，但因為我們利用這幾個演化的基本原則來模擬我們的世界，結果也會得到類似的結果。我們可以看到我們所模擬的吃金幣的人果真在這個金幣世界裡面，慢慢的演化出愈來愈聰明的路徑搜尋方法。而同自然界的生物演化一樣，你甚至無法知道也無法分析它到底是怎麼辨到的。 前面提到這個世界是個10x10的地圖，共有100個格子，在這個世界面裡有會隨機產生的金幣。如果一個格子上...

在 猜數字遊戲 (電腦猜人) 這篇文章裡，最後提到怎麼從10個數字裡面挑出4個數字的組合的方法。 這個方法很簡單，0x3ff這個數字共有10個位元1(bit)，我們可以把這10個位元和0-9這10個數字作一一對應。用一個迴圈來找從1到0x3ff這些數字裡面，有那些數字是包含4個位元1，也就是要找的。例如0xf這個數字，2進制是0000 0000 0000 1111，最右邊4個bit都是1，根據1的位置轉換後變成3210這個數字。同理0x17這個數，2進制是0000 0000 0001 0111也是4個bits為1，轉換後為4210這個數字。依此類推。 這個方法用來選取小範圍數的組合還可以，可是一但數字大了，效能就太慘不忍睹了。例如以今彩539的可能組合為例，全部1-39共39個數字裡面挑出5個，全部共有575757種組合。雖然57萬多種組合看起來不大，但是以上面的方法來找，則要搜尋的迴圈範圍一下暴漲為2^39才能得到這57萬組結果，這是一個天文數字。所以這個方法就不可行了，勢必要使用更有效率的演算法才行。 稍微研究後，很幸運的不到10鐘就讓我找到了一個看來可行的演算法，很快的寫了一支小程式來測試。測試結果果然很理想，以C(39,5)作計算測試，不到1秒鐘的時間就得到正確結果！ ; 底下是演算法的概述，同樣以10個數字取組合為例： * 考慮最簡單的情況，作10取1組合 0 1 2 3 4 5 6 7 8 9 10個數字共有10個位置可以放入數字1，從最左邊的位置開始，共有10個位置可選擇，所以總共有10種可能。 用計算組合的公式驗算一下，C(10,1)=10!/1!(10-1)!=10!/1!9!=10 * 考慮10取2的情形 因為第一個1有0-9共10個位置可以選擇，如果第一個1選擇放入位置0，則第二個1有1-9共9種位置可以選擇放入。因為位置0的情況已經考慮過，所以接下來只要往後看不再往前看，需要排除掉已考慮過的位置。接著考慮如果第一個1選擇放入位置1，則第二個1排除位置0和1後還有2-9共8種選擇。依此類推，根據第一個1的位置選擇不同，則有9(p0), 8(p1), 7(p2), 6(p3), 5(p4), 4(p5), 3(p6), 2(p7), 1(p8), 0(p9)種選擇，小括號內的p0-9為第一個1的選擇位置...

將小圖合併成大圖是最佳化的一種技巧，合併的時機可以是在程式編譯時期，透過工具或者是人工方式作到。或者也能在程式執行時期，由程式自動將小圖合併。這牽涉到怎麼將小圖合併成大圖的演算法，同時在繪圖時也需要支援怎麼從大圖裡抽取出原本是小圖的相關資訊等等。 這裡只對小圖合併大圖作簡介，提供一個簡單的演算法。 首先想到的是很直接的作法： 假設大圖是一張矩形，而小圖也都是矩形。一開始有張空白的大圖，當第一張小圖要擺進大圖時，先確認這張小圖是否可以放進這張空白的大圖裡，如果答案是可以的話，則將這張小圖擺進大圖的左上角位置。接著將空白大圖剩下來的空白區域切割成二塊空白矩形。切割的方法是，小圖以右及小圖以下作分界。 如圖所示，把1號小圖放進大圖後，剩下來的空白區域可以依小圖位置往右往下切成AB二塊較小的空白區塊。 接下來繼續同樣的步驟依序再擺入其它的小圖，如下圖所示。2號小圖可以擺的進去原來切出來的A號空白區塊，把2號小圖放進去後，剩下來的空白區域再以同樣的方法再切成AB二塊空白區塊。 依此累推，將各小圖一個一個塞進去，如果某張小圖找不到可以塞的進去的空白區塊，則再新開另一張空白大圖即可。 因為每次會把剩餘的空白區域切割成二塊，所以很自然的在實作上可以應用一個二元樹的結構，將每個節點分成左右二個子樹，底下列出主要的虛擬碼。 Node::Add(Image) {   if (NotImageAdded()) {     if (IsImageFit(Image)) {       AddImage(Image);       Left = new Node(BoundLeft + ImageWidth, BoundTop, BoundRight, BoundTop + ImageHeight);       Right = new Node(BoundLeft, BoundTop + ImageHeight, BoundRight, BoundBottom);       return true;     }     return false;  ...

程式(sleepsort.bash): while [ -n "$1" ] do   (sleep "$1"; echo "$1") &   shift done wait 執行例: user@your-c24a217e1d ~ $ bash sleepsort.bash 4 1 3 1 3 4 user@your-c24a217e1d ~ $ bash sleepsort.bash 4 2 5 1 3 1 2 3 4 5