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。

    範例程式:

    BLOG #4.zip

    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 < 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<Thread> threads = new List<Thread>();
                for (int positionX = 0; positionX < worldSizeX; positionX++)
                {
                    for (int positionY = 0; positionY < 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<Thread> 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)。

    接下來下一篇,我們再繼續調整這世界的遊戲規則,加入更多元素進去,看看程式會變怎樣? 多執行緒解決時間的問題了,再來我們要用繼承及多型,讓不同的生命可以在同一個世界下共同生活… ((待續))

    Multi-Thread Source Code

    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的優點就會被突顯出來了。

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

    – 附件: 範例程式碼

    SourceCode.zip

    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# 多執行緒 技術隨筆 物件導向 系列文章: 生命遊戲