【導(dǎo)讀】的“尋路”過程。性、可維護(hù)性、可修改性和可擴(kuò)充性。戲更具備對(duì)抗性和刺激性。闡述了分支限界法與面相對(duì)象開發(fā)思想在連連看局域網(wǎng)對(duì)戰(zhàn)游戲中的應(yīng)用。論文內(nèi)容與結(jié)構(gòu)........

　　

【正文】 否勝利）、 AddTime()（設(shè)置游戲時(shí)間）、 GetGameState()（獲取游戲狀態(tài)）等進(jìn)行相應(yīng)定義。其詳細(xì) 定義的相關(guān)類圖如圖 所示。 圖 CBoard類的設(shè)計(jì) 繪圖器類的設(shè)計(jì) 繪圖器類 CDraw主要針對(duì) m_rcClient（窗體客戶區(qū)對(duì)應(yīng)的矩形）、 m_brsBG（背景畫刷對(duì)象）、 m_DCMen（內(nèi)存緩存 DC）、 m_BmpMem（內(nèi)存畫布）、m_pDC （設(shè)置 DC ）、 DrawBoard()（繪制棋盤）、 SetDC()（創(chuàng)建 DC ）、 GetCardWidth()（獲取游戲牌在界面中的寬度）、 GetCardHeight()（獲取游戲牌在界面中的高度）、 m_nBmpWidth（游戲牌的位圖寬度）、 m_BmpUnselect()（包含了未選中游戲牌圖案的 CBitmap 類）、 m_BITMAP_Unselect（未選中游戲牌圖案的位圖結(jié)構(gòu)）、 m_DCSelect（已選中的游戲牌圖片資源對(duì)應(yīng)的內(nèi)存圖片DC）、 m_DCUnSelect（未選中的游戲牌圖片資源對(duì)應(yīng)的內(nèi)存圖片 DC）m_nBmpHeight（游戲牌的位圖高度）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。 圖 CDraw類的設(shè)計(jì) 控制器類的設(shè)計(jì) 控制器類 CControl，該類繼承自 MFC 的 CDialogEx類， CControl主要針對(duì)m_pDraw（控制器所控制的繪圖器指針）、 m_pBoard（控制器所控制的棋盤指針）、 m_nTimer（游戲定時(shí)器）、 m_nGameMode（游戲模式，單機(jī)還是局域網(wǎng)）、 m_pClientSocket（客戶端套接字指針）、 m_pListenSocket（服務(wù)端的監(jiān)聽套接字指針）、 OnLButtonDown()（鼠標(biāo)左鍵響應(yīng)事件）、 OnTimer()（定時(shí)器啟動(dòng)響應(yīng)函數(shù)）、 GetBoard()（獲取棋盤指針）、 SendToSocket()（發(fā)送套接字?jǐn)?shù)據(jù)包）、 CloseAllSocket()（關(guān)閉所有套接字）、 GetGameMode()（獲取游戲模式，單機(jī)還是局域網(wǎng)）、 GetClientSocket()（獲取客戶端套接字）、 SetGameMode()（設(shè)置游戲模式，單機(jī)還是局域網(wǎng)）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。 圖 CControl類的設(shè)計(jì) 客戶套接字類的設(shè)計(jì) 客戶套接字 CClientSocket 類繼承自 MFC 的 CSocket 類。 CClientSocket 主要針對(duì) SetDraw()（設(shè)置繪圖器對(duì)象）、 .m_hWnd（游戲窗體句柄）、 SetControl()（設(shè)置控制器）、 m_pControl（控制器）、 m_pDraw（畫圖）、 GetConTrol()（獲取控制器）、 SetHWnd()（設(shè)置窗體句柄）、 OnReceive()（接收到客戶端套接字發(fā)送過來的數(shù)據(jù)時(shí)的處理函數(shù)）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。 圖 CClientSocket類的設(shè)計(jì) 監(jiān)聽套接字類的設(shè)計(jì) 監(jiān)聽套接字類 CLintenSocket 類繼承自 MFC 的 CSocket 類， CLintenSocket主要針對(duì) OnAccept()（接收到套接字連接請(qǐng)求的處理函數(shù)）、 .m_hWnd（游戲窗體句柄）、 StartGame()（游戲開始）、 SetHWnd()（設(shè)置窗體句柄）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。 圖 CListenSocket類的設(shè)計(jì) 服務(wù)套接字類的設(shè)計(jì) 服務(wù)套接字 CServerSocket 類繼承自 MFC 的 CSocket 類， CServerSocket 主要針對(duì) OnReceive()（接收到客戶端套接字發(fā)送過來的數(shù)據(jù)時(shí)的處理函數(shù)）、 .m_nWnd（游戲窗體句柄）、 OnClose()（關(guān)閉套接字時(shí)的處理函數(shù)）、SetHWnd()（設(shè)置游戲窗體句柄）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。 圖 CServerSocket類的設(shè)計(jì) 游戲主對(duì)話框類的設(shè)計(jì) 連連看局域網(wǎng)對(duì)戰(zhàn)游戲主對(duì)話框 CCardGameDlg 類主要針對(duì) m_Board（棋盤類）、 .m_ListenSocket（監(jiān)聽套接字）、 ClientSocket()（客戶端套接字）、m_Control()（控制器）、 OnPaint()（畫刷函數(shù)）、 SetClientSize()（設(shè)置客戶端 IP大?。?OnSet()（設(shè)置網(wǎng)絡(luò)連接）、 OnNew()（啟動(dòng)網(wǎng)絡(luò)對(duì)戰(zhàn)）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。 圖 CCardGameDlg 類的設(shè)計(jì) 小結(jié) 本章使用面向?qū)ο蠓椒ㄡ槍?duì)將要開發(fā)的連連看局域網(wǎng)對(duì)戰(zhàn)游戲進(jìn)行了分析與設(shè)計(jì)，對(duì)游戲進(jìn)行 UML 建模，獲得了游戲的用例圖、活動(dòng)圖、順序圖、部分游戲?qū)ο蟮臓顟B(tài)圖和類圖。 ? 算法設(shè)計(jì) 狀態(tài)空間搜索算法簡(jiǎn)介 窮舉搜索法簡(jiǎn)介 窮舉搜索法 [2]是編程中常用到的一種方法，通常在找不到解決問題的規(guī)律時(shí)對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從中找出那些符合要求的候選解作為問題的解。窮舉搜索的思想是不管狀態(tài)優(yōu)劣， “ 一個(gè)都不放過 ” ，顯然是最沒有 “ 技術(shù)含量 ” 的，適用于問題規(guī)模較小或者找不到更好的搜索方法的情況，對(duì)于問題規(guī)模較大的情況下不適用。 回溯法簡(jiǎn)介 回溯法 [2]是一種深度優(yōu)先的選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為 “ 回溯點(diǎn) ” ?；厮莘ㄓ?“ 通用的解題法 ” 之稱。用它可以系統(tǒng)地搜索一個(gè)問題的所有解或任一解?；厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。 回溯法從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)（自身已生成但其孩子結(jié)點(diǎn)還沒有全部生成的結(jié)點(diǎn)稱為活結(jié)點(diǎn)），同時(shí)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)（正 在產(chǎn)生孩子結(jié)點(diǎn)的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)），在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)，這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前的擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)（所有的孩子結(jié)點(diǎn)已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)點(diǎn)），此時(shí)，應(yīng)往回移動(dòng)（回溯）到最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。反復(fù)如此，直到找到所需要的解，或者解空間已經(jīng)沒有活結(jié)點(diǎn)時(shí)為止 [2]。 回溯法的算法設(shè)計(jì)使用偽代碼表示如下。 void Backtrack(int level, STATETYPE CurrentState) { if(CurrentState 包含問題的解 ) { 記錄解 。 return。 } if(CurrentState 是終止?fàn)顟B(tài) ) { return。 } if(CurrentState 是非法狀態(tài) ) { return。 } if(CurrentState 肯定不包含問題的最優(yōu)解 ) { return。 } for each(CurrentState 的后繼狀態(tài) NextState) { Backtrack(level + 1, NextState) } } 分支限界法簡(jiǎn)介 分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。一般情況下，分支限界法是在滿足約束條件的所有解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索解空間樹 [2]。在搜索問題的解空間樹時(shí)，分支限界法與回溯法對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有孩子結(jié)點(diǎn)。在這些孩子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的孩子結(jié)點(diǎn)被舍棄，其余孩子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止[2]。 從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的方式通常有以下兩種 [2]。 1．隊(duì)列式（ FIFO）分支限界法：隊(duì)列式分支限界法將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并按隊(duì)列的先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 2．優(yōu)先隊(duì)列式分支限界法：優(yōu)先隊(duì)列式分支限界法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列，交按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)常用一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值 p 來表示。結(jié)點(diǎn)優(yōu)先級(jí)的高低與 p 值大小相關(guān)，根據(jù)問題的不同情況，采用大根堆或小根堆來描述優(yōu)先隊(duì)列。用一個(gè)大根堆來實(shí)現(xiàn)最大優(yōu)先隊(duì)列，體現(xiàn)最大效益優(yōu)先的原則；用一個(gè)小根堆來實(shí)現(xiàn)最小優(yōu)先隊(duì)列，體現(xiàn)最小費(fèi)用優(yōu) 先的原則。 分支限界法可用偽代碼表示如下。 void BranchBound() { 定義活結(jié)點(diǎn)列表 Q，一般是優(yōu)先隊(duì)列或者 FIFO隊(duì)列 定義當(dāng)初始狀態(tài)前活結(jié)點(diǎn) CurrNode CurrNode 進(jìn)隊(duì)列 。 while(Q不為空 ) { Q中的隊(duì)首節(jié)點(diǎn) CurrNode 出隊(duì)列 。 for each(CurrNode 生成的孩子節(jié)點(diǎn) NextNode) { if(NextNode 包含解 ) { 記錄解 。 return。 } if(NextNode 非法 or NextNode 肯定不包含最優(yōu)解 ) { continue。 } 將 NextNode 插入到 Q中 。 } } } A*算法簡(jiǎn)介 回溯法和分支限界法在搜索過程中有一定的盲目性。 A*算法 [6]是一種啟發(fā)式搜索算法，在一定程度上，可以減少搜索的盲目性。 A*算法涉及兩張表，即OPEN 表和 CLOSE 表。 OPEN 表用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索策略，節(jié)點(diǎn)在 OPEN 表中的排列順序是不同的。 OPEN 表的節(jié)點(diǎn)信息至少包含兩個(gè)域：節(jié)點(diǎn)所表示的狀態(tài)，以及父節(jié)點(diǎn)的指針。 CLOSE 表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展的節(jié)點(diǎn)。 CLOSE 表的節(jié)點(diǎn)信息至少包含三個(gè)域：節(jié)點(diǎn)的編號(hào)、節(jié)點(diǎn) 所表示的狀態(tài)，以及父節(jié)點(diǎn)的指針。 假設(shè) f*(x)是從初始狀態(tài) S0出發(fā)，約束經(jīng)過狀態(tài) x達(dá)到目標(biāo)狀態(tài) T的最小代價(jià)，估值函數(shù) f(x)是對(duì) f*(x)的估計(jì)值。且 f*(x)=g*(x)+h*(x)。其中， g*(x)是從初始狀態(tài) S0到狀態(tài) x 的最小代價(jià)； h*(x)是從狀態(tài) x 到目標(biāo)狀態(tài) T 的最小代價(jià)，若有多個(gè)目標(biāo)狀態(tài)，則為其中最小的一個(gè)。如果搜索過程滿足如下限制，則它就稱為 A*算法： 1．把 OPEN 表中的狀態(tài)按估值函數(shù) f(x)=g(x)+h(x)的值從小至大進(jìn)行排序； 2． g(x)不小于從初始狀態(tài) S0到狀態(tài) x的最小代價(jià) g*(x)，即對(duì)所有的 x均有g(shù)(x)≥ g*(x)； 3． h(x)不大于從狀態(tài) x到達(dá)目標(biāo)狀態(tài) T的最優(yōu)路徑代價(jià) h*(x)，即對(duì)所有的x均有： h(x)≤ h*(x)。 一般來說，在滿足 h(n)≤ h*(n)的前提下， h(n)的值越大越好。 h(n)的值越大，攜帶的啟發(fā)性信息越多， A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少，搜索效率就越高。 A*算法的基本搜索步驟如下： void AStar() { 初始化 OPEN← {S0}, CLOSED← Φ, g(S0)← 0, f(S0)← 0, preds0← NULL, found← false。 while(OPEN≠ Φ且 found==false) { x← OPEN 表中第一個(gè)節(jié)點(diǎn) 。 OPEN← OPEN{x}。 CLOSED← CLOSED+{x}。 if(x==T) {記錄解 。 found← true。} else { 對(duì)節(jié)點(diǎn) x 進(jìn)行擴(kuò)展，其子節(jié)點(diǎn)集合為 {y0,y1,...,yk1}。 for(i← 0。 ik。 i++){ if(yi不屬于 OPEN 且 yi不屬于 CLOSED) { g(yi)← g(x)+C(x,yi)。 f(yi)← g(yi)+h(yi)。 predyi← x。 OPEN← OPEN+{yi}。