【文章內(nèi)容簡介】 第 5章 綜合程序練習(xí)題 —— 貪吃蛇 主要算法提示 碰撞檢測模塊： 蛇移動模塊：在程序中定義循環(huán)鏈表來表示蛇，并記錄蛇頭指針以及蛇尾指針、當(dāng)前移動方向。若有方向按鍵信息： a1. 按鍵方向跟當(dāng)前方向相同或是相反，則不做處理； a2. 否則將當(dāng)前方向設(shè)置為新的方向；按當(dāng)前方向得到蛇頭的下一位置；對該位置進(jìn)行碰撞檢測，判斷該位置是什么狀態(tài) c1. 若是蛇身和墻壁，跳到步驟 e； c2. 若是空白，則將蛇尾設(shè)為蛇頭，將倒數(shù)第二節(jié)設(shè)為蛇尾，更新蛇頭的位置為當(dāng)前的新位置。界面上就把當(dāng)前最新位置用蛇的顏色畫上，并把原蛇尾用背景色擦除。 c3. 若是食物，則新增加當(dāng)前位置做為蛇頭，蛇尾不變。利用記分模塊更新分?jǐn)?shù)。并再重新隨機(jī)產(chǎn)生食物。 返回 a做循環(huán)；游戲結(jié)束 第 5章 綜合程序練習(xí)題 —— 五子棋 1：問題描述 ? 五子棋基本規(guī)則：棋盤上形成橫向、豎向、斜向的連續(xù)的相同顏色的五個棋子稱為 “五連 ” 。黑白雙方先在棋盤上形成五連的一方為勝。若對局雙方均認(rèn)為不可能形成五連或是剩余棋盤空間已不足以形成五連則為和棋。下棋過程中不考慮各種禁手規(guī)則。 2：基本功能 ? 提供圖形界面 、 鍵盤操作 、 人人對戰(zhàn) 、 支持某方先下 、 棋盤 15*15，顯示網(wǎng)格線 ， 黑白棋子 、 當(dāng)前光標(biāo)所在；顯示當(dāng)前執(zhí)棋方 3：高級功能 ? 支持人機(jī)對戰(zhàn)，顯示人機(jī)對子情況和勝負(fù)判別 ? 悔棋功能 ? 音效功能 第 5章 綜合程序練習(xí)題 —— 五子棋 難點分析 1）勝負(fù)判別 2）悔棋功能 3）人機(jī)對戰(zhàn)的人工智能部分 五子棋的人機(jī)對戰(zhàn)是一個典型的博弈問題。博弈問題一般可用極大 極小法和 αβ法求解（讀者可找相關(guān)資料，一般人工智能或博弈論教材中會涉及這些內(nèi)容）。而即便是用 αβ法，五子棋的搜索空間還是相當(dāng)龐大。 第 5章 綜合程序練習(xí)題 —— 五子棋 設(shè)計及實現(xiàn)要點 游戲初始化模塊 主循環(huán)控制模塊 鍵盤處理模塊 勝負(fù)判別模塊 人工智能模塊 游戲結(jié)束清理模塊 五子棋程序的總體結(jié)構(gòu) 第 5章 綜合程序練習(xí)題 —— 五子棋 主要數(shù)據(jù)結(jié)構(gòu)提示 （ 一 ） 1）棋盤用 15*15的二維數(shù)組表示，數(shù)組的每一個元素對應(yīng)棋盤上的一個交叉點，用‘ 0’表示空位、‘ 1’代表玩家 1的子、‘ 2’代表玩家 2的子 ： char ChessBoard[15][15]。 第 5章 綜合程序練習(xí)題 —— 五子棋 主要數(shù)據(jù)結(jié)構(gòu)提示 （ 二 ） 2)用于搜索過程的結(jié)構(gòu)體： typedef struct five_chess* point。 struct five_chess{ int x。 int y。 int layer。 int value。 int score。 int chess[LENGTH][LENGTH]。 int record[LENGTH][LENGTH]。 }。 其中， x,y表示在某個位置上擴(kuò)展出來的新節(jié)點， layer是表示第幾層擴(kuò)展，用于控制擴(kuò)展深度。 value表示該點上極大極小值， score表示葉子節(jié)點的得分，用于推算父輩節(jié)點的 value， chess這個二維數(shù)組表示擴(kuò)展出來的棋盤信息， record記錄在 x、 y點上擴(kuò)展過的節(jié)點，如果沒有擴(kuò)展 record中對應(yīng)某個值為 0。如果record中沒有可以擴(kuò)展的節(jié)點，那么該層擴(kuò)展結(jié)束，返回一個特定值。 第 5章 綜合程序練習(xí)題 —— 五子棋 主要算法提示 （ 一 ） 對棋盤的評分算法。評估一個棋盤的分?jǐn)?shù)，主要通過掃描 整個棋盤，對每個點評分。對某個點上評分從四個方向 ( 角度分別為 0、 4 90、 135的四個方向 )分別統(tǒng)計，進(jìn)而 累積該點總分，最后得到整個棋盤的分?jǐn)?shù)。實際上對當(dāng)前 的局面按照下面規(guī)則的順序進(jìn)行比較，如果滿足某一條規(guī) 則的話，就給該局面打分并保存，然后退出規(guī)則的匹配。 注意這里的規(guī)則是根據(jù)一般的下棋規(guī)律的一個總結(jié)，在實 際運行的時候，可以添加規(guī)則和對評分機(jī)制加以修正。 第 5章 綜合程序練習(xí)題 —— 五子棋 主要算法提示 （ 二 ） 人工智能部分的搜索算法流程如下（以擴(kuò)展兩層為例）： ? 根據(jù)棋盤信息 chessman[15][15]建立根結(jié)點 s0（數(shù)據(jù)結(jié)構(gòu)：five_chesman） ,并把 s0壓入堆棧中 ? 擴(kuò)展 s1=top()；判斷 s1layer是否等于－ 1 ? s1layer等于－ 1， push(s1),擴(kuò)展 s2=top(),查看 s2layer是否－ 1 ? s2layer!=1，計算此時棋盤得分 score，并判斷是否要更改上一層的極小值 ? s2layer==1,pop()：判斷是否更改極大值， max_chess指向得分最高的棋盤 ? 如果 s1layer=1,表示搜索結(jié)束，返回最大棋盤信息 max_chess 第 5章 綜合程序練習(xí)題 —— 搬運工 1：問題描述 在一個四周有圍墻的倉庫的中，堆放著若干箱子、阻擋箱子前進(jìn)的障礙物，以及標(biāo)識出了箱子需要被推到的目標(biāo)位置。游戲者通過觀查分析，找到合適的策略，然后只能用推的方法把所有散落在場地中的箱子借助于空閑區(qū)間推到目標(biāo)位置，即獲得勝利；否則失敗 2：基本功能 ? 場地元素定義與設(shè)計 、 箱子的搬運動作 、 提供一定數(shù)量的按鍵功能實現(xiàn)游戲者對搬運工的多種操作 3：高級功能 ? 提供多套場地 ? 提供視聽效果 ? 智能識別游戲的終止 ? 自動完成移動 第 5章 綜合程序練習(xí)題 —— 搬運工 難點分析 墻壁 箱子 x y 死角判定： 這里舉一個例子，如下圖所示： 死角判定 第 5章 綜合程序練習(xí)題 —— 搬運工 設(shè)計及實現(xiàn)要點 搬運工程序的總體結(jié)構(gòu) 第 5章 綜合程序練習(xí)題 —— 搬運工 主要數(shù)據(jù)結(jié)構(gòu)提示 系統(tǒng)的組成元素主要包含外圍墻壁、內(nèi)部障礙物、箱子、搬運工。我們先建立一個虛擬的元素（不妨稱之為容器），它用來將整個圖形界面網(wǎng)格化，并記錄各種圖形元素的位置等屬性。然后，再為各個圖形元素建立相應(yīng)的保存其特有信息的數(shù)據(jù)結(jié)構(gòu)。 先定義兩個基本結(jié)構(gòu)，在后面也會用到： typedef struct tagRect /*矩形 */ { Point leftTop, rightButton。/*矩形左上定點和右下定點 */ } Rect。 typedef struct tagPoint /*直角坐標(biāo)系點 */ { int x, y。 } Point。 第 5章 綜合程序練習(xí)題 —— 搬運工 主要數(shù)據(jù)結(jié)構(gòu)提示 1）虛擬的容器結(jié)構(gòu)體： typedef struct tagContainer { Rect cRect。 /*確定整個容器在屏幕上的坐標(biāo) */ int cBoard[N][M]。 /*N、 M是事先設(shè)定的網(wǎng)格行數(shù)和列數(shù) */ } Container。 其中數(shù)組 cBoard其取值代表各網(wǎng)格是何種圖形元素：箱子、空格、障礙、目標(biāo)位置，其它必要屬性，可自行酌情添加。 第 5章 綜合程序練習(xí)題 —— 搬運工 主要數(shù)據(jù)結(jié)