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