很讚的遊戲編輯器

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

把十年前的作品拿出來，試著build看看。其實很早就想這樣作了，這樣作的目的很單純，因為這是一個具體而微的on-line game，可以以它為基礎繼續作研究實驗。

在 猜數字遊戲 (電腦猜人) 這篇文章裡，最後提到怎麼從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的選擇位置...

之前玩了一陣子的連連看小遊戲，不過一直沒有去想想這類型的遊戲的主要gameplay的原理。現在花了點時間思考一下，研究看它的模式，設計了一個簡單的演算法，寫了支小程式來試試，效果基本上還不錯。 基本玩法是這樣子的。地圖大小是NxM，填滿X種類的圖形，每一個圖形一定可以跟另一個同樣的圖形作配對。配對方法是找出一條二個同樣圖形之間的連線，就可以同時把這二個圖形消除。連線最多只允許二個轉折，中間必須暢通。 以下對基本判定原理作概述，如下圖。 現在要找出A點和B點之間的連線。r0和rn是上邊界及下邊界，c1-c2線在r0至rn之間滑動。只要確定A-c1及B-c2及c1-c2三條線是暢通，即找到連線。若找不到連線，再以同樣原理找垂直方向一次。 若水平或垂直方向都找不到，則連線不存在。

這是數獨解題技巧裡面的高級技巧，比X-Chains還再高一點點。會這個技巧的話，就可以解4或5顆星的題目了。 這個用來測試的題目，用 KillSudoku 來解可以解出，中間使用了2次Naked Subset，1次 W-Wings ，1次 X-Chains ，2次 XY-Chains 。所以算起來，這一題應該是有5顆星的題目。 附帶一提，目前找鍊的演算法並沒有去找一條最短的鍊，所以可以看到用 KillSudoku 解的時候，第36的步驟找到一條超長的鍊，這條鍊足足由13條連線構成，要是沒練過的話，絕對頭昏眼花，找不出這樣的鍊來的。 實際上在這個步驟裡，是可以找到另一條更短的鍊。不過目前以先能work，之後有空會再改進演算法的部份。

作了幾個更新。 １，圖形解碼(Image Decoder) 原本Good使用來解碼圖形的程式庫是 ImageStone ，這是個C++的影像處理程式庫。當初會用它，是因為容易使用。但因為只是用來載入圖形，所以在作 PSP版移植 時，就另外作了一個簡單的image decoder，不過當時只作了 PNG 格式的支援就沒再繼續進行。 現在繼續完成了 BMP 及 JPEG 格式的支援。 BMP：BMP的格式比較簡單些，是自行實作。 PNG ：使用 libpng 。 JEPG：使用 libjpeg 。 目前還缺 GIF 的支援，另外取消 TGA 格式支援。 而在Windows平台上，則直接使用系統提供的 GDI+ 來作圖形解碼。將ImageStone替換掉後，code size縮減了約40k。 ２，繪圖模組(Render Pipe) 基於前次的 rect packing 的研究結果，利用昨天台風假在家，花了幾個小時將演算法整合進到GoodEngine的繪圖模組裡，過程相當順利。 以範例遊戲 25940m 為例，遊戲全部使用了9張貼圖。以原本的繪圖引擎來說，這9張貼圖會被載入並建立成各自獨主的9張貼圖。如此在繪圖時，貼圖間的切換就會相當頻繁。現在加上texture packing支援後，9張貼圖可以全部合併到1張1024x1024的貼圖內，這樣就能省掉切換的時間提升速度，同時也省掉額外貼圖記憶體的浪費。 3，新增範例 新增了一個簡單的範例solar，建立簡單的太陽系系統示範物件階層架構的使用。 這個範例建立三個貼圖物件用來代表太陽、地球及月球。月球繞行parent object地球轉，地球繞行parent object太陽旋轉，而太陽慢慢自轉。

這題數獨(sudoku)題目估計為4+顆星，有點難度。解題需要應用多種技巧，過程非常精彩有趣，是個好題。 底下使用 KillSudoku 作詳細圖解。 １，使用基本排除法則，可以簡單填入６個數字。到此為止，開始使用 候選數法 來解題。如下所示，為填入６個數字後的狀態圖。 ２，如下圖，使用進階排除法，在第９列和第４行可以先排除幾個候選數。 ３，如圖，在第２行有一個 Naked Subset (3,4)，可以對3,4候選數作排除。附帶提一下，反過來看在同一行裡面也可以說有另一個Hidden Subset(2,5,8)存在。Naked Subset和Hidden Subset常是一體二面同時存在，只不過對我們來說，Naked Subset是相對比較容易看的出來。 排除第２行的3,4後，又可以對第２列以外的3作排除，如下圖。 ４，接著，在第５行又發現了一個 Naked Subset (3,7,8)。 對第５行三個Subset以外的候選數3,7,8作排除後，又接著產生可以對第５行以外的3作排除。 ５，這一題解到此為止，開始進入高潮。大部份能解到3顆星題目的人，猜想應該就此卡住。以下開始需要應用更高級的鍊技巧，才能夠繼續進行。 應用X-Chains鍊技巧，可以找到一條由４條強連結組成的鍊，可以排除候選數2。這裡的鍊指的是由２條以上的強連結組成，而所謂的強連結是指在同一行、或同一列或同一個Box裡，由唯二的候選數構成的連結。如上圖中的第９行中，只有二個2，這二個2構成一條強連結。為什麼說這是一條強連結？因為在這條連結的AB二個端點中，肯定會有一個2存在，要麼是A點要麼是B點。鍊技巧就是將多條強連結串連起來作候選數排除的技巧，而X-Chains是高級的鍊技巧裡面的基本技巧。 接上圖，這樣一來就又可以應用基本排除方法，填入３個數字，如下圖所示。 ６，接下來就是本題最精彩的部份，以下需要連續找到３條鍊，才能繼續往下解。 ７，找出３條鍊後，剩下來的部份就沒什麼特別的了，只需要應用基本法就能把所有剩餘數字填完。