編程模擬自然(九)：元胞自動機

序·精衛填海篇

　　舊書有云：發鳩之山，其上多柘木。有鳥焉，其狀如烏，文首、白喙、赤足，名曰精衛。

　　（前情提要：主角元乘坐返回艙降落到了碼海上，隨后遇到了個鳥人...）

　　“咳咳，遠道的客人，我名精衛 XIV，乃是先祖精衛鳥的第十四代后裔...”鳥人作自我介紹。

　　“...你是誰，從哪里來又要到哪里去？”鳥人頓了頓接著問道。

　　元不禁陷入了沉思，哲學問題無法快速給出答案。

　　精衛 XIV 打量了會兒元，見其仍沉默不語，更是堅定了自己的想法，又道

　　“客人，我看你頸椎清奇，必是萬中無一的編程奇才，今日與你有緣，這里有一本《碼海之巔》，就贈予你了。”

　　“唔，這講的是什么？”元好奇道。

　　“精衛變成了個鳥人，但他沒有放棄這個世界的愛，他始終微笑著，十年以后，精衛終于成為了一名偉大的軟件測試工程師。所以，我們不要放棄希望，天使永遠住在你微笑的嘴角。”

　　...

碼海，充斥著代碼的海洋

Bug，碼海中普遍存在的一種生物

第一章 復雜系統

　　Hawaii 讀者評論：

　　“我最近讀到一本好書《碼海之巔 》，文中提到了如何用元胞自動機模型更好地理解碼海中 Bug 的繁衍模式。”--從事編程 20 余年的 LuisIbara

　　“很多編程書讀起來味同嚼蠟，大多數的編程課程同樣枯燥無聊。本書給出了我目前所知各種編程概念最深入淺出的雞湯解釋。”--不愿意透露姓名的 Alice

　　“我是一名文學愛好者，最喜歡的就是作者在書中的回憶錄，在我看來這實際是一本講述軟件測試員與 Bug 之間愛恨情仇的書。”--自稱文學愛好者的 Youkili

　　...

 --節選自《碼海之巔·讀者評論》

　　復雜系統的性質

　　個體之間存在小范圍的聯系

　　個體的動作是并行的

　　系統在整體上會呈現出自發現象

　　什么是元胞自動機？

　　它能構建隨時間推移發生狀態轉移的系統

　　細胞存在于一維或多維網格中

　　每個細胞都有一個或多個狀態

　　每個細胞都有鄰居（即鄰近的細胞）

　　元胞自動機分類

　　平穩型：自任何初始狀態開始，經過一定時間運行后，元胞空間趨于一個空間平穩的構形，這里空間平穩即指每一個元胞處于固定狀態。不隨時間變化而變化。
　　周期型：經過一定時間運行后，元胞空間趨于一系列簡單的固定結構（Stable Patterns）或周期結構（Perlodical Patterns)。由于這些結構可看作是一種濾波器（Filter），故可應用到圖像處理的研究中。
　　混沌型：自任何初始狀態開始，經過一定時間運行后，元胞自動機表現出混沌的非周期行為，所生成的結構的統計特征不再變止，通常表現為分形分維特征。
　　復雜型：出現復雜的局部結構，或者說是局部的混沌，其中有些會不斷地傳播。

圖1-1 二維元胞自動機

第二章 生命游戲

　　初九日，驚蟄。

　　我常常眺望碼海，以為會等到一個人。很多年以后，我去了碼海，我才知道是我錯了。

　　很多年以前，我有個綽號叫做瘋子，任何人都可以變得瘋狂，只要你嘗試過什么叫做 Debug 時的無助。我不會介意其他人怎么看我，我只不過不想看到別人比我更無助。

　　又是一個下雨天，我帶了把雨傘。可是每次我一個人撐傘走在雨中的時候，我都會難過。

　　以前我是不打傘的，因為我感覺自己是一只無腳鳥，只能不停的飛，飛的累了就在風里休息。這樣也挺好的，不知道疲倦。

　　直到有一天，一個大眼睛的女人和我一起在樹下躲雨。

　　我們最接近的時候，我跟她之間的距離只有 1 像素，2 幀之后，我愛上了這個女人。

　　我相信除了寂寞，緣分是男人和女人之間相愛的另一種原由。寂寞是每時每刻，緣分是不知不覺。

 --節選自《碼海之巔》

　　四邊網格-死亡

　　競爭：細胞周圍存在 4 個及以上的鄰居時，細胞死亡

　　孤獨：細胞周圍“活著”的鄰居等于或小于 1 時，細胞死亡

　　四邊網格-新生

　　處于死亡狀態的細胞，當它周圍剛好有三個活著的鄰居，它也會變為活著的狀態

　　四邊網格-靜止

　　保持活著：如果細胞是“活著”的，而且周圍有 2 個或 3 個鄰居時，它將繼續活著

　　保持死亡：如果細胞是“死亡”的，而且鄰居數目不等于3時，它將保持死亡狀態

圖2-1 保持靜止的組合

圖2-2 交替出現的組合

第三章 擴展屬性

　　驚蟄，忌驕暴動怒。每年的這個時候，我都會駕著船，去東方的沙洲，見一個人。我知道，她見不到我，會悄悄咬自己的頭發。

　　“我們在哪里見過嗎？”她的船艙里，總有幾個奇奇怪怪的伙計。

　　“你忘了嗎？忘了最好--”那個圓臉蛋的伙計擦了擦桌子，臉色變了變。

　　“我們發過誓要殺了你的，不過很不巧，我們現在也不算是敵人。”一個瘦高個，山羊胡子的人答道。我覺得他們都很奇怪，明明是店里的伙計，總說自己是敵人。

　　她這里有一種泡了桃花的酒，她說酒叫“醉生夢死”，喝了之后，可以叫你忘掉以前做過的任何事情。

　　我很奇怪，為什么會有這樣的酒。她說，人最大的煩惱，就是記性太好，如果什么都可以忘了，以后的每一天，都會是新的開始。那你說多開心。

　　她陪著我一起喝，喝了之后還會唱曲調很怪的歌曲。

　　現在，我只記得兩句，丑 Bug 怪~呀咦呀啊啊~啊啊啊，能否別把燈打開。

 --節選自《碼海之巔》

　　擴展的屬性

　　位置：網格中的位置

　　顏色：實際顯示的 ARGB 顏色

　　大小：單個網格占據的像素大小

　　形狀：方塊、圓形或其他形狀

　　生命：記錄迭代次數

　　其他：其他自定義的屬性

　　擴展屬性的特點

　　多狀態：前述中細胞只有“生”與“死”兩種狀態，現在它的狀態變得極其豐富，比如 RGB 顏色可表示多達 1678 萬種色彩。

　　歷史性：在面向對象的生命游戲程序中，如果你用一個數組存放細胞的狀態歷史，會有怎樣的特性？事實上這種特性常用于開發“復雜自適應系統”，它能從歷史學習中不斷適配和改變規則。

圖3-1 保留歷史的 CA 圖案

第四章 六邊網格

　　立春過后，一場清剿碼海 Bug 的戰役打響了，我擔任測試資源調度員。

　　“精衛小賊，我們來取你的命。”我看到山羊胡子和圓臉胖子發出白光，覺得很可笑。自動化測試大軍勢如破竹，已經攻到了近海，還有這種不怕死的 Bug 嗎？

　　他們說他們叫沙洲八怪。但是好奇怪，我殺了一只又一只，為何還是少一只。

　　一個小時以后，碼海上有一股波浪線直沖云霄。這天是驚蟄，萬物復蘇，是新的開始。現在，卻有一個 Bug 來找死。

　　我的編譯器不再提示錯誤了。甲板前方有一個扶著兵器的女人，一句話也不說，向著我走來。

　　我認識時就知道她是 Bug，她騙的了編譯器，卻騙不了我。有時候最了解你的人不是你的朋友，而是你的敵人。

　　“回去不好嗎？在你的沙洲泡酒，快活一世。我攔不住他們，只能攔下你了。”

　　“可我不圖一世，只圖一時。我是個 RuntimeException。”

　　“哎——”她拋出的空指針暗器來勢洶洶，卻沒有多少殺意。我看到她的嘴角流血，自己的心也開始莫名的痛了一下。

　　我知道所有的悲歡都已化為灰燼，任世間哪一條路，她都不能與我同行。

 --節選自《碼海之巔》

　　二維CA空間劃分

　　三角網格：較少的鄰居數目，這在某些時候很有用

　　四邊網格：適合在計算機環境下進行可視化輸出

　　六邊網格：自然真實，能較好地模擬各向同性的現象

　　六邊網格的實現

　　六邊網格依然可以用二維數組存儲

　　奇數層相對偶數層偏移一定的距離

　　奇數層、偶數層對應不同的鄰居關系

圖4-1 六邊網格鄰居關系

圖4-2 六邊網格生命游戲

第五章 CA應用

　　當我站在沙洲前，覺得非常的難過，我總覺得，應該是兩個人站在這里。

　　很多年后，總有些代碼，你想寫卻不知從何寫起，總有些人，你想見卻又無處找尋，瑣碎生活與時間倦怠的逐步侵蝕，感覺日益趨于遲鈍，心也由得滿不在乎。

　　只是記憶不由得你，或閑庭信步的觸景傷情，或夢醒時分的黯自惆悵，或只是某個漫不經心的調侃后，那昔日的情景乍然浮現心間，遙遠得恍若海市蜃樓。

　　其實“醉生夢死”只不過是她跟我開的一個玩笑，你越想知道自己是不是忘記的時候，你反而記得越清楚。我曾經聽人說過，當你不能夠再擁有，你唯一可以做的，就是令自己不要忘記。

--節選自《碼海之巔》

　　CA可用來研究很多一般現象　　

　　通信（Communication）

　　計算（Compulation）

　　構造（Construction）

　　生長（Grain Growth）

　　復制（Reproduction）

　　競爭（Competition）

　　進化（Evolution）

　　計算機科學領域的應用

　　并行計算：CA 可以被看作是并行計算機，從而用于并行計算的研究

　　圖像處理：CA 規則可以用于模擬墨水在紙上的浸散效果及圖像的水紋效果

圖5-1 CA 模擬水墨浸散（50% 保留）

圖5-2 CA 模擬水墨浸散（100% 保留）

后記

　　“暴風雨就要來了！我得走了。”精衛 XIV 向元告別。

　　元點了點頭。他從另一個世界來，又能去哪里呢？

　　...

附錄

　　在線演示：CA - GameOfLife

　　未完待續。了解更多請瀏覽目錄導航。