[設計案例] 生命遊戲#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));
            }
        }

        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;
        }

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

[設計案例] 生命遊戲#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:

  
圖1. class diagram (World & Cell)

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

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

        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 照貼:

    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:

    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# 作品集 技術隨筆 物件導向 系列文章: 生命遊戲

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

HVRemote (Hyper-V Remote Management Configuration Utility)

被這東西搞了半天，過了幾個月後發現有善心人事寫了個工具，今天看到了特地來記一篇... 免的以後又忘了 @@

話說 Microsoft 從幾年前開始被一堆 security 的問題苦惱後，決定所有產品都把安全視為第一優先... 這是件好事啦，不過為了 security 問題，真的會把 MIS 及 DEV 的相關工作難度加上好幾倍... 今天這個就是一例: 在沒有 AD 環境下，如何遠端的管理 Hyper-V server ?

之前把家裡的 SERVER 升級到 Windows Server 2008 + Hyper-V, PC 升級為 Vista 後，當然很高興的抓了 Hyper-V 的遠端管理工具回來裝。想說大概跟以往的 MMC 一樣，輸入 SERVER 的資訊，帳號密碼打一打，就可以用了...

事情當然沒這麼簡單，不然就沒這篇了... 直接使用的結果當然只是丟個沒權限之類的訊息。GOOGLE 找了一下解決方式... 找到這文章 (有五篇，別以為很辛苦的把它照作就結束了，還有 part 2 ~ part 5 @@):

http://blogs.technet.com/jhoward/archive/2008/03/28/part-1-hyper-v-remote-management-you-do-not-have-the-requested-permission-to-complete-this-task-contact-the-administrator-of-the-authorization-policy-for-the-computer-computername.aspx

細節就不講了，要調整的步驟還真它X的多... 先在 CLIENT / SERVER 都建好帳號，防火牆要允許 WMI，DCOM... 再設定 WMI 相關的權限給指定的帳號，還有後續一堆安全相關的設定要開... 最後搞了半天，真的成功了，不過... 最近趕流行，把 Vista 換成 Windows 7... 真糟糕，這堆步驟又要來一次 @@

這次又找了一下解決方式，還是一樣有這堆設定要改，不過跟幾個月前找到的同一個 BLOG，版主真是個好人，他把他整理出來的步驟寫成了個工具: HVRemote.wsf … 沒錯，就只是個 script 而已，不過它可不簡單。先看一下它的網站:

http://blogs.technet.com/jhoward/archive/2008/11/14/configure-hyper-v-remote-management-in-seconds.aspx

http://code.msdn.microsoft.com/HVRemote

http://technet.microsoft.com/en-us/library/ee256062(WS.10).aspx

作者把上面那一大串的步驟都寫成 script 了，你只要把這 script 抓下來，放到 client / server 都執行一次，就搞定了 :D  真專業，還有一份很完整的操作說明 PDF 檔... 一定要推一下這個工具 (Y)

附帶提一下，Hyper-V 遠端管理工具是透過 MMC 來執行的，但是我喜歡像 Remote Desktop 那種簡單的作法，只要開個連線工具，驗證過之後就可以遠端桌面這樣... Hyper-V 也有提供這樣的工具。只要裝好管理工具，你的電腦就會有這檔案:

C:\Program Files\Hyper-V\vmconnect.exe

搞什麼，連登入視窗都弄的跟 Remote Desktop Client 一模一樣，有時不小心還真會弄錯 =_=

開起來後就是大家熟悉的 Hyper-V 遠端管理的畫面了。這工具只是讓你省掉從 MMC 去 connect VM 這些步驟而以，像 RDP 一樣開了就能用:

當然透過這工具，上面那堆設定步驟也要照做才會通啦，只是順帶提一下這個 tips 而已。有了 HVRemote 這工具，要設定遠端管理 Hyper-V VM 就更輕鬆了，有需要的人就參考看看吧!

2009/08/16 MSDN Tips 有的沒的

JPEG XR (就是 Microsoft HD Photo 啦) 已經是 ISO 正式標準了...

先寫在前面，這篇不是什麼技術的探討或是評論，純脆是我個人看到這消息的想法而已。很久沒貼些軟體相關的文章了，最近比較少在動手寫 Code, 自然就沒什麼新題材好寫 @@，不過這兩天倒是看到一個蠻令人興奮的新聞，就是:

JPEG XR 已經正式通過 ISO 標準了!!

http://jpeg.org/newsrel26.html
http://blogs.msdn.com/billcrow/archive/2009/07/29/jpeg-xr-is-now-an-international-standard.aspx

JPEG 應該已經無人不知，無人不曉了吧? 不過當年還是有朋友鬧過笑話... 曾有人正經八百的來問我

"什麼是 [結合照片專業群組] 啊???" 就是 JPEG 啦 (無聊的話看一下底下的題外話)

我還丈二金剛摸不著頭腦，把他在看的整篇文章拿過來看，才晃然大悟他到底在問啥 =_= ... 原來是 "JPEG: Joint Photographic Experts Group”的縮寫... 當然類似的 MPEG (Moving Picture Experts Group) 也碰過類似的笑話... 無聊 GOOGLE 一下，竟然還查的到一篇範例...

http://support.microsoft.com/default.aspx/kb/235928/zh-tw

My God… 這翻譯真是比之前碰到了 "註冊傑克" 還絕 XD...

之前其實沒特別注意這些標準，曾經有印像的就是用 wavelet 壓縮方式的 JPEG2000... 嘗試取代 JPEG，也取得 ISO 的標準化，不過一直沒達成它的目的，只在特定領域還有應用空間。兩年前 Microsoft 隨著 Vista / WPF 推出 Windows Media Photo 的格式，後來為了讓它成為標準，換了個叫沒有 MS 色彩的名字: HD Photo, 最後變成現在的 JPEG XR ..

我是在兩年前，隨著 .NET 3.0 推出 WPF，剛好自己用的 CANON 相機的 RAW FILE 又被 WPF 支援，所以開始研究相關的 API 及 support .. 在關於 HD Photo 眾多報導中，有個觀點是我相當認同的。找不到較具代表性的消息來源，我就憑記憶寫一下，大意是:

隨著技術進步，未來影像設備 (如印表機，掃描器，顯示器等等) 的色彩表現能力及色域會遠超過 JPEG 格式的範圍 (現在就是了)，因此儲存格式支援的動態範圍 (dynamic range) 越高，對於影像的長期保存越重要。

這就是處女座的龜毛個性啊... 衝著這個看法，我從 Canon PowerShot G2 時代開始，我就試著盡量用 .CRW 格式 (CANON RAW) 來保存相片，而不是用 JPEG。後來換了 Canon PowerShot G9，正好 WPF 出來，我就開始改用保存 .CR2 檔，而另外轉一份 JPEG 檔來作一般用途 (畢竟 JPEG 還是方便的多)。不過一張照片花掉 15 ~ 20mb, 保存起來壓力還真不小 =_=

現在看到 JPEG XR 的標準化，正好是我要的東西啊 :D   我需要的正是個能妥善保存這些影像資料細節的方式，同時能讓我輕鬆愉快的使用，不用耽心工具支不支援，或是其它五四三等問題困擾...。這些問題對阿宅來說，一點都不困難，有一缸子的工具辦的到，不過... 如果隨變看個照片，或是要 COPY 給家人朋友看，還要動用一堆雞絲，那也太辛苦了一點... 能有個通用的標準格式及大廠背書，那是再好也不過了 :D

所以，接下來要做什麼? 我突然慶興我一直都有留著這幾年拍下來的 RAW file (.CRW / .CR2) 檔案... 該是替我的歸檔程式翻新的時後了，下一步是開始嘗試用 .WDP 來取代現在放兩份 RAW + JPEG 的方式...

2009/08/05 .NET WPF 技術隨筆 有的沒的