# 人工智慧導論 生命模擬 康威生命遊戲

## 組別: 第一組

| | 組長 | 組員一 | 組員二 |
| ---- | ----- | ----- | ----- |
| 姓名 | 高聖傑 | 蔡明軒 | 張子姍 |
| 系級 | 資工113 | 資工113 | 資工113 |
| 學號 | B093040016|B093040044|B093040053|

## 摘要

康威生命遊戲是由英國數學家John Horton Conway，於1970所發明的細胞自動機。康威生命遊戲是由一個二維的像素平面世界組成，世界中的每個單位可以居住著一個死亡或存活的細胞。而這個遊戲主要是要模擬這些細胞的消長，讓觀察者(玩家)可以進行觀察，而我們第一組透過網路上的規則，以及一些圖形相關的套件(Pygame,EasyX)，實作了自己的康威生命遊戲。
**關鍵字: 康威生命遊戲, Conway Life Game, Pygame, EasyX**

## 1. 前言簡介
最基礎的生命遊戲是一個零玩家遊戲。它發生在一個二維矩形世界，而這個世界的基本單位是一個等大的小正方形。每個方格皆居住著一個細胞，這個細胞可以是死亡或存活的。一個細胞在下一個時刻的狀態取決於相鄰八個細胞中存活細胞的數量。如果相鄰存活的細胞數量過多，這個細胞會因為資源匱乏而在下一個時刻死亡，若如果周圍活細胞過少，這個細胞則會因太孤獨而死去，這個世界也有繁衍的機制，當附近的存活細胞適當，死掉的細胞也會死而復生。

## 2. 相關研究

要實作康威生命遊戲的第一步，當然是要先知道細胞消長的規則，在維基百科中有一個介紹康威生命遊戲的頁面，裡面就有清楚敘述康威生命遊戲的規則，以下是我們對這些規則的整理。

>1. 若此細胞存活，周圍八個細胞中有小於兩個細胞存活(細胞稀少)，或是大於三個細胞存活(細胞過多)該細胞死亡。
>2. 若此細胞死亡，周圍八個細胞中有三個細胞存活，該細胞復活(細胞繁殖)。

## 3. 程式設計方式

**由於三位組員都具有程式能力，我們三人都各用了一種方式實作康威生命遊戲**

### C++: command-line interface實作 (高聖傑)

- cout to sprintf 優化
- 在第一版時，發現瓶頸是輸出的 for 迴圈裡 cout 佔用太多時間，曾經嘗試使用 printf ，結果比 cout 更慢，於是把目標改成"減少 cout 呼叫次數"。
- $O(n^2)$ 次的 cout 會造成畫面輸出的效能瓶頸，於是改成先在 buffer 內一個一個直接 assign。預處理後，再一次全部 cout ，複雜度一樣是 $O(n^2)$，但最後的常數低了許多，得到更好的輸出效能。

- 小功能：死灰復燃 (repopulate) 系統
- 當一群細胞發生更新（不論是出生或是死亡）時，可以說明此細胞周圍正在變動，也就是說，混亂程度較**高**。
- 當一群細胞達到平衡（不論是動態還是靜態）時，可以說明此細胞周圍已達到相對穩定，也就是說，混亂程度較**低**。
- 可以用 sliding window 來求得**近期**混亂程度的平均值。
- 當系統趨近穩定時，混亂程度平均值就會逐漸下滑，低於設定閥值時，即可加入新的細胞，讓版面再次活躍起來。

### C++: 利用經典圖形庫EasyX(graphics.h) (張子姍)
- EasyX 是針對 C++ 的圖形庫，可以幫助 C 語言初學者快速上手圖形和遊戲編程。

- 比如，可以用 VC + EasyX 很快的用幾何圖形畫一個房子，或者一輛移動的小車，可以編寫俄羅斯方塊、貪吃蛇、黑白棋等小遊戲，可以練習圖形學的各種算法，等等。

### Python: 利用Pygame套件實作 (蔡明軒)

- Pygame 一個簡易的遊戲製作套件

- 由於讓使用者單純觀察細胞消長可能使這個遊戲過於單調，於是我利用了Pygame套件實作出了一個簡單的互動式介面，使用者可以扮演上帝的角色，任意使特定的細胞復活或死亡，也可以暫停這個世界的流動，甚至清除世界中的所有細胞。

- 懶人更新：
- 每一輪 update 時，可以順便記錄將要出生和將要死亡的細胞，將他們分別寫入個別的 Queue 中。當輸出畫面時，就可以只更新有變動過的細胞。

## 4. 結論

經過多次的測試，我們發現就算一開始的生命非常多，細胞死亡的速度也會非常迅速，而死亡的速度會隨著盤面上的細胞數量減少而降低，直到世界維持動態穩定的狀態(圖形變化有固定周期)。

- 每個單位時間死亡的細胞數量，可以發現每一輪死亡的細胞有逐漸減少的趨勢

- 每一輪死亡和復活的數量相等，達到動態穩定

- 達到穩定的世界

## 5. 參考文獻

[1] 康威生命遊戲 - 維基百科
https://zh.wikipedia.org/wiki/%E5%BA%B7%E5%A8%81%E7%94%9F%E5%91%BD%E6%B8%B8%E6%88%8F

[2] Wiki index - pygame wiki
https://www.pygame.org/wiki/

[3] Dev-Cpp/Code::Block/MinGW下使用EasyX
https://www.codeprj.com/zh/blog/bb8a171.html