1. [設計案例] 生命遊戲 #4, 有效率的使用執行緒

    原本這篇不講執行緒,要直接跳到 OOP 多型的應用... 不過看一看 #3 自己寫的程式,實在有點看不下去... 30x30 的大小,程式跑起來就看到 903 條執行緒在那邊跑... 而看一下 CPU usage, 只有 5% 不到... 這實在不是很好看的實作範例,如果這是線上遊戲的 SERVER 程式,裡面的每個人,每個怪物等等都用一條專用的執行緒在控制他的行為的話,我看這遊戲不用太多人玩,SERVER 就掛掉了吧! 因此要繼續更貼近實際的生命模擬遊戲前,我們先來解決效能的問題,所以多安插了這篇進來 :D 前一篇 (#3) 的主題是把生命的進行,從被動的在固定時間被喚醒 (callback) 的作法,改成主動的在指定時間執行 (execute)。 想也知道,現實世界的生物都是 "主動" 的,後面的作法比較符合 OOP 的 "模擬世界,加以處理" 的精神。但是,一個小程式就吃掉 900 條執行緒,是有點過頭了。不知道還有沒有人記得,我騙到獎品的這個程式... 很另類的用 yield return 來解決類似問題的作法... 藉著 compiler 很雞婆的把單一流程翻成數段可以切開執行的邏輯...,正好拿來利用一下,替我們把一連串連續的邏輯切段,以便利用多執行緒來處理。我的想法是這樣,原程式是用個迴圈,作完該作的事,就休息 (sleep) 一段時間。而新的寫法,我打算用 yield return new TimeSpan(…) 來取代 Thread.Sleep(…)。每個 Cell內部的程式結構修改不大,不過對於 GameHost 就是個挑戰了... 來看看修改前及修改後的程式碼:

            // 修改前
            // 使用 Thread.Sleep( ) 來控制時間
            public void WholeLife(object state)
            {
                int generation = (int)state;
                for (int index = 0; index < generation; index++)
                {
                    this.OnNextStateChange();
                    Thread.Sleep(_rnd.Next(950, 1050));
                }
            }
            //
            //
            //
            // 修改後
            // 使用 yield return new TimeSpan( ) 來控制時間
            public IEnumerable<TimeSpan> WholeLife(object state)
            {
                int generation = (int)state;
                for (int index = 0; index < generation; index++)
                {
                    this.OnNextStateChange();
                    yield return TimeSpan.FromMilliseconds(_rnd.Next(950, 1050));
                }
                yield break;
            }
    
    別想的太美,只改這樣,程式是不會動的... 修改過之後,麻煩的地方會在 GameHost. 因為整個 GameHost 的邏輯都反過來了。原本是 GameHost 只要放著那九百條執行緒自生自滅,它只要不斷的刷新畫面就好了。現在它則得用 foreach(…) 去詢問:
    "大爺,這次您要休息多久?"
    接到 yield return 傳回的 TimeSpan 物件 (代表它要休息多久後,繼續下一個動作) 後,經過這段時間,GameHost 就要再去叫醒 cell, 然後再詢問一次:
    "大爺,這次您要休息多久?"
    關鍵就在於 GameHost 如何能透過少量的 thread 來伺後這些大爺,而不是像 #3 的程式一樣,每個大爺都用一條專屬的 thread… 要共用執行緒,就要先想辦法把工作切碎,這是基本法則。如果你希望你的生命遊戲程式不只是作業的話,那麼效能跟即時回應的問題是必需要考慮的。在動手改寫 GameHost 程式之前,先來分析一下改寫的目標有那些:
    目標是要達到像 #2 範例一樣的效果,但是要用更有效率的方式。
    目標很清楚,再來就看看有什麼手段可以用了。第一個是過量的執行緒,應該要想辦法改用執行緒集區。因為 #2 用了高達 900 條執行緒,不過整體 CPU USAGE 不到 5%,大部份的執行緒都在閒置狀態。如果能想辦法把這些運算丟到執行緒集區,由集區動態管理會有效率的多。 第二,就是把原本的 Thread.Sleep(ts) 改成 yield return ts 後,原本每個 thread 自己睡覺的機制,就要改成 cell 各自回報 game host 它想要睡多久,然後由 game host 統一在時間到時叫醒它。由於一次有多個 cell 同時在運作,因此我們需要一個簡單的排程器,作法像這樣:
    1. 建立一個時間表,依照時間順序,把每個 cell 預計要被叫醒的時間標上去。
    2. 時間到了之後,就去呼叫該 cell 的 OnNextStateChangeEx(),同時取得該 cell 下次要喚醒的時間,再標到時間表上
    3. GameHost就不斷的替每個 cell 重複 (1) (2) 的動作..
    4. 同時另外用一條獨立的執行緒,作畫面更新的動作。
    嗯,要處理的方式越來越清楚了。剩下的是 "時間表" 要用什麼型式來表現? 我的選擇是,我希望它是個 ToDo List, 會幫我排好時間,我只要把工作標上時間,丟進 ToDo List, 然後 ToDo List 只要能忠實的回報給我還有沒有排定的工作? 如果有,下一個要處理的工作是那一個? 什麼時後處理? 它的用法只有丟工作進去,跟拿工作出來,因此我設計它的公開介面長這個樣子:
            public class CellToDoList
            {
                public void AddCell(Cell cell) {...}
                public Cell GetNextCell() {...}
                public Cell CheckNextCell() {...}
                public int Count {get;}
            }
    
    裡面的實作,我就不多說了。我是把它當成 QUEUE 在設計,唯一的差別是,放進 QUEUE 的東西會先經過排序,因此不見得是 "First In First Out" 這種典型的貯列,而是會以 Cell 上標示的時間為準,依序 Out …。實作起來很簡單,用現成的 SortedList 當內部的儲存方式,加上基本的 lock 機制來確保它是 thread safe 的就夠了。 好,這些雞絲都準備好之後,就可以來打造我們的新版 GameHost 了。來看看 Code:
            static CellToDoList _cq;
            static void _YieldReturnGameHost(string[] args)
            {
                int worldSizeX = 30;
                int worldSizeY = 30;
    
                World realworld = new World(worldSizeX, worldSizeY);
    
                _cq = new CellToDoList();
                // init threads for each cell
                for (int positionX = 0; positionX < worldSizeX; positionX++)
                {
                    for (int positionY = 0; positionY < worldSizeY; positionY++)
                    {
                        Cell cell = realworld.GetCell(positionX, positionY);
                        cell.OnNextStateChangeEx();
                        _cq.AddCell(cell);
                    }
                }
    
                // 啟動定期更新畫面的執行緒
                Thread t = new Thread(RefreshScreen);
                t.Start(realworld);
    
                while (_cq.Count > 0)
                {
                    Cell item = _cq.GetNextCell();
                    if (item.NextWakeUpTime > DateTime.Now)
                    {
                        // 時間還沒到,發呆一下等到時間到為止
                        Thread.Sleep(item.NextWakeUpTime - DateTime.Now);
                    }
                    
                    ThreadPool.QueueUserWorkItem(RunCellNextStateChange, item);
                }
            }
    
            private static void RunCellNextStateChange(object state)
            {
                Cell item = state as Cell;
                TimeSpan? ts = item.OnNextStateChangeEx();
                if (ts != null) _cq.AddCell(item);
            }
    
    
            private static void RefreshScreen(object state)
            {
                while (true)
                {
                    Thread.Sleep(500);
                    (state as World).ShowMaps("");
                }
            }
      GameHost 的工作很明確,一開始 (line 18 ~ 20) 就把更新畫面的動作完全交給另一個執行緒,之後就專心處理 ToDoList 內的工作了。 接著後面的 while loop (line 21 ~ 30) 則是很單純的從 ToDoList 裡取出下一個要要動作的 Cell, 如果時間還沒到就 Sleep 等一下它。執行完後會再詢問下一次是什麼時後,同時再把他加到 ToDoList 內等待下一次輪到他時繼續。 這次的程式我沒有設定停止的條件,因此你會看到程式會不斷的執行下去。程式執行起來,結果跟 #3 沒什麼不同,畫面上的每個細胞會照著題目的規則生長或死亡,不同的是 #3 的 Game Host 需要用到 903 條執行緒,而這版的 Game Host 只要 9 條執行緒... image   其實,以這樣的範例題,我大可以不用顧慮到效能的問題,不過就是示範程式怎麼寫嘛。不過,我的目標如果只是訂在怎麼寫這練習題,大可以 GOOGLE 一下就有一堆作業解答了 :D。我的目標是要展示一下,該如何開發這樣的 GameHost ? 這樣的程式,是大部份的遊戲的基礎,尤其是像線上遊戲或是 facebook 這類互動遊戲的基礎。有了像樣的 Game Host 之後,接下來就把目標放在如何建立多樣的生物,一起放在這世界裡面生活了。接下來就會大量運用到 OOP 的特點 (對,就是上一篇預告的...) 繼承及多型。 有沒有人覺的,這種程式越寫越像 Matrix (就是駭客任務裡的 "母體") 了? 裡面活著的東西其實都在我的掌控之下... =_= 哈哈... 未完待續,請期待續集 :D。 -- 範例程式:

    2009/09/19 系列文章: 生命遊戲 .NET C# 作品集 多執行緒 技術隨筆 有的沒的 物件導向 系列文章: 生命遊戲

  2. [設計案例] Login With SSL ?

    Game Of Life 那一系列的,先暫停一期 :D,先穿插一篇不相干的內容...。這篇要講的是網站的登入部份要改用 SSL 的作法。這是很常見的問題,不過對怎麼作搞不清楚的人,仍然大有人在... 所以興起了寫這篇的念頭。

    先從 "為什麼" 來說好了。實際碰到的客戶,常常會把 "SSL" 跟 "加密" 劃上等號... 以為網站加上 SSL 就固若金湯了。這樣講是沒錯啦,不過 SSL ( Secure Socket Layer。Wiki 有說明) 再安全,也只是個 "加密" 的傳輸方式,只有對外人 (竊聽者) 是加密的... 正所謂內賊難防... SSL 可以防外賊,但是防不了內賊。因此 SSL 是不等於 DRM 這類技術的...

    扯遠了,會這樣講只是因為,很多客戶需要的其實是 DRM,不過客戶的 IT 卻天真的以為,網站加上 SSL 就萬無一失了... 於是老有客戶在問:

    客: "你們的系統可以整個放到 HTTPS 裡嗎?"

    我: "可以啊,不過效能會很糟,有什麼特別的需求,要這樣作嗎?"

    客: "老闆說網站的文件怕流出去,所以要用 HTTPS"

    我: "...."

    很想把 DRM / DPM 的介紹貼給客戶看... 不過只能很婉轉的引導客戶的需求...

    我: "HTTPS 只是防竊聽,不防把資料存下來偷帶出去的... 要防外賊,只要保互好登入過程傳輸帳號秘碼"

     

    大部份人對 SSL 的第一個誤解,就是 SSL 只是個加密的傳輸方式,不是加密的儲存方式。就好像你用黑貓寄東西,他是用貨車載... 像 Mission Impossible 裡的阿湯哥那種身手,一下就可以把你的包裹摸出來... 如果你的包裹給保全公司送,他們用的安全規格就完全不同了... 至少是運鈔車的那種規格 (不過應該也擋不住阿湯哥就是...)。

    不過,貨物送到對方手上之後,保護就不見了... 這點就是大家常常沒搞清楚的地方。

    弄清楚 SSL 只保護傳輸過程後,該怎麼應用,該應用在那裡,就很清楚了。最典型的例子,就是用在網站登入 (輸入帳號密碼,輸入信用卡號碼等等) 的地方。登入成功後就沒必要繼續留在 SSL (HTTPS) 保護的範圍了,就可以切回一般網站 (HTTP)。

    剩下的就跟你怎麼設計,怎麼規劃有關了。概念上來說,一般網站就像這張圖一樣:

    image

    所有資訊都在橘色 (不安全) 的部份傳輸。為了確保重要資訊不被竊聽,我們至少要改成這樣:

    image

    如果把 HTTP / HTTPS 當成兩個網站,則帳號密碼一定要在綠色(安全)部份傳輸。而兩台SERVER之間可以用HTTPS,或是其它管道傳輸,不一定要加密,不過至少可以把外面的駭客檔在門外。

    接下來的作法就各憑本事了,沒有標準的解法。我的客戶因為有可能有各種不同的認證規則,這規則可能跟網站的邏輯有關,所以不大適合把認證的部份擺在 HTTPS 這端,因此我的設計是:

    1. 把帳號密碼,透過HTTPS安全送到A網站,儲存起來。
    2. A網站發出一個 TOKEN (可以搭配一些HASH及EXPIRE的處理),再把這 TOKEN 轉給B網站。
    3. B網站再根據收到的 TOKEN,先作好基本的HASH及EXPIRE的檢查後無誤後,最後再到後端的 STORAGE 把當初 (1) 儲存的登入資訊取出。
    4. 取得登入資訊後,就在B網站用正常的登入程序,進行驗證工作。
    5. 驗證成功後,就可以正常的設定SESSION,使用網站的各個功能。

     

    打個比方,這就是傳統的商店刷信用卡時,會用電話等方式,銀行先跟使用者確認資訊後,給店家一個授權碼。之後店家就只能在規範的條件下,用這授權碼取款。這授權碼是不怕被盜取的,因為它只是個代號,外人取得它完全無法做壞事,就好像上例的 TOKEN 一樣。

    接下來,就來看看程式該怎麼寫了。只要使用量不大的話,A/B兩網站是可以放在同一台SERVER上,這時中間的傳輸方式就很多種簡易的選擇 (比如 local file)。考量到整個系統的 scalability, HTTPS 的部份屬 CPU BOUND,量大的話有可能影響到原網站的運作,因此實際部屬時,有可能碰到 A 網站必需跟 B 網站獨立出來,而且 B 網站也有可能因為效能問題,而再分散成多個 Web Farm 的運作方式...,這時 AB 網站間的傳輸方式就得能跨 SERVER 運作,就得挑選 DB / WCF 等等方式進行。 (當然 ASP.NET Session State Server 也可以啦,不過暫不考慮,不然就沒東西好寫了...)

     

    整理一下最後要實作的需求,跟架構設計。都到設計階段了,Use Case 就跳過去,直接到 Sequence Diagram…

     

     

     

     

     

     

    用到的技術反而沒什麼特別的。我舉幾個常見的難題,或是常被忽略掉的漏洞:

    1. HTTP / HTTPS 可能是不同的網站,SESSION 不會通... 怎麼把 LOGIN 成功的資訊, *安全* 的帶到 HTTP 這邊的 SESSION ?

    2009/09/18 設計案例: Login With SSL

  3. [設計案例] 生命遊戲#3, 時序的控制

    原本的範例,其實有些盲點,不知各位有沒看到? 一樣的起始狀態,一樣的遊戲規則,你不一定會得到一樣的結果。為什麼? 因為這會跟你程式 SCAN 的順序有關。怎麼說? 因為到目前為只,整個遊戲就好像下棋一樣,是 "回合制",我下完了換你... 一路一直輪下去。 這時先下後下就會影響結果了。現實世界的生命不是這樣的啊... 不知有沒有人玩過早期的太空戰士 (Final Fantasy) 系列遊戲? 當年 FF 有個很重要的突破,就是把 RPG 從傳統的 "回合制" 改成即時戰鬥... 每個人都有個倒數的碼錶,數到 0 你就可以發動下一次的攻擊... 這樣才接近現實世界啊。套用到我們的生命遊戲,這次我們想作的改變,就是把程式改成這種模式。 因此來調整一下規則,每個細胞每隔 1000ms 後會進到下一個狀態。不過生命總是沒有完全一樣的,因此每個細胞進到下一個狀態的時間差,都會有 10% 的誤差 (也就是 950ms ~ 1050ms 之間的時間都有可能)。其它規責則維持不變,來看看程式該怎麼改寫。 這種 "即時制",是比較合乎現實的情況的,如果未來你想發展到像 facebook 上的那些小遊戲,或是其它線上遊戲一樣的話, "回合制" 是決對行不通的... 這時,我們可以想像,每個細胞都有自己的執行緒,每換過一次狀態後就 Sleep() 一段時間,醒來再換到下一次狀態... 一直到指定的世代 (generation) 到達為止。 來看一下改版過的程式。我們先不動原本的 Cell, 只追加一個 method: WholeLife( ), 呼叫後就會一直更新這個細胞的狀態,直到它結束為止 (不是死掉喔,是 generation 到達)。而整個世界的所有細胞,都是獨立的個體,都有個專屬的執行緒在運作...。這時 Game Host 就得換個方式來讓這些細胞過日子 (執行),同時 Game Host 好像有個人造衛星一樣,不斷的在上空拍照來更新畫面,而完全不影響這些細胞的生命進行。 來看一下改寫過的 Cell 追加的 method:

            public void WholeLife(object state)
            {
                int generation = (int)state;
                for (int index = 0; index &lt; generation; index++)
                {
                    this.OnNextStateChange();
                    Thread.Sleep(_rnd.Next(950, 1050));
                }
            }
      改變不大,只是多個簡單的迴圈,跟 sleep 來控制時間而已。再來看看 Game Host 要怎麼改:
            static void Main(string[] args)
            {
                int worldSizeX = 30;
                int worldSizeY = 30;
                int maxGenerationCount = 100;
    
                World realworld = new World(worldSizeX, worldSizeY);
    
                // init threads for each cell
                List&lt;Thread&gt; threads = new List&lt;Thread&gt;();
                for (int positionX = 0; positionX &lt; worldSizeX; positionX++)
                {
                    for (int positionY = 0; positionY &lt; worldSizeY; positionY++)
                    {
                        Cell cell = realworld.GetCell(positionX, positionY);
                        Thread t = new Thread(cell.WholeLife);
                        threads.Add(t);
                        t.Start(maxGenerationCount);
                    }
                }
    
                // reflesh maps
                do
                {
                    realworld.ShowMaps("");
                    Thread.Sleep(100);
                } while (IsAllThreadStopped(threads) == false);
    
                // wait all thread exit.
                foreach (Thread t in threads) t.Join();
            }
    
            private static bool IsAllThreadStopped(List&lt;Thread&gt; threads)
            {
                foreach (Thread t in threads)
                {
                    if (t.ThreadState != ThreadState.Stopped) return false;
                }
                return true;
            }
        其實這卅幾行 code, 大都花在控制執行緒上面,有興趣的讀者可以翻翻我之前寫的那系列文章,我就不多作說明了。調整之後,這個世界變的更不可測了,一樣的起始環境,連上帝 (在這模擬世界裡,我就是上帝 XD) 都無法預測下一秒會發生什麼事... image   感覺就好像看電視一樣。畫面不斷的在閃動,而畫面裡的細胞會不規責的跳動,不像上一版程式一樣,每刷一次就變一次那樣的枯燥無聊。如果畫面呈現的地方再多用點心思,就可以弄的像卡通一樣,每個細胞都各自用自己的步調在活著... 到這裡,如何? 應該沒有人把作業寫到這個樣子了吧 XD (就說別抄我的程式去交作業了)。不適當的利用執行緒,也做的到類似的結果。不過,你花費的代價會很大,因為你的程式得自己來做 context switch (這些是 OS + thread scheduler 會幫你解決掉的,只要你曉得要用 thread)。 接下來下一篇,我們再繼續調整這世界的遊戲規則,加入更多元素進去,看看程式會變怎樣? 多執行緒解決時間的問題了,再來我們要用繼承及多型,讓不同的生命可以在同一個世界下共同生活...  ((待續))  

    2009/09/15 系列文章: 生命遊戲 .NET C# 作業系統 多執行緒 技術隨筆 物件導向 系列文章: 生命遊戲

  4. [設計案例] 生命遊戲#2, OOP版的範例程式

    還好,第一版的程式沒有難產。這版的目的很簡單,就是把題目實作出來,同時我會盡量套用物件導向的理念去設計程式的結構,而不是只把結果算出來而已。其實我一直覺的,這類生命模擬的程式,是非常適合用OOPL來實作的範例,大概OOPL所有強調的特性 (封裝、繼承、多型、動態聯結... 等等) 都用的到,算是完美的應用範例題吧!

    不過很奇怪的,我特地 GOOGLE 了一下,不知 OOPL 高手都不屑寫這種範例還是怎樣,找到的範例程式,不管用什麼語言 (C/C++/Java/C#都有) 寫的,清一色都很沒有物件導向的 fu ... 好吧,只好自己來寫一個。

    第一步,一定是先看看你的程式,分析出需要那些類別/物件,及它們之間的關係。比較正規的作法就是 UML 的 UseCase 了。不過這範例其實不大,我就直接跳到 Class Diagram 了 (因為VS2008剛好有現成的...)... 主要的類別有兩個: World (世界) 及 Cell (細胞)。

    World 就是給 Cell 生活的空間,我們只訂義一個有限大小的二維空間,就一個 M x N 的棋盤這樣。而 Cell 則是一個細胞,描述單一一個細胞本身,在各種不同的條件下會有什麼反應。先貼一下 class diagram:

     

    image  
    圖1. class diagram (World & Cell)

    老實說,這張圖還蠻乏善可陳的,World對外公開的介面,大概包含了幾個主要功能,就是取得指定座標的 Cell (GetCell), 及把目前的整個 World 狀態印出來 (ShowMaps) 的 method 而已。而 Cell 的公開介面,不外乎是它目前是活著還是死的,還有它的建構式,及呼叫後會把狀態轉移到下一次狀態的 method。

    其它都是 World / Cell 互相溝通用,或是 Init 用的 Method / Prop, 就不多作介紹。先來看看主程式,扮演上帝的你,如何讓這堆單細胞生物,在你的世界裡活起來:

    Game Of Life 主程式
            static void Main(string[] args)
            {
                int worldSizeX = 30;
                int worldSizeY = 30;
                int maxGenerationCount = 100;
    
                World realworld = new World(worldSizeX, worldSizeY);
                for (int generation = 1; generation <= maxGenerationCount; generation++)
                {
                    realworld.ShowMaps(string.Format("Generation: {0}", generation));
                    Thread.Sleep(1000);
    
                    for (int positionX = 0; positionX < worldSizeX; positionX++)
                    {
                        for (int positionY = 0; positionY < worldSizeY; positionY++)
                        {
                            // do day pass
                            Cell cell = realworld.GetCell(positionX, positionY) as Cell;
                            cell.OnNextStateChange();
                        }
                    }
                }
            }

     

    主程式我還沒把不相干的動作刪掉,也才廿一行... line 1 ~ 5 只是初始值,line 6 建立整個世界,之後就每跑完一個世代 (generation) 就休息一秒鍾,繼續下一次進化。這樣隨著時間的過去,畫面上會一直更新整個世界的狀態... 直到只定的次數到了為止。

     

    class World 的部份就沒什麼特別的,就只是把一個二維陣列包裝一下而已。直接貼 Code 就混過去吧 XD,一樣沒有刪掉程式碼,原 CODE 照貼:

    class World 的程式碼
        public class World
        {
            private int SizeX = 0;
            private int SizeY = 0;
            private Cell[,] _map;
            public World(int maxPosX, int maxPosY)
            {
                this._map = new Cell[maxPosX, maxPosY];
                this.SizeX = maxPosX;
                this.SizeY = maxPosY;
    
                for (int posX = 0; posX < maxPosX; posX++)
                {
                    for (int posY = 0; posY < maxPosY; posY++)
                    {
                        this._map[posX, posY] = new Cell(this, posX, posY);
                    }
                }
            }
    
            internal void PutOn(Cell item, int posX, int posY)
            {
                if (this._map[posX, posY] == null)
                {
                    this._map[posX, posY] = item;
                    item.PosX = posX;
                    item.PosY = posY;
                }
                else
                {
                    throw new ArgumentException();
                }
            }
    
            public Cell GetCell(int posX, int posY)
            {
                if (posX >= this.SizeX) return null;
                if (posY >= this.SizeY) return null;
                if (posX < 0) return null;
                if (posY < 0) return null;
    
                return this._map[posX, posY];
            }
    
            public void ShowMaps(string title)
            {
                Console.Title = title;
                Console.SetWindowSize(this.SizeX * 2, this.SizeY);
                Console.SetCursorPosition(0, 0);
                Console.Clear();
    
                for (int y = 0; y < this.SizeY; y++)
                {
                    for (int x = 0; x < this.SizeX; x++)
                    {
                        Cell item = this.GetCell(x, y);
                        Console.SetCursorPosition(x * 2, y);
                        Console.Write(item.IsAlive? "●":"○");
                    }
                }
            }
        }

     

    接下來是封裝每個細胞本身跟環境互動的影響,把上一篇講的規則對應成程式碼的樣子。先來看看 CODE:

    class Cell 的程式碼
        public class Cell //: Life
        {
            protected World CurrentWorld { get; private set; }
    
            internal int PosX = 0;
            internal int PosY = 0;
    
            private const double InitAliveProbability = 0.2D;
    
    
            private static Random _rnd = new Random();
            public Cell(World world, int posX, int posY) //: base(world, posX, posY)
            {
                this.CurrentWorld = world;
    
                // setup world
                this.PosX = posY;
                this.PosY = posY;
                this.CurrentWorld.PutOn(this, posX, posY);
    
                this.IsAlive = (_rnd.NextDouble() < InitAliveProbability);
            }
    
            public bool IsAlive { get; private set; }
    
            protected IEnumerable<Cell> FindNeighbors()
            {
                foreach (Cell item in new Cell[] {
                    this.CurrentWorld.GetCell(this.PosX -1, this.PosY-1),
                    this.CurrentWorld.GetCell(this.PosX, this.PosY-1),
                    this.CurrentWorld.GetCell(this.PosX+1, this.PosY-1),
                    this.CurrentWorld.GetCell(this.PosX-1, this.PosY),
                    this.CurrentWorld.GetCell(this.PosX+1, this.PosY),
                    this.CurrentWorld.GetCell(this.PosX-1, this.PosY+1),
                    this.CurrentWorld.GetCell(this.PosX, this.PosY+1),
                    this.CurrentWorld.GetCell(this.PosX+1, this.PosY+1)})
                {
                    if (item != null) yield return item;
                }
                yield break;
            }
    
            public void OnNextStateChange()
            {
                int livesCount = 0;
                foreach (Cell item in this.FindNeighbors())
                {
                    if (item.IsAlive == true) livesCount++;
                }
    
                if (this.IsAlive == true && livesCount <1)
                {
                    //孤單死亡:如果細胞的鄰居小於一個,則該細胞在下一次狀態將死亡。
                    this.IsAlive = false;
                }
                else if (this.IsAlive == true && livesCount >= 4)
                {
                    //擁擠死亡:如果細胞的鄰居在四個以上,則該細胞在下一次狀態將死亡。
                    this.IsAlive = false;
                }
                else if (this.IsAlive == true && (livesCount == 2 || livesCount == 3))
                {
                    //穩定:如果細胞的鄰居為二個或三個,則下一次狀態為穩定存活。
                    //this.IsAlive = true;
                }
                else if (this.IsAlive == false && livesCount == 3)
                {
                    //復活:如果某位置原無細胞存活,而該位置的鄰居為三個,則該位置將復活一細胞。
                    this.IsAlive = true;
                }
                else
                {
                    // ToDo: 未定義的狀態? assert
                }
            }
        }

    這裡開始應用到 OOPL 第一個特性: 封裝。從程式碼可以看到,主要的邏輯都被包在裡面了,就 Game Of Life 裡提到的四條規則。

    程式這樣寫起來,比那些作業的標準答案看起來舒服多了吧? 雖然行數多了一些,不過看起來比較有 OO 的樣子了。當然只是看起來爽是沒用的,這樣的架構,到目前為只除了邏輯清楚一點之外,還看不到其它很明顯的好處。不過當這個規責稍微複雜一點,OOPL的優點就會被突顯出來了。

    下回,把題目做點變化,再來看看程式該如何調整…   ((待續))

    --
    附件: 範例程式碼

    2009/09/14 系列文章: 生命遊戲 .NET C# 作品集 技術隨筆 物件導向 系列文章: 生命遊戲

  5. [設計案例] 生命遊戲#1, 前言

    [前言]

    好久沒寫點自己覺的有內容的東西了... 最近 code 寫的少,實在沒有什麼了不起的新技術可以分享,而 thread 那種 "古典" 計算機科學的東西也寫的差不多了.. 就懶了起來。

    雖然沒新技術好寫,不過老狗玩的把戲還是能榨出點渣的... 很多人都熟新技術,可以寫出很炫的程式,不過也常看到程式的結構真的是亂搞一通的... 所以我打算寫些 [設計案例] 的文章,舉一些我實作過的案例,說明什麼樣的問題可以用什麼方式或技術來解決。其實我想寫的就是像 design patterns 那類的東西,只不過我程度還差的遠,只能稱作 "案例" ... Orz

    ----------------------------------------------------------------------------------

    最近 facebook 上有一些小遊戲,不知道在紅什麼... 突然間大家都在玩,就都是些模擬遊戲,像是開心農場、My FishBowl … 之類的,你要在裡面種東西或養魚,條件充足就會長大,收成等等... 然後透過 Facebook API 可以跟別人互動的遊戲。看到這類的 GAME,不禁想起過去在唸書時,幾個經典的作業題目,其中一個 [生命遊戲] (Game of Life) 就是這種 GAME 的始祖...

    在 Wiki 找的到這段介紹:

    http://zh.wikipedia.org/zh-hk/%E7%94%9F%E5%91%BD%E6%B8%B8%E6%88%8F

    生命遊戲(Game of Life),又稱生命棋,是英國數學家約翰·何頓·康威(John Horton Conway)在1970年發明的細胞自動機(cellular automaton,也翻譯成「格狀自動機」)。

    它最初於1970年10月在《科學美國人》(Scientific American)雜誌中馬丁·葛登能(Martin Gardner)的「數學遊戲」專欄出現。

    1970… 我還沒出生... Orz, 不過, 這麼一個古老經典的問題,找的到一大堆範例程式,或是作業解答。清一色是用 C 這類配的上它的年紀的程式語言寫的,就算有 JAVA 版,大概也是換湯不換藥... 這四十年程式語言及軟體技術的進步,寫這種程式總該有點改變吧?

    這篇我想寫的,就是這樣的問題,配合現在的 .NET / C#,能怎麼寫它? 這年代的軟體開發技術,對這種古典的程式能發揮什麼效益?

    (警告: 剛好要交作業的人,可千萬別用我的方法交出去啊... 你的助教看不懂可能會給你零分...)

    先找個範例來看看... 為了不讓過多的畫面處理程式碼,干擾到主程式的架構,我特地找了兩個 console based 的範例:

    Java 版:
    http://tw.myblog.yahoo.com/dust512/article?mid=25&prev=28&next=-1

    多語言版 (C, Java, Python, Scala):
    http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/LifeGame.htm

    這... 這就是典型的 "Java 版 C 程式碼" 的範例... 用 Java 來寫只寫這樣,有點用牛刀的感覺... 新的開發環境強調這幾項:

    1. 物件導向 (封裝,多型,動態連結... etc)
    2. 多執行緒
    3. 其它語言特色 (這次會講到的是 yield return)

    這些技術怎麼套進這程式? 先來看看這遊戲有幾個障礙要克服吧。遊戲的規則簡單明瞭,借轉貼上面第二個範例的說明:

    生命遊戲(game of life)為1970年由英國數學家J. H. Conway所提出,某一細胞的鄰居包括上、下、左、右、左上、左下、右上與右下相鄰之細胞,遊戲規則如下:

    1. 孤單死亡:如果細胞的鄰居小於一個,則該細胞在下一次狀態將死亡。
    2. 擁擠死亡:如果細胞的鄰居在四個以上,則該細胞在下一次狀態將死亡。
    3. 穩定:如果細胞的鄰居為二個或三個,則下一次狀態為穩定存活。
    4. 復活:如果某位置原無細胞存活,而該位置的鄰居為三個,則該位置將復活一細胞。

    以前我最討厭寫這種程式了,這種程式寫起來就跟 Regexp 一樣,是 "write only” 的 code… 怎麼說? 程式寫好後,可能自己都看不懂了,因為邏輯被切的亂七八糟... GAME 裡可能同時有好幾個細胞,每個都有獨立的規則,不過程式卻是一個主迴圈,每次執行每個細胞的一小段邏輯... 程式的流程就這樣被切碎了... 我打算用C#的 yield return, 解決這邏輯破碎的問題。

    第二個障礙,就是這類程式,某種程度都是隨著時間的進行而跑的,比如上面的條件都是 "下一次狀態" … 把每次狀態改變定義一個時間 (比如一秒),這就是個 realtime 的模擬程式了。如果有的細胞是一秒改變一次狀態,有的是兩秒,有的是五秒... 那就傷腦筋了... 你的程式會被切的更破碎... 這些每種細胞特殊的部份,我打算用 OOP 的多型來解決。

    最後,這種很明顯是 "並行" 的問題,照道理來說,用多執行緒是最適合的了。不過隨便也有成千上萬個 "細胞" 在成長,每個都來一個 thread 養它,再高級的 server 都撐不住吧? 這邊會來探討一下,怎麼用執行緒相關的技巧,來解決這問題。

     

    --------------------------------------------------------------------------------------

    寫到這裡,突然覺的這題目好大... Orz, 搞不好這幾篇要撐幾個月才寫的完... 至少有個題材好寫,等到我生出第一個 sample code, 就會有下一篇了... 如果有同好也想試試看的,也歡迎分享看看你的 code… 只不過我沒像 darkthread 有本錢提供獎品... 哈哈 :D

    2009/09/12 系列文章: 生命遊戲 .NET C# 多執行緒 技術隨筆 物件導向 系列文章: 生命遊戲