2013年11月5日 星期二

加強除錯訊息機制 Enhanced debug/trace message

* 增強Good.Trace語法。

原本若想要透過Good.Trace輸出格式化的訊息,需要利用間接的方法,經由string.format格式化訊息,再傳給Good.Trace輸出,現在可以直接使用格式化輸出。

Good.Trace(string.format('id = %d', idObj))
Good.Trace('id = %d', idObj)

以上二種方式都可接受。

* 編輯器內建播放器支援即時顯示除錯訊息。

若從編輯器執行遊戲測試(F5),則透過Good.Trace丟出的訊息或者是系統訊息都可以在遊戲中檢視,而不必跳出遊戲後再到Output視窗查看訊息。同時,也能透過Ctrl+Alt+O即時開關除錯訊息。





2013年10月29日 星期二

新增範例: 連連看遊戲(link)

* 新增範例:連連看遊戲

這是根據之前的研究,改以Good實作而成的範例。這個範例實作出gameplay的部份,只需要新增新的關卡就可以一直玩下去。


* 關卡編輯器(LevelEditor)新增自訂貼齊格線大小

這個功能是因應編輯新的連連看link範例而新增的功能。因為link使用的tileset的tile大小是24x34,而原來的關卡編輯器格線都是8的倍數。增加自訂功能後,方便編輯。

* 線上API參考手冊改連至WIKI

現在終於把API參考手冊都搬到wiki上了。

* 除此之外,還修正了一些bug..

2013年10月27日 星期日

WIN32 EditBox顯示行號

前面介紹過在.NET平台使用C#語言怎麼讓TextBox顯示行號,這篇文章則是介紹怎麼用WIN32的方式在EditBox上顯示行號。


基本概念如下:

首先,透過EM_SETMARGINS設定EditBox的LeftMargin,讓EditBox的內容往右縮排保留一定空間。接著處理WM_PAINT訊息,先透過DefWindowProc讓系統預設處理後,接著我們再疊畫上行號的部份。底下虛擬碼使用CEdit成員。
    int FirstLine = GetFirstVisibleLine();
    int FirstLineIndex = LineIndex(FirstLine);
    POINT ptBottom = {0, rcClient.bottom - GetSystemMetrics(SM_CYHSCROLL) - 1};
    int LastLineIndex = CharFromPos(ptBottom);
    int LastLine = LineFromChar(LastLineIndex);
上面的程式片段用來計算目前顯示的行號範圍。
    for (int i = FirstLine; i <= LastLine; i++) {
      int Index = LineIndex(i);
      POINT pos = PosFromChar(Index);
      if (-1 == pos.x) {
        break;
      }
      DrawText(LineNumber, Pos);
    }
知道要顯示的行號範圍後,接著再把它們畫出來。到此為止就完成的行號的顯示工作。但是,在測試時會發現當EditBox作水平捲動,或Selection變更時有重繪的問題。

一個簡單的解決辨法是,設定一個Timer。每當TextSelection變更時就作重畫動作,這樣就可以消除重繪問題。
  void OnTimer(UINT_PTR nIDEvent)
  {
    int Start, End;
    GetSel(Start, End);
    if (Start != nStartChar || End != nEndChar) {
      DrawLineNumbers();
      nStartChar = Start;
      nEndChar = End;
    }
  }

2013年10月18日 星期五

改良動作編輯器(Sprite Editor)

* 修正API Good.Clone的錯誤。

* 改良動作編輯器(Sprite Editor),將原來右上角的Preview小視窗整合到編輯區。

如下圖,是原來的設計。


改成如下新的設計。


2013年10月6日 星期日

連連看遊戲原理

之前玩了一陣子的連連看小遊戲,不過一直沒有去想想這類型的遊戲的主要gameplay的原理。現在花了點時間思考一下,研究看它的模式,設計了一個簡單的演算法,寫了支小程式來試試,效果基本上還不錯。


基本玩法是這樣子的。地圖大小是NxM,填滿X種類的圖形,每一個圖形一定可以跟另一個同樣的圖形作配對。配對方法是找出一條二個同樣圖形之間的連線,就可以同時把這二個圖形消除。連線最多只允許二個轉折,中間必須暢通。

以下對基本判定原理作概述,如下圖。


現在要找出A點和B點之間的連線。r0和rn是上邊界及下邊界,c1-c2線在r0至rn之間滑動。只要確定A-c1及B-c2及c1-c2三條線是暢通,即找到連線。若找不到連線,再以同樣原理找垂直方向一次。

若水平或垂直方向都找不到,則連線不存在。

2013年9月21日 星期六

KillSudoku 4顆星精彩數獨 (三) - XY-Chains

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

2013年9月14日 星期六

KillSudoku 4顆星精彩數獨 (二) - W-Wings

這一題很有趣,花了20多分鐘終於解出來。這裡面用到了幾個高級技巧,最主要的技巧是W-Wings。後來用KillSudoku來檢驗看看,結果發現我還是太遜,腦袋昏昏不夠靈,中間多走了一些可以省略過的步驟。

在用KillSudoku檢驗這題的時候,發現W-Wings的判定存在一個bug,之前測試時沒有發現到,順便解掉。

附帶提一下,目前KillSudoku加上了可以從網址列取出謎題初始值,這樣就方便多了,不必每次都要先手動把題目輸入再解題。

格式如下:http://www.smallworld.idv.tw/misc/KillSudoku.html?s=1&p=800010000520900080076002000009500600340090025005008400000200540010009037000080006

s=1表示開始就作solve
p=<題目內容>由,分隔的最多81個數字,0-9

2013年9月1日 星期日

寶石方塊外掛 自動打

昨晚花些時間,繼續實作拖了很久的GameOver檢查,原理很簡單。因為GameOver的檢查會建立一個可移動消除方塊的Map,正好可以拿來作Autoplay,所以今早又花點時間順便實作一下Autoplay。效果還ok,錄了段影片。


2013年8月22日 星期四

Image Decoder and Render Pipe Improvement

作了幾個更新。

1,圖形解碼(Image Decoder)

原本Good使用來解碼圖形的程式庫是ImageStone,這是個C++的影像處理程式庫。當初會用它,是因為容易使用。但因為只是用來載入圖形,所以在作PSP版移植時,就另外作了一個簡單的image decoder,不過當時只作了PNG格式的支援就沒再繼續進行。


現在繼續完成了BMPJPEG格式的支援。

BMP:BMP的格式比較簡單些,是自行實作。
PNG :使用libpng
JEPG:使用libjpeg

目前還缺GIF的支援,另外取消TGA格式支援。

而在Windows平台上,則直接使用系統提供的GDI+來作圖形解碼。將ImageStone替換掉後,code size縮減了約40k。

2,繪圖模組(Render Pipe)

基於前次的rect packing的研究結果,利用昨天台風假在家,花了幾個小時將演算法整合進到GoodEngine的繪圖模組裡,過程相當順利。


以範例遊戲25940m為例,遊戲全部使用了9張貼圖。以原本的繪圖引擎來說,這9張貼圖會被載入並建立成各自獨主的9張貼圖。如此在繪圖時,貼圖間的切換就會相當頻繁。現在加上texture packing支援後,9張貼圖可以全部合併到1張1024x1024的貼圖內,這樣就能省掉切換的時間提升速度,同時也省掉額外貼圖記憶體的浪費。


3,新增範例

新增了一個簡單的範例solar,建立簡單的太陽系系統示範物件階層架構的使用。

這個範例建立三個貼圖物件用來代表太陽、地球及月球。月球繞行parent object地球轉,地球繞行parent object太陽旋轉,而太陽慢慢自轉。


2013年8月7日 星期三

KillSudoku 4顆星精彩數獨詳解 - 鍊技巧

這題數獨(sudoku)題目估計為4+顆星,有點難度。解題需要應用多種技巧,過程非常精彩有趣,是個好題。


底下使用KillSudoku作詳細圖解。

1,使用基本排除法則,可以簡單填入6個數字。到此為止,開始使用候選數法來解題。如下所示,為填入6個數字後的狀態圖。


2,如下圖,使用進階排除法,在第9列和第4行可以先排除幾個候選數。



3,如圖,在第2行有一個Naked Subset(3,4),可以對3,4候選數作排除。附帶提一下,反過來看在同一行裡面也可以說有另一個Hidden Subset(2,5,8)存在。Naked Subset和Hidden Subset常是一體二面同時存在,只不過對我們來說,Naked Subset是相對比較容易看的出來。


排除第2行的3,4後,又可以對第2列以外的3作排除,如下圖。


4,接著,在第5行又發現了一個Naked Subset(3,7,8)。


對第5行三個Subset以外的候選數3,7,8作排除後,又接著產生可以對第5行以外的3作排除。


5,這一題解到此為止,開始進入高潮。大部份能解到3顆星題目的人,猜想應該就此卡住。以下開始需要應用更高級的鍊技巧,才能夠繼續進行。


應用X-Chains鍊技巧,可以找到一條由4條強連結組成的鍊,可以排除候選數2。這裡的鍊指的是由2條以上的強連結組成,而所謂的強連結是指在同一行、或同一列或同一個Box裡,由唯二的候選數構成的連結。如上圖中的第9行中,只有二個2,這二個2構成一條強連結。為什麼說這是一條強連結?因為在這條連結的AB二個端點中,肯定會有一個2存在,要麼是A點要麼是B點。鍊技巧就是將多條強連結串連起來作候選數排除的技巧,而X-Chains是高級的鍊技巧裡面的基本技巧。

接上圖,這樣一來就又可以應用基本排除方法,填入3個數字,如下圖所示。


6,接下來就是本題最精彩的部份,以下需要連續找到3條鍊,才能繼續往下解。




7,找出3條鍊後,剩下來的部份就沒什麼特別的了,只需要應用基本法就能把所有剩餘數字填完。


2013年7月25日 星期四

Texture packing algorithm

將小圖合併成大圖是最佳化的一種技巧,合併的時機可以是在程式編譯時期,透過工具或者是人工方式作到。或者也能在程式執行時期,由程式自動將小圖合併。這牽涉到怎麼將小圖合併成大圖的演算法,同時在繪圖時也需要支援怎麼從大圖裡抽取出原本是小圖的相關資訊等等。

這裡只對小圖合併大圖作簡介,提供一個簡單的演算法。

首先想到的是很直接的作法:

假設大圖是一張矩形,而小圖也都是矩形。一開始有張空白的大圖,當第一張小圖要擺進大圖時,先確認這張小圖是否可以放進這張空白的大圖裡,如果答案是可以的話,則將這張小圖擺進大圖的左上角位置。接著將空白大圖剩下來的空白區域切割成二塊空白矩形。切割的方法是,小圖以右及小圖以下作分界。


如圖所示,把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;
  }
  if (Left->Add(Image)) {
    return true;
  }
  if (Right->Add(Image)) {
    return true;
  }
  return false;
}



如上圖,是依此演算法實作出來的一個測試程式的結果。隨機產生100個15x15~165x165之間的小圖,想辨法擺進一張1024x1024的大圖。
 
可以看到結果有22張小圖放不進去大圖裡,但從結果的顯示來看,這張大圖裡似乎有太多空白區域因為切割的方式,造成太多小碎片以致於浪費了,很難再塞入大一點的小圖。所以這個演算法,有很大的改進空間。

;

上一個演算法裡面,切割剩餘空白區域的方式很簡單的只根據加入的小圖的大小,切成右及下二塊,很容易造成小碎片。所以如果改善切割的方式,減少碎片的話,就可以塞入更多的小圖到大點裡去。

原來的方法一律都是以小圖的底的延長線當作是切割線,切出在小圖右及下的二塊區域。現在改善切割的方法,切割時同時還要考慮切的方向。改善方法以計算小圖的寬高及區塊的寬高差異量來決定切割線是水平或垂直方法。

改良後的演算法如下。

Node::Add(Image)
{
  if (NotImageAdded()) {
    if (IsImageFit(Image)) {
      AddImage(Image);
      if (BoundWidth - ImageWidth > BoundHeight - ImageHeight) {
        Left = new Node(BoundLeft + ImageWidth, BoundTop, BoundRight, BoundBottom);
        Right = new Node(BoundLeft, BoundTop + ImageHeight, BoundLeft + ImageWidth, BoundBottom);
      } else
{
        Left = new Node(BoundLeft + ImageWidth, BoundTop, BoundRight, BoundTop + ImageHeight);
        Right = new Node(BoundLeft, BoundTop + ImageHeight, BoundRight, BoundBottom);
      }
      return true;
    }
    return false;
  }
  if (Left->Add(Image)) {
    return true;
  }
  if (Right->Add(Image)) {
    return true;
  }
  return false;
}
只需一點點改善,就可以得到更好的結果,可以在同一張大圖裡塞入更多的小圖。如下圖所示,是改良後的一個測試結果。


2013年6月4日 星期二

java實作多人連線麻將

斷斷續續用java寫了一個多人連線麻將。目前有一個Server,一個連線測試用Client,及一個單機測試用Client,全都是用java實作的Console程式。當進行中的牌局有人離開,則AI會接手打牌,直到所有人離開或打完一圈。


目前考慮使用WebSocket作一個Client。等有空再看看,已經作了點相關研究

2013年4月18日 星期四

寶石方塊實驗 2



這個實驗使用更多的script控制再加上STGE粒子效果測試。

測試由C++程式碼叫Good API產生方塊,當方塊消除時透過script呼叫STGE API執行產生粒子的script,再生成色塊物件和粒子連結作出爆炸效果。

2013年3月26日 星期二

快速2D空間搜尋



基本概念是將空間切成小格子,搜尋時先找出搜尋涵盖了那些小格子,再從這些小格子去查找即可達到快速查找的目的。




2013年3月13日 星期三

寶石方塊實驗

寶石方塊演算法的部份使用C++實作, 繪圖部份使用Good, 背景移動的綠色方塊在Good裡定義從C++程式碼裡透過建立, 笑臉由Good建立, 縮放由C++程式碼控制。



2013年1月31日 星期四

HTML5 Kill Sudoku

花了二晚將前次發表的KillSudoku移植成Web版,這次利用HTML5的繪圖功能取代掉原來簡單的文字模式顯示,改良成更好的圖形顯示。

這個版本實作了簡單的編輯功能,可以很容易的輸入或創造謎題(滑鼠左鍵輸入再點一下取消輸入)。不過目前還沒有實作檢查輸入的題目是否有唯一解,所以如果嘗試去解沒有唯一解的題目時可能有會不可預期的結果。

這次增加了一個新的Pattern:XYZ Wings,不過現在懶的介紹了~



目前只在Chrome及Safari上試過。

(試試看)

2013年1月15日 星期二

Kill Sudoku

前陣子斷斷續續的玩了一陣子數獨(sudoku),才終於把安裝在我的野火機裡的OpenSudoku的全部謎題解到只剩下一題VeryHard等級的謎題留作紀念。

在解這些題目的過程中一直有個想法,就是想要也自己寫個可以解數獨的小程式。數獨解答機在網路上很多,大多是使用回溯法為基礎的演算法製作的,也就是基於試誤法或窮舉法的方式,和我們一般在解題時使用的方法不同。我想要寫的是一個可以像人類一樣,使用各種技巧來解數獨謎題的程式,解題過程的每一個步驟都要清楚條列出來,這樣這個程式也可以用來作學習用途。

這個想法一直到最近才動手,目前還只是初步階段,寫了一支文字模式的小程式,可以從文字檔案裡讀出一個數獨謎題,將解題過程一個一個步驟都顯示出來,如下圖所示。將來可以寫成圖形化的APP或者是Web的型式,以更豐富的圖式方式來呈現。(HTML5 KillSudoku)


這個程式是基於使用候選數法來製作的,所以從上圖可以看到個一個還未解出答案的格子裡都會列出全部的可能的數字,這些數字就叫作候選數。

~~~

一道數獨謎題是由9(row)x9(column)=81個格子(cell)組成,每一個cell裡可以填入1~9中的一個數字。這9x9個格子裡面,又可以再分成較小的9(box)個3x3的格子。


如上的一個9x9宮格圖所示,左側數字1~9為每一列(row)的編號,上方小寫英文字母a~i為每一行(column)的編號,b1~b9為每一個小九宮(box)的編號。

以上定義了幾個基本名詞:cell, row, column, box,再加上前面所提到過的候選數(candidate),就是我們全部需要知道的幾個定義。至於數獨的規則部份,這裡就不再複述。

~~~

這個程式的基本原理很單純,只是把我們平常在解數獨題時所用到的手法程式化而已。例如要找唯一數存不存在,就一行一行一列一列的去找看看某數是不是在這一行或這一列裡面是唯一的,如果是的話那就把這個數填入。目前版本的程式還很陽春,只實作了7種pattern,下面一一介紹。使用這7種找pattern的方法最多可以解出初級到中級左右的題目。

在開始找pattern前,需要把輸入資料作一些轉換成內部資料的處理。謎題的輸入是81個數字,由左至右,由上而下,一列一列的由上往下輸入。每一個數字範圍為0~9,0表示這個cell是空的,待填的,1~9則表示這個cell的確定數。

這81個數字讀入後,在程式裡面使用一個一維陣列儲存(int cell[]),同時再以另一個同樣維度的陣列,用來儲前面提到過的候選數(int candidate[]; // bitset)。如果cell[n] != 0,那candidate[n]就不看。如果cell[n] == 0,那就是說cell[n]是空的,那candidate[n]裡存的就是cell[n]的候選數,其中n = 0~80。

整支程式基本上作的事情就是根據程式定義的pattern,想辨法去消減候選數,當某個cell的候選數消減到只剩下一個的時候,那就可以將這個最後的數填入這個cell,變成確定數。程式執行時會不斷的重複找pattern的動作,直找無法再找到任何pattern為止。結果有二種,一種是全部解完,一種是卡關,需要加入更多pattern才能繼續。這是程式的基本運作概念。


Single

Single是唯一候選數的pattern,這個pattern有二種情況:

  1. 顯式的(naked):在這個情況下,這個候選數是這個cell裡唯一的一個候選數。
  2. 隱式的(hidden):這表示說,在這個cell裡面還有其它的候選數存在,但因為在這個cell所在的column或row或box裡面,這個候選數是唯一的,所以可以忽略其它候選數,填入這個唯一數。

如上圖,cell f2裡面只有一個候選數8,所以可以將8填入f2。


如上圖,在紅線框的這個box裡面,候選數5只存在cell c1裡面,所以可以將5填入c1。


Claiming

在一個row或column裡面,如果某一數的候選數都集中在同一個box裡面,則在這個box裡面在這個row或column以外的候選數都可以消除。


如上圖所示,候選數7在row9裡面都集中在box7裡,這表示說在box7裡面候選數7只可能出現在row9裡面,因此在box7裡面row9以外的候選數7都可以消除。


Pointing

這個技巧和Claiming類似,差別只在於Pointing是先由box的角度來看。如果在一個box裡面的某個候選數都集中在同一個row或column的話,則在這個row或column上的其它候選數都可以消除。


如上圖,在box7裡候選數3只存在row8裡面,也就是說在整個row8上面候選數3只可能出現在box7裡面,因此在row8上在box7以外的候選數3都可以被消除。


Set

Set(或Subset)是在找數字組合的pattern,Set的長度可以是2~4。長度為n的Set可以定義一組由這幾個數字構成的Subset,Subset的長度可以是2~n。

例:3及9二個數字構成的Set,長度為2,Subset只有一種39。
例:1,4及7三個數字構成的Set,長度為3,它的Subset可以是14、17、47及147。

Set可以是顯式及隱式二種。


對於顯式的Set,假如構成長度為n的Set的Subset只出現在n個不同的cell裡面的話,則其它cell裡面的Set候選數都可消除。如上圖所示為一個顯式的Set的例子。這是由5及7構成的Set,出現在box3裡的g2及i3 cell裡面。換句話說,5及7只可能出現在這二個cell裡面,因此其它的cell裡面的5或7都可以消除。


對於隱式的Set,假如構成長度為n的Set的Subset只出現在n個不同的cell裡面的話,則在這n個cell裡面的其它候選數都可以消除。如上圖是一個隱式Set的例子,在這個例子裡面2及8只出現在d4及f6二個cell裡面,因此構成了一個Set的pattern,所以除了2和8以外的數字都可以從d4及f6二個cell裡面消除,只留下2及8。


X Wings

若某個候選數同時出現在二個row和二個column上共4個cell裡面,並且這4個cell都處在不同的cell裡面。若其中二個row或二個column裡的這個候選數都是唯二的,那麼在對應的二個column或二個row裡面的這個候選數都可以被消除。


如上圖,在column e和column h都各有二個候選數5,並且這二對5也同時存在於row 2和row 5上,因此構成XWings pattern。

因為在column e上候選數5要嘛出現在e2要嘛出現在e5,在column h上候選數5要嘛出現在h2要嘛出現在h5。當5出現在e2時,h5必為5,e5及h2就不能為5(互斥);當5出現在e5時,h2必為5,e2及h5就不能為5(互斥)。

無論5出現在那個地方,在row 2和row 5上其它地方也不可能出現5(也被排斥掉了),所以column e和column h上以外的5都可以被消除。


Finned X Wings

這是XWings的變化型態,如下圖所示。


如果h3 != 4的話就構成上述的XWings pattern,那麼i2的4就可以被消除。如果在box3裡面h3=4的話,那麼i2就被排除不能為4。結合這二個pattern,不論那個情況發生,i2都不可能為4,所以可以把候選數4消除。


XY Wings

這是在找由XYZ三個數構成的XY / XZ / YZ的組合,分別存在三個不同的cell裡面,其中二個cell在同一row或同一column,並且其中二個cell必須在同一個box中。


如上圖所示,由245三個數構成的三個數對分別在e8 g9 h8三個cell裡,其中e8和h8在同一個row上,而g9和h8在同一個box裡面,所以構成XY Wings pattern。

現在來分析:如果h8=2的話,那麼g9=5;如果h8=4的話,那麼e8=5。無論那種情況發生,同時被這三個cell看到的5都會被排除。


Related Posts Plugin for WordPress, Blogger...