基于分支限界法的連連看局域網對戰游戲的開發_畢業設計論文-資料下載頁

【導讀】的“尋路”過程。性、可維護性、可修改性和可擴充性。戲更具備對抗性和刺激性。闡述了分支限界法與面相對象開發思想在連連看局域網對戰游戲中的應用。論文內容與結構........

　　

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