【文章內(nèi)容簡介】 的實(shí)現(xiàn)都有一些共同的特點(diǎn)：1 需要一個二維的空間第 9 頁 共 31 頁2 在程序運(yùn)行時，需要頻繁的刷新繪圖區(qū)域3 運(yùn)動的個體都是一些離散的個體所以，我設(shè)計(jì)了一個通用的模塊，實(shí)現(xiàn)下面的功能的時候，都是調(diào)用了這個模塊。這個模塊包含了兩個部分：（1）在二維空間上繪制離散的個體（2）對這些離散個體的存儲另外，為了證明這個模塊通用的程度，我利用這個模塊輕易實(shí)現(xiàn)了貪吃蛇、五子棋等小游戲，證明了這個模塊的功能確實(shí)超出了預(yù)期的設(shè)想。下面介紹一下這個模塊的組成。先看圖 4：圖 4 生命游戲模擬圖觀察黑色的繪圖區(qū)域，我們就可以發(fā)現(xiàn)，要實(shí)現(xiàn)各種功能，我們首先要用一個數(shù)據(jù)結(jié)構(gòu)來記錄各種離散個體的信息，也就是布局，然后把這些離散信息繪制出來。1) 布局布局相對來說比較簡單。因?yàn)槔L圖區(qū)域是個二維圖形。我們可以先創(chuàng)建一個int類型的二維數(shù)組cell，然后使二維數(shù)組的元素和對上面的每一個小區(qū)域一一對應(yīng)起來。比如，某一個元素?cái)?shù)值是 1 的話，那么就代表這個相應(yīng)的區(qū)域存在一個個體，如果數(shù)值是 0 的話，就說明這塊區(qū)域沒有個體。我們可以先對這個數(shù)組進(jìn)行處理，然后再一次性繪制出來。實(shí)踐證明，這樣的方法是可行的。由于程序是動態(tài)運(yùn)行，也就是說，當(dāng)前的數(shù)組狀態(tài)須根據(jù)相應(yīng)的規(guī)則，產(chǎn)生下一代的狀態(tài)。所以，單單只有一個數(shù)組，沒辦法實(shí)現(xiàn)這個功能。所以，我定義了另外一個數(shù)組： 。這個數(shù)組保存的就是cell狀態(tài)的一個備份。當(dāng)需要演化時，我們逐個對cell上的個體進(jìn)行判斷，鄰居在workcopy 上判斷。修改直接體現(xiàn)在cell數(shù)組上。第 10 頁 共 31 頁2) 繪制離散個體離散的個體我們可以調(diào)用圖形來，然后把它畫在黑色的畫布上。由于畫布是個二維的矩陣，所以，要規(guī)整的在畫布上布局這些個體，我們使用的圖形必須是正方形的，并且，圖形的背景要透明，看起來才比較自然。至于個體在畫布上的擦除，我們可以采用對整個畫布進(jìn)行刷新的辦法。但是這個方法不僅低效，而且程序運(yùn)行的時候，整個畫面非常閃爍，令人很不愉快。我采取了一個小技巧，由于畫布是黑色的，我們可以制作一個尺寸和個體圖片尺寸一樣大小的的黑色圖片，把它覆蓋在原來的區(qū)域，就等于把這個個體擦除了。這個方法不需要刷新整個屏幕，而且，只對小區(qū)域的圖形進(jìn)行操作，大大提高了系統(tǒng)的性能。下面是這個想法的算法實(shí)現(xiàn)（為了提高系統(tǒng)的性能，我使用了雙緩沖技術(shù)）：3) 算法描述：Begin（1）首先把 cell 里的信息復(fù)制到 workcopy 里。（2）載入你想在屏幕上顯示的圖片，建立虛擬畫布。（3）對繪畫區(qū)域上的位置逐個進(jìn)行判斷。如果這個位置下一代有而上一代沒有的話，就繪制一個圖形；如果這個位置下一代沒有而上一代有的話，就擦除上面的圖形。End請看通用模塊顯示部分算法流程圖5第 11 頁 共 31 頁圖 5 通用模塊顯示部分算法流程圖4) 總結(jié)這個模塊之所以有一定的通用性是因?yàn)樗娘@示不受任何規(guī)則的影響，也就是說它是一個獨(dú)立的函數(shù)。繪制的個體也可以多種多樣，不一定非要是一個小球，你甚至可以定義一個坦克的小圖品，沒有問題，只要您的圖片是正方形的，而且圖片的長度能滿足下面這個公式：600 % 圖片長度（像素點(diǎn)） == 0 （因?yàn)槔L圖區(qū)域的長度是 600 個像素點(diǎn)） 。這就說明了它的兩個組成部分都是獨(dú)立的。如果您要實(shí)現(xiàn)的算法滿足我上面列出的三個特征，您可以使用這個通用模塊，并添加一些輔助的規(guī)則，輕易實(shí)現(xiàn)這個算法。 生命游戲的實(shí)現(xiàn)算法描述（這里，離散個體這個稱呼我們改成細(xì)胞）：。Begin（1）初始化。把 cell 數(shù)組的每一個元素都設(shè)置成 ，如臨時變量、記錄坐標(biāo)的變量等。（2）對 cell 數(shù)組進(jìn)行隨機(jī)賦值，只能是 0 和 1.（3）備份 cell 數(shù)組的信息到 workcopy 數(shù)組里。第 12 頁 共 31 頁（4）對 cell 數(shù)組的每個元素逐個計(jì)算。取得這個細(xì)胞上、下、左、右的坐標(biāo)值。如果數(shù)組元素已遍歷完，則直接到 End.（5）利用這些坐標(biāo)值求出生存鄰居的個數(shù)（6）結(jié)合鄰居個數(shù)和約束條件，如果細(xì)胞是活的，那么當(dāng)它有2到3個鄰居時就可以繼續(xù)生存下去. 否則只能死亡或者當(dāng)原來沒有細(xì)胞生存時，當(dāng)它的鄰居是3時。把這些信息記錄到cell數(shù)組上。返回到（4）。End1) 收集鄰居個數(shù)圖 6 生命游戲中收集鄰居個數(shù)的算法流程圖2) 按規(guī)則演化第 13 頁 共 31 頁圖 7 生命游戲中細(xì)胞按規(guī)則演化的算法流程圖注意：算法流程圖中出現(xiàn)的變量名解釋：h_i 是二維矩陣的行號；h_j 是二維矩陣的列號。 top 存儲當(dāng)前細(xì)胞上一行的行號坐標(biāo)；bottom 存儲當(dāng)前細(xì)胞下一行的行號坐標(biāo)； left 存儲當(dāng)前細(xì)胞前一列的列號坐標(biāo)；right 存儲當(dāng)前細(xì)胞后一列的列號坐標(biāo)；z 是矩陣的邊界處理了 cell 數(shù)組以后，我們就可以使用通用模塊中的 Display 函數(shù)把它的狀態(tài)繪制出來。至此，完成了生命游戲的程序設(shè)計(jì)。請看程序運(yùn)行的截圖 圖8：第 14 頁 共 31 頁圖 8 生命游戲 一維通用細(xì)胞自動機(jī)（CA ）的實(shí)現(xiàn)生命游戲其實(shí)是一維細(xì)胞自動機(jī)的一個特殊的例子。它能實(shí)現(xiàn)比一維細(xì)胞自動機(jī)更生動直觀和奇幻的圖形。但是，由于一維細(xì)胞自動機(jī)規(guī)則簡單、現(xiàn)象直觀，故而人們對它進(jìn)行了深入的研究，而且，沃夫拉姆的四種分類也是建立在一維細(xì)胞自動機(jī)的基礎(chǔ)之上。它的理論基礎(chǔ)可參照本論文第一章第二節(jié)。所以，有必要實(shí)現(xiàn)一維細(xì)胞自動機(jī)模型。一維細(xì)胞自動機(jī)的算法描述：Begin（1）隨機(jī)生成第一代的細(xì)胞：先在繪制區(qū)域的最后一行，也就是矩陣數(shù)組的最后一行進(jìn)行一次隨機(jī)生成細(xì)胞操作。（2）從第二行開始，把整個區(qū)域往上挪一行（3）根據(jù)一維細(xì)胞自動機(jī)的規(guī)則和上一代的細(xì)胞狀態(tài)，計(jì)算出下一代的細(xì)胞狀態(tài)。并放置在 cell 數(shù)組的最后一行里。根據(jù) cell 數(shù)組的信息，繪制出相應(yīng)的圖形并返回到（2）步驟。End在這里，我們有必要對一維細(xì)胞自動機(jī)的規(guī)則作出解釋，請先參看第一章第三節(jié)對規(guī)則的解釋，上面是以一維細(xì)胞自動機(jī)為例的，也詳細(xì)闡述了其規(guī)則的原理。下面簡單其規(guī)則產(chǎn)生的算法：一維細(xì)胞自動機(jī)規(guī)則生成算法描述：Begin（1）取得使用者給出規(guī)則的十進(jìn)制表達(dá)形式。（2）使用相關(guān)的函數(shù)把十進(jìn)制值轉(zhuǎn)化成二進(jìn)制（具體語言不一樣，可參照本畢業(yè)設(shè)計(jì)源程序的 trun_this_on() 函數(shù)） 。（3）把這個二進(jìn)制值每一位分別拆開，放到數(shù)組里以便使用。End圖 9 一維細(xì)胞自動機(jī)演化規(guī)則號轉(zhuǎn)化為二進(jìn)制值的算法流程圖第 15 頁 共 31 頁圖 10 一維細(xì)胞自動機(jī)算法流程圖注意：算法流程圖中出現(xiàn)的變量名解釋：f、k、a 和 b 是臨時變量 ，abc是存放二進(jìn)制位的一個數(shù)組。完成程序設(shè)計(jì)工作，請看程序運(yùn)行截圖 圖11：圖11 一維細(xì)胞自動機(jī) 分子熱運(yùn)動模擬由于上面的章節(jié)沒有提到分子熱運(yùn)動，所以這里需要解釋一下。我們還是使用原來的通用模塊來對分子熱運(yùn)動這個物理現(xiàn)象進(jìn)行模擬。這里，離散個體的稱呼改成小分子。因?yàn)榉肿舆\(yùn)動性質(zhì)和上面的細(xì)胞有點(diǎn)區(qū)別，每個分子都必第 16 頁 共 31 頁須有自己的運(yùn)動方向和當(dāng)前以及下一步的坐標(biāo)，所以使用了一個結(jié)構(gòu)體來存儲這些信息。當(dāng)然，我們對這群分子的狀態(tài)的顯示離不開cell數(shù)組，cell 屬于通用模塊的第一個組成部分。我們可以這樣定義這個數(shù)據(jù)結(jié)構(gòu)：public struct qiuti{public int x。 //這個小分子當(dāng)前的坐標(biāo)值 public int y。public int fang。 //指示這個小分子當(dāng)前的的運(yùn)動方向 }我們用上面的結(jié)構(gòu)體定義一個結(jié)構(gòu)體數(shù)組，來存儲所產(chǎn)生的分子的信息（信息指這個分子下一步的坐標(biāo)和方向） 。public qiuti[] fenzi = new qiuti[15000]。分子隨機(jī)熱運(yùn)動模擬程序算法描述：（1）在cell數(shù)組上隨機(jī)生成小分子的坐標(biāo)和方向。（2）把這些信息記錄在我們定義的結(jié)構(gòu)體數(shù)組里。（3）把 cell 數(shù)組的信息復(fù)制到 workcopy 數(shù)組里去。（4）對結(jié)構(gòu)體數(shù)組的每一個數(shù)據(jù)項(xiàng)都進(jìn)行計(jì)算，給出分子下一步的方向和坐標(biāo)。（5）調(diào)用通用模塊顯示出所有分子的狀態(tài)，并返回（3）步驟。圖12 分子熱運(yùn)動模擬算法流程圖注意：算法流程圖中出現(xiàn)的變量名解釋：fenzi 是結(jié)構(gòu)體數(shù)組，fenzi_count 是存儲分子個數(shù)的變量，qq 是臨時變量。至此，分子熱運(yùn)動的程序設(shè)計(jì)完成，請看程序運(yùn)行的截圖：第 17 頁 共 31 頁圖13 分子熱運(yùn)動模擬3 細(xì)胞自動機(jī)的實(shí)驗(yàn) 一維細(xì)胞自動機(jī)分類20 世紀(jì) 80 年代 ，（CA）進(jìn)行了分類，做了全面研究（1984） 。他認(rèn)為細(xì)胞自動機(jī)是個真實(shí)的復(fù)雜系統(tǒng)，有一些系統(tǒng)非常有趣，可以展現(xiàn)出和真實(shí)世界類似的現(xiàn)象。從大氣現(xiàn)象到生物體甚至是經(jīng)濟(jì)系統(tǒng)，莫不如此。因此，有可能利用細(xì)胞自動機(jī)發(fā)現(xiàn)復(fù)雜系統(tǒng)的一般規(guī)律。更為有意義的是：復(fù)雜的系統(tǒng)可以從簡單的行為中突現(xiàn)出來。其次， 他相信，科學(xué)正處在一種新型研究方法變革的重大時期。這就是計(jì)算機(jī)實(shí)驗(yàn)。對自然界的一些對象，特別是復(fù)雜對象的研究，很難進(jìn)行直接的實(shí)驗(yàn)。比如遙遠(yuǎn)星系中旋轉(zhuǎn)的巨大的氣體云，據(jù)說，它們往往在引力的作用下收縮成高密度的集結(jié)物，并最終成為恒星的中心團(tuán)塊，其周圍繞著它旋轉(zhuǎn)的較小的團(tuán)塊最后變成伴隨該恒星的行星系統(tǒng)。這種說法，很顯然沒有人能用實(shí)際的實(shí)驗(yàn)來檢驗(yàn)一下。又假如有人說通過提高利率，比如說在很短的時間內(nèi)提升500 個基點(diǎn)，以檢驗(yàn)關(guān)于貨幣和股票的價格波動的某個新理論?？梢钥隙ǎ魏我粋€國家的金融機(jī)構(gòu)都不會同意，因?yàn)檫@種系統(tǒng)對人們的生活太重要了，任何人都不敢貿(mào)然作這類實(shí)驗(yàn)。但是，利用計(jì)算機(jī)進(jìn)行模擬實(shí)驗(yàn)，同樣也可以得出有意義的結(jié)果。而細(xì)胞自動機(jī)是利用這種新型研究方法進(jìn)行研究的最好的對象。沃夫拉姆所研究的細(xì)胞自動機(jī)是一維的，而康維和馮。諾伊曼的細(xì)胞自動機(jī)都是二維的，它們是在二維的平面上運(yùn)行的。沃夫拉姆的一維細(xì)胞自動機(jī)是在一條直線上運(yùn)行。每一個細(xì)胞只有左右兩個鄰居。一維細(xì)胞自動機(jī)的一個優(yōu)點(diǎn)是：因?yàn)槊恳淮?xì)胞的狀態(tài)都可以表示在一條直線上，因此，我們可以把不同時代的細(xì)胞狀態(tài)從上到下一代代地排列。這樣，我們就能輕易地看到它的歷第 18 頁 共 31 頁史變化情況。還有一個好處就是，規(guī)則的設(shè)定很簡單，這佐證了簡單規(guī)則能產(chǎn)生復(fù)雜現(xiàn)象的理論，同時，也能很輕易的研究不同的規(guī)則會產(chǎn)生什么樣的結(jié)果。下面介紹沃夫拉姆的一維細(xì)胞自動機(jī)每一個細(xì)胞只能處在兩個狀態(tài)中的一個，即”生”和”死” 。開始一行是隨機(jī)配置的。我們把它叫做 A 行，A 行的下面一行就是 B 行，表示下一代的情況。B 行的狀態(tài)由既定的規(guī)則根據(jù) A 行的狀態(tài)來決定。主要考慮下面的情況：B 行的某個細(xì)胞的狀態(tài)依賴于它正上方（A 行）的 3 個細(xì)胞的狀態(tài)。這 3 個個細(xì)胞的狀態(tài)有 8 種可能。如果用”0”來表示死亡，用”1”來表示生存，那么，這 8種狀態(tài)就是：111 ,110,101,100,011,010,001,000,對既定的規(guī)則來說，這三個細(xì)胞決定了 B 行這個細(xì)胞的狀態(tài)。B 行的每一個細(xì)胞的狀態(tài)都可以用同樣的規(guī)則來確定。以下 C 行和 D 行依此類推…很明顯，我們可以用 8 個二進(jìn)制代碼對這個八個狀態(tài)進(jìn)行編碼，每一個編碼就是事實(shí)上的一條規(guī)則，我們可以有 2 的 8 次方（256）種規(guī)則來約束這個一維細(xì)胞自動機(jī)。每一條規(guī)則我們可以用二進(jìn)制代碼的十進(jìn)制數(shù)碼來作為它的代號。下面我們來對這個一維細(xì)胞自動機(jī)進(jìn)行詳細(xì)的研究，請看圖 14：圖 14 一維細(xì)胞自動機(jī)這就是一維細(xì)胞自動機(jī)的模型。這是一個方格的世界，所有的方格都排成一排，每個方格都有黑或白兩種顏色，我們用黑色的格表示直線上 0 狀態(tài)的方格，用白色的格表示 1 狀態(tài)的方格。那么一條斷續(xù)的橫線就是當(dāng)前所有細(xì)胞狀態(tài)的一種分布。這些方格隨著時間變化，就形成了不同的橫線。我們把這些隨著時間變化的線縱向拼在一起形成了一個網(wǎng)格區(qū)域。其中縱軸表示時間的流逝（往下為正） ，橫軸為細(xì)胞自動機(jī)在對應(yīng)時刻的狀態(tài)，就能得到一幅圖像。狀態(tài)指的是每個細(xì)胞的狀態(tài)（如生和死） ，半徑是指每個細(xì)胞鄰居的半徑，第 19 頁 共 31 頁如果是 1，就表明有兩個鄰居，如果是 2 就表明有四個鄰居。編碼也就是我們上面說的那個編碼。照這樣看來，只要我們改變了編碼，相當(dāng)于改變了規(guī)則，我們能比較各種簡單的規(guī)則下，細(xì)胞自動機(jī)能展現(xiàn)出什么復(fù)雜的現(xiàn)象來了。首先我們輸入 224 號規(guī)則，出現(xiàn)了這樣的圖示 圖 15：圖 15 一維細(xì)胞自動機(jī) 224 號規(guī)則的圖形剛出現(xiàn)了一些白點(diǎn)，過了幾個周期，屏幕就變成了一片黑