【正文】 OPEN← OPEN+{yi}。 f(yi)← g(yi)+h(yi)。 ik。} else { 對節(jié)點(diǎn) x 進(jìn)行擴(kuò)展，其子節(jié)點(diǎn)集合為 {y0,y1,...,yk1}。 if(x==T) {記錄解 。 OPEN← OPEN{x}。 A*算法的基本搜索步驟如下： void AStar() { 初始化 OPEN← {S0}, CLOSED← Φ, g(S0)← 0, f(S0)← 0, preds0← NULL, found← false。 一般來說，在滿足 h(n)≤ h*(n)的前提下， h(n)的值越大越好。其中， 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è)。 假設(shè) f*(x)是從初始狀態(tài) S0出發(fā)，約束經(jīng)過狀態(tài) x 達(dá)到目標(biāo)狀態(tài) T 的最小代價(jià)，估值函數(shù) f(x)是對 f*(x)的估計(jì)值。 CLOSE 表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展的節(jié)點(diǎn)。對于不同的搜索策略，節(jié)點(diǎn)在 OPEN 表中的排列順序是不同的。 A*算法涉及兩張表，即OPEN 表和 CLOSE 表。 } } } A*算法簡介 回溯法和分支限界法在搜索過程中有一定的盲目性。 } if(NextNode 非法 or NextNode 肯定不包含最優(yōu)解 ) { continue。 for each(CurrNode 生成的孩子節(jié)點(diǎn) NextNode) { if(NextNode 包含解 ) { 記錄解 。 void BranchBound() { 定義活結(jié)點(diǎn)列表 Q，一般是優(yōu)先隊(duì)列或者 FIFO 隊(duì)列 定義當(dāng)初始狀態(tài)前活結(jié)點(diǎn) CurrNode CurrNode 進(jìn)隊(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)先的原則。 優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級常用一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值 p 來表示。 1．隊(duì)列式（ FIFO）分支限界法：隊(duì)列式分支限界法將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并按隊(duì)列的先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。這個(gè)過程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止[2]。在這些孩子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的孩子結(jié)點(diǎn)被舍棄，其余孩子結(jié) 點(diǎn)被加入活結(jié)點(diǎn)表中。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)。 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索解空間樹 [2]。 } for each(CurrentState 的后繼狀態(tài) NextState) { Backtrack(level + 1, NextState) } } 分支限界法簡介 分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。 } if(CurrentState 是非法狀態(tài) ) { return。 return。 回溯法的算法設(shè)計(jì)使用偽代碼表示如下。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(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)往回移動（回溯）到最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。 回溯法從開始結(jié)點(diǎn)（根結(jié)點(diǎn)） 出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。用它可以系統(tǒng)地搜索一個(gè)問題的所有解或任一解。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為 “ 回溯點(diǎn) ” 。窮舉搜索的思想是不管狀態(tài)優(yōu)劣， “ 一個(gè)都不放過 ” ，顯然是最沒有 “ 技術(shù)含量 ” 的，適用于問題規(guī)模較小或者找不到更好的搜索方法的情況，對于問題規(guī)模較大的情況下不適用。 圖 CCardGameDlg 類的設(shè)計(jì) 小結(jié) 本章使用面向?qū)ο蠓椒ㄡ槍⒁_發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲進(jìn)行了分析與設(shè)計(jì)，對游戲進(jìn)行 UML 建模，獲得了游戲的用例圖、活動圖、順序圖、部分游戲?qū)ο蟮臓顟B(tài)圖和類圖。 圖 CServerSocket 類的設(shè)計(jì) 游戲主對話框類的設(shè)計(jì) 連連看局域網(wǎng)對戰(zhàn)游戲主對話框 CCardGameDlg 類主要針對 m_Board（棋盤類）、 .m_ListenSocket（監(jiān)聽套接字）、 ClientSocket()（客戶端套接字）、m_Control()（控制器）、 OnPaint()（畫刷函數(shù)）、 SetClientSize()（設(shè)置客戶端 IP大小）、 OnSet()（設(shè)置網(wǎng)絡(luò)連接）、 OnNew()（啟動網(wǎng)絡(luò)對戰(zhàn)）等進(jìn)行相應(yīng)定義。 圖 CListenSocket 類的設(shè)計(jì) 服務(wù)套接字類的設(shè)計(jì) 服務(wù)套接字 CServerSocket 類繼承自 MFC 的 CSocket 類， CServerSocket 主要針對 OnReceive()（接收到客戶端套接字發(fā)送過來的數(shù)據(jù)時(shí)的處理函數(shù)）、 .m_nWnd（游戲窗體句柄）、 OnClose()（關(guān)閉套接字時(shí)的處理函數(shù)）、SetHWnd()（設(shè)置游戲窗體句柄）等進(jìn)行相應(yīng)定義。 圖 CClientSocket 類的設(shè)計(jì) 監(jiān)聽套接字類的設(shè)計(jì) 監(jiān)聽套接字類 CLintenSocket 類繼承自 MFC 的 CSocket 類， CLintenSocket主要針對 OnAccept()（接收到套接字連接請求的處理函數(shù)）、 .m_hWnd（游戲窗體句柄）、 StartGame()（游戲開始）、 SetHWnd()（設(shè)置窗體句柄）等進(jìn)行相應(yīng)定義。 CClientSocket 主要針對 SetDraw()（設(shè)置繪圖器對象）、 .m_hWnd（游戲窗體句柄）、 SetControl()（設(shè)置控制器）、 m_pControl（控制器）、 m_pDraw（畫圖）、 GetConTrol()（獲取控制器）、 SetHWnd()（設(shè)置窗體句柄）、 OnReceive()（接收到客戶端套接字發(fā)送過來的數(shù)據(jù)時(shí)的處理函數(shù)）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。其詳細(xì)定義的相關(guān)類圖如圖 所示。其詳細(xì)定義的相關(guān)類圖如圖 所示。其詳細(xì)定義的相關(guān)類圖如圖 所示。 游戲的類關(guān)系圖 通過需求分析得到的用例模型以及活動圖，可以分析得出 游戲系統(tǒng)中所要涉及的一些基本的對象，如：游戲牌、棋盤區(qū)、控制系統(tǒng)、對話框（窗體）、繪圖系統(tǒng)和數(shù)據(jù)包等。短式圖形符號由一個(gè)矩形實(shí)績方框及在方框內(nèi)書寫的類名表示。一個(gè)系統(tǒng)的類模型可以由多張類圖描述，一個(gè)類也可以出現(xiàn)在幾張類圖中。類之間的關(guān)系有關(guān)聯(lián)、聚集、繼承、依賴、細(xì)化等。建立類和對象模型是面向?qū)ο蠓治雠c設(shè)計(jì)方法的核心技術(shù)之一，也是面向?qū)ο蠹夹g(shù)的基本任務(wù)，是軟件開發(fā)的基礎(chǔ) [4]。 圖 雙人對戰(zhàn)模式每隔 1 秒的扣時(shí)操作的順序圖 雙人對戰(zhàn)模式下，客戶端套接字處理接收到的數(shù)據(jù)包的順序圖，如圖 所示。 圖 單人游戲模式每隔 1 秒的扣時(shí)操作的順序圖 雙人對戰(zhàn)模式下的處理一次鼠標(biāo)點(diǎn)擊事件的順序圖如圖 所示。 單人游戲模式下的活動圖，如圖 所示。玩家可隨時(shí)選擇開始單人游戲，在局域網(wǎng)雙人對戰(zhàn)游戲中，只有服務(wù)器端有選擇可以開始游戲，而客服端只 能等待游戲開始。 圖 系統(tǒng)模塊結(jié)構(gòu)圖 “ 選中游戲牌 ” 過程的順序圖 連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)根據(jù)其業(yè)務(wù)邏輯來看，提供了單人游戲模式和局域網(wǎng)雙人對戰(zhàn)模式。 “ 游戲設(shè)置 ”子系統(tǒng)包含 “ 局域網(wǎng)連接設(shè)置 ” 功能模塊。 待開發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲程序，包含游戲模式選擇和游 戲設(shè)置兩個(gè)子系統(tǒng)。 本文設(shè)計(jì)的連連看局域網(wǎng)雙人對戰(zhàn)游戲，雖然不涉及 Web，也不涉及數(shù)據(jù)庫，但是也可以吸收 MVC 模式的特點(diǎn)，從某種程度上降低了程序的復(fù)雜度，使程序結(jié)構(gòu)更加直觀。 程序結(jié)構(gòu)介紹 在 Web 開發(fā)中，有一種常用的開發(fā)模式，被稱為 MVC 模式（ ModelView Controller），這種模式開發(fā)的 Web 系統(tǒng)大致由模型（ Model）、視圖（ View）和控制器（ Controller）三個(gè)基本部分組成。本文選擇用順序圖對交互進(jìn)行建模。它通常用來描述一個(gè)用例的行為，顯示該用例中所涉及的對象和這些對象之間的消息傳遞情況。因此在設(shè)計(jì)系統(tǒng)時(shí)，就免不了對交互進(jìn)行建模，并用交互圖展現(xiàn)出來。 因此，得到棋盤對象的狀態(tài)圖如圖 所示： 圖 棋盤對象的狀態(tài)圖 對象交互建模 交互建模與順序圖的概念 一次交互就是指在特定語境中，為了實(shí)現(xiàn)某一個(gè)目標(biāo)，而在一組對象之間進(jìn)行交換的一組消息所表示的行為。 游戲牌對象的狀態(tài)，包括 “ 選中 ” 、 “ 未選中 ” 、 “ 清除 ”3 個(gè)狀態(tài)。描述狀態(tài)圖的圖符元素除了圖符和遷移圖符外，還有起始狀態(tài)（用實(shí)心圓表示）、結(jié)束狀態(tài)（用一個(gè)圓中間套實(shí)心圓表示）、條件判定（用空心菱形表示）、發(fā)出信號（用一個(gè)一側(cè)為凸尖角的矩形表示）、接收信號（用一個(gè)一側(cè)為凹尖角的矩形表示）和并發(fā)（用一條粗短實(shí)線表示）等各種圖符元素 [4,5]。顯然，軟件的運(yùn)行平臺對硬件的要求要低于開發(fā)平臺。 此次開發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲程序，既沒有涉及到數(shù)據(jù)庫，也沒有涉及到中間件等環(huán)境。 圖 局域網(wǎng)對戰(zhàn)模式活動圖 開發(fā)工具的選擇 在軟件開發(fā)行業(yè)中，各種可視化程序設(shè)計(jì)工具和編譯平臺如： Visual C++、Visual C、 Delphi、 C++Builder、 Java 等都是當(dāng)今的主流。 單人游戲模式下的活動圖，如圖 所示。玩家可隨時(shí)選擇開始單人游戲，在局域網(wǎng)雙人對戰(zhàn)游戲中，有且只有服務(wù)器端有選擇可以開始游戲的權(quán)利，而客服端只能等待游戲開始。 游戲的活動圖 連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)根據(jù)其業(yè)務(wù)邏輯來看，提供了單人游戲模式和局域網(wǎng)雙人對戰(zhàn)模式。 活動圖的終止點(diǎn)，即活動圖的最后活動稱為結(jié)束活動，本身無活動。 用帶箭頭的實(shí)線表示各種活動狀態(tài)的先后順序，即遷移。活動圖實(shí)際上也是一種流程圖，它描述活動的序列，即系統(tǒng)從一個(gè)活動到另一個(gè)活動的控制流，與流程圖不同的是，活動圖還可以描述系統(tǒng)的并發(fā)處理 [4,5]。 “ 設(shè)置局域網(wǎng)連接 ” 用例的用例描述如表 所示。 表 “進(jìn)行局域網(wǎng)雙人對戰(zhàn)游戲 ” 用例的用例描述 名稱 描述 用例名稱 進(jìn)行局域網(wǎng)雙人對戰(zhàn)游戲 執(zhí)行者 玩家 目的 在局域網(wǎng)雙人對戰(zhàn)模式下進(jìn)行游戲 類型 主要的 過程描述 1．玩家選擇作為同時(shí)作為服務(wù)端和客戶端，還是僅作為客戶端。 3．每隔 1 秒鐘，計(jì)時(shí)器自動減 1，如果時(shí)間耗盡，轉(zhuǎn) 14； 4．如果玩家用鼠標(biāo)選中一張游戲牌，轉(zhuǎn) 5，否則轉(zhuǎn) 3； 5．搜索玩家上一次選中的并且未消去的游戲牌，如果不存在玩家上一次選中的并且未消去的游戲牌，轉(zhuǎn) 12，否則，轉(zhuǎn) 6； 6．如果玩家當(dāng)前選中的游戲牌和上次選中的并且未消去的 游戲牌不是同一張游戲牌，轉(zhuǎn) 7；否則，轉(zhuǎn) 13； 7．判斷當(dāng)前選中的游戲牌和上次選中的并且未消去的游戲牌能否消去，如果不能，轉(zhuǎn) 8，如果能，轉(zhuǎn) 9； 8．將玩家上一次選中的并且未消去的游戲牌取消選中，將當(dāng)前選中的游戲牌指為選中狀態(tài)，并罰時(shí) 4 秒鐘，轉(zhuǎn) 3； 9．將當(dāng)前選中的游戲牌指為選中狀態(tài)，消去這一對游戲牌，并加時(shí) 2 秒鐘，轉(zhuǎn) 11； 10．如果棋盤內(nèi)所有的游戲牌都被消去，轉(zhuǎn) 15，否則，轉(zhuǎn) 14； 11．如果不存在一對能夠消去的游戲牌，則在原有位置重新擺放未消去的游戲牌，直到存在一對能夠消去的游戲牌，轉(zhuǎn) 3； 12．將當(dāng)前選中的游戲牌置為選中狀態(tài)，轉(zhuǎn) 3； 13．將上一次選中的并且未消去的游戲牌置為未選中狀態(tài)，轉(zhuǎn) 3； 14．游戲失敗，則給出相應(yīng)的失敗信息提示，轉(zhuǎn) 16； 15．游戲勝利，則給出相應(yīng)的勝利信息提示； 16．游戲結(jié)束。 表 “進(jìn)行單人游戲 ” 用例的用例描述 名稱 描述 用例名稱 進(jìn)行單人游戲 執(zhí)行者 玩家 目的 在單價(jià)模式下進(jìn)行游戲 類型 基本的、主要的 過程描述 1．選擇 “ 游戲 ” 菜單中的 “ 開始單人游戲 ” 選項(xiàng)，啟動開始單人游戲。下面將給出“ 進(jìn)行單人游戲 ” 用例、 “ 進(jìn)行局域網(wǎng)雙人對戰(zhàn)游戲 ” 用例、 “ 設(shè)置局域網(wǎng)連接 ” 用例的用例，與其有關(guān)聯(lián)的擴(kuò)展用例和包含用例、子用例將會在這三個(gè)用例中一并描述。 連連看局域網(wǎng)對戰(zhàn)游戲的用例圖，如圖 所示。 玩家通過選 擇游戲模式，與 “ 進(jìn)行單人游戲 ” 用例、 “ 進(jìn)行局域網(wǎng)雙人對戰(zhàn) ” 用例這兩個(gè)用例進(jìn)行交互。 游戲的用例圖 待開發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)，支持單人游戲，也支持在一臺機(jī)器上或者局域網(wǎng)不同的兩臺機(jī)器上最多有兩個(gè)玩家同時(shí)游戲，但這兩個(gè)玩家的性質(zhì)完全相同，因此處于系統(tǒng)邊界之外的參與者只有一個(gè)，就是玩家。執(zhí)行者（ actor）[4,5]是指在系統(tǒng)外部與系統(tǒng)交互的人或其他系統(tǒng)，他