【正文】 11．等待服務(wù)端響應(yīng)； 12．如果接收到服務(wù)端的響應(yīng)消息，給出連接成功提示，轉(zhuǎn) 13，否則轉(zhuǎn)11； 13．操作結(jié)束 活動圖建模 活動圖的概念 活動圖是系統(tǒng)動態(tài)行為建模的圖形工具之一，用來表示完成一個操作所需求的活動，或者是一個用例實(shí)例（場景）的活動 [4,5]。 “ 進(jìn)行單人游戲 ” 用例的用例描述如表 所示。 “ 與系統(tǒng)交互 ” 是指執(zhí)行者向系統(tǒng)發(fā)送消息，或從系統(tǒng)那里接收消息，或與系統(tǒng)交換信息。在用例模型中，功能以用例來表示，每個用例指明了一個完整的功能 。 第 4 章，標(biāo)題為 “ 面向?qū)ο髮?shí)現(xiàn) ” ，闡述待開發(fā)的連連看游戲的面向?qū)ο髮?shí)現(xiàn)過程，并給出編程時使用到的具體技術(shù)，如： Windows GDI 雙緩沖、Socket 套接字編程。 面向?qū)ο蟮姆椒▌t是將軟件系統(tǒng)看作一系列離散的解空間對象的集合，并使問題空間的對象與解空間對象盡量一致，這些解空間對象相互之間發(fā)送消息而相互作用，從而獲得問題空間的解 [3,4]。 狀態(tài)空間至少包含問題的一個最優(yōu)解。傳統(tǒng)的連連看游戲的最初運(yùn)行界面如圖 所示。之后村子的連連看風(fēng)靡版，阿達(dá)的連連看奧運(yùn)版，連連看反恐版，還有敏敏連連看，水晶連連看等遍地開花，造就了一個連連看的新世界。 游戲大致分為兩大類，即單機(jī)游戲（ Console Game）和網(wǎng)絡(luò)游戲（ Online Game）。 連連看 。 本科畢業(yè)論文（設(shè)計） 題 目 基于分支限界法的連連看局域網(wǎng)對戰(zhàn)游戲的開發(fā) 作 者 學(xué) 院 信息科學(xué)與工程學(xué)院 專 業(yè) 計算機(jī)科學(xué)與技術(shù) 學(xué) 號 指導(dǎo)教師 二〇一三年五月十五日 摘要 分支限界法是一種廣泛使用的狀態(tài)空間搜索算法，這種算法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式來搜索問題的狀態(tài)空間，在搜索過程中，利用剪枝來提高搜索效率，分支限界法與回溯法、 A*算法等常用于游戲中的“ 尋路 ” 過程。 面向?qū)ο?。所謂單機(jī)游戲指僅使用一臺計算機(jī)或者其它游戲平臺就可以獨(dú)立運(yùn)行的 電 子游戲 。連連看游戲規(guī)則簡單，在一個擺放了游戲牌的棋盤內(nèi)，只要將相同花色的兩個游戲牌用三根以內(nèi)的直線連在一起就可以消除，在規(guī)定的時間內(nèi)消除了棋盤內(nèi)的所有游戲牌，即可獲得游戲勝利，否則游戲失敗。 圖 傳統(tǒng)連連看游戲運(yùn)行界面 狀態(tài)空間搜索簡介 狀態(tài)是指在系統(tǒng)中決定系統(tǒng)狀態(tài)的最小數(shù)目的變量的有序集合。如對于有 n 種可選物品的 01 背包問題，其解空間由長度為 n 的 01 向量組成， 該解空間包含了對變量所有可能的 01 賦值。這樣， 問題空間與解空間的結(jié)構(gòu)、描述的模型十分一致，減少了軟件系統(tǒng)開發(fā)的復(fù)雜度，使系統(tǒng)易于理解和維護(hù)。 結(jié)論部分，總結(jié)開發(fā)出來的連連看游戲系統(tǒng)的特點(diǎn)，并論證面向?qū)ο蠓椒ê头种藿缢惴ㄋ枷朐谶B連看游戲開發(fā)的可行性，并分析了開發(fā)出的連連看游戲的優(yōu)勢和不足。系統(tǒng)由若干用例組成，系統(tǒng)的邊界定義了一個系統(tǒng)所具有功能。 游戲的用例圖 待開發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲系統(tǒng)，支持單人游戲，也支持在一臺機(jī)器上或者局域網(wǎng)不同的兩臺機(jī)器上最多有兩個玩家同時游戲，但這兩個玩家的性質(zhì)完全相同，因此處于系統(tǒng)邊界之外的參與者只有一個，就是玩家。 表 “進(jìn)行單人游戲 ” 用例的用例描述 名稱 描述 用例名稱 進(jìn)行單人游戲 執(zhí)行者 玩家 目的 在單價模式下進(jìn)行游戲 類型 基本的、主要的 過程描述 1．選擇 “ 游戲 ” 菜單中的 “ 開始單人游戲 ” 選項，啟動開始單人游戲。活動圖實(shí)際上也是一種流程圖，它描述活動的序列，即系統(tǒng)從一個活動到另一個活動的控制流，與流程圖不同的是，活動圖還可以描述系統(tǒng)的并發(fā)處理 [4,5]。玩家可隨時選擇開始單人游戲，在局域網(wǎng)雙人對戰(zhàn)游戲中，有且只有服務(wù)器端有選擇可以開始游戲的權(quán)利，而客服端只能等待游戲開始。顯然，軟件的運(yùn)行平臺對硬件的要求要低于開發(fā)平臺。因此在設(shè)計系統(tǒng)時，就免不了對交互進(jìn)行建模，并用交互圖展現(xiàn)出來。 本文設(shè)計的連連看局域網(wǎng)雙人對戰(zhàn)游戲，雖然不涉及 Web，也不涉及數(shù)據(jù)庫，但是也可以吸收 MVC 模式的特點(diǎn)，從某種程度上降低了程序的復(fù)雜度，使程序結(jié)構(gòu)更加直觀。玩家可隨時選擇開始單人游戲，在局域網(wǎng)雙人對戰(zhàn)游戲中，只有服務(wù)器端有選擇可以開始游戲，而客服端只 能等待游戲開始。建立類和對象模型是面向?qū)ο蠓治雠c設(shè)計方法的核心技術(shù)之一，也是面向?qū)ο蠹夹g(shù)的基本任務(wù)，是軟件開發(fā)的基礎(chǔ) [4]。 游戲的類關(guān)系圖 通過需求分析得到的用例模型以及活動圖，可以分析得出 游戲系統(tǒng)中所要涉及的一些基本的對象，如：游戲牌、棋盤區(qū)、控制系統(tǒng)、對話框（窗體）、繪圖系統(tǒng)和數(shù)據(jù)包等。其詳細(xì)定義的相關(guān)類圖如圖 所示。 圖 CServerSocket 類的設(shè)計 游戲主對話框類的設(shè)計 連連看局域網(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)定義。用它可以系統(tǒng)地搜索一個問題的所有解或任一解。 return。在分支限界法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)。 優(yōu)先隊列中規(guī)定的結(jié)點(diǎn)優(yōu)先級常用一個與該結(jié)點(diǎn)相關(guān)的數(shù)值 p 來表示。 } if(NextNode 非法 or NextNode 肯定不包含最優(yōu)解 ) { continue。 CLOSE 表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展的節(jié)點(diǎn)。 A*算法的基本搜索步驟如下： void AStar() { 初始化 OPEN← {S0}, CLOSED← Φ, g(S0)← 0, f(S0)← 0, preds0← NULL, found← false。 ik。 f(yi)← g(yi)+h(yi)。 OPEN← OPEN{x}。 假設(shè) f*(x)是從初始狀態(tài) S0出發(fā)，約束經(jīng)過狀態(tài) x 達(dá)到目標(biāo)狀態(tài) T 的最小代價，估值函數(shù) f(x)是對 f*(x)的估計值。 } } } A*算法簡介 回溯法和分支限界法在搜索過程中有一定的盲目性。用一個大根堆來實(shí)現(xiàn)最大優(yōu)先隊列，體現(xiàn)最大效益優(yōu)先的原則；用一個小根堆來實(shí)現(xiàn)最小優(yōu)先隊列，體現(xiàn)最小費(fèi)用優(yōu)先的原則。在這些孩子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的孩子結(jié)點(diǎn)被舍棄，其余孩子結(jié) 點(diǎn)被加入活結(jié)點(diǎn)表中。 } if(CurrentState 是非法狀態(tài) ) { return。 回溯法從開始結(jié)點(diǎn)（根結(jié)點(diǎn)） 出發(fā)，以深度優(yōu)先的方式搜索整個解空間。 圖 CCardGameDlg 類的設(shè)計 小結(jié) 本章使用面向?qū)ο蠓椒ㄡ槍⒁_發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲進(jìn)行了分析與設(shè)計，對游戲進(jìn)行 UML 建模，獲得了游戲的用例圖、活動圖、順序圖、部分游戲?qū)ο蟮臓顟B(tài)圖和類圖。 CClientSocket 主要針對 SetDraw()（設(shè)置繪圖器對象）、 .m_hWnd（游戲窗體句柄）、 SetControl()（設(shè)置控制器）、 m_pControl（控制器）、 m_pDraw（畫圖）、 GetConTrol()（獲取控制器）、 SetHWnd()（設(shè)置窗體句柄）、 OnReceive()（接收到客戶端套接字發(fā)送過來的數(shù)據(jù)時的處理函數(shù)）等進(jìn)行相應(yīng)定義。其詳細(xì)定義的相關(guān)類圖如圖 所示。類之間的關(guān)系有關(guān)聯(lián)、聚集、繼承、依賴、細(xì)化等。 單人游戲模式下的活動圖，如圖 所示。 待開發(fā)的連連看局域網(wǎng)對戰(zhàn)游戲程序，包含游戲模式選擇和游 戲設(shè)置兩個子系統(tǒng)。它通常用來描述一個用例的行為，顯示該用例中所涉及的對象和這些對象之間的消息傳遞情況。描述狀態(tài)圖的圖符元素除了圖符和遷移圖符外，還有起始狀態(tài)（用實(shí)心圓表示）、結(jié)束狀態(tài)（用一個圓中間套實(shí)心圓表示）、條件判定（用空心菱形表示）、發(fā)出信號（用一個一側(cè)為凸尖角的矩形表示）、接收信號（用一個一側(cè)為凹尖角的矩形表示）和并發(fā)（用一條粗短實(shí)線表示）等各種圖符元素 [4,5]。 單人游戲模式下的活動圖，如圖 所示。 用帶箭頭的實(shí)線表示各種活動狀態(tài)的先后順序，即遷移。 3．每隔 1 秒鐘，計時器自動減 1，如果時間耗盡，轉(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)，并罰時 4 秒鐘，轉(zhuǎn) 3； 9．將當(dāng)前選中的游戲牌指為選中狀態(tài)，消去這一對游戲牌，并加時 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)行局域網(wǎng)雙人對戰(zhàn) ” 用例這兩個用例進(jìn)行交互。用例模型的步驟包括 [4,5]：定義系統(tǒng)，尋找執(zhí)行者和用例，描述用例，定義用例之間的關(guān)系，最后確認(rèn)模型。建立用例模型的目的是為了尋找需求規(guī)約，需要通過開發(fā)者和客戶之間進(jìn)行多次交互完成。 面向?qū)ο缶幊?（ Object Oriented Programming， OOP， 面向?qū)ο蟪绦蛟O(shè)計 ）是一種計算機(jī)編程架構(gòu)。可以把解空間看作樹或者圖的形式，葉節(jié)點(diǎn)表示一個可能的解，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的任一路徑表示解空間的一個元素。狀態(tài)空間搜索就是通過在狀態(tài)空間中的初始狀態(tài)出發(fā)，按照一定的順序和條件對空間中的狀態(tài)進(jìn)行遍歷，最終找到目標(biāo)狀態(tài) [2]。適度游戲，不僅能增強(qiáng)思維能力，提高智力，鍛煉眼力，還能起到健腦益智的效果。而網(wǎng)絡(luò)游戲又稱 “ 在線游戲 ” ，簡稱 “ 網(wǎng)游 ” 。 Branch bound algorithm。 連連看游戲是一種簡單但不失趣味性的大眾游戲，具有一定的數(shù)學(xué)性和動態(tài)性，而將普通的傳統(tǒng)單機(jī)游戲擴(kuò)充為局域網(wǎng)上的多人對戰(zhàn)游戲，能使傳統(tǒng)游戲更具備對抗性和刺激性。 關(guān)鍵詞 ：狀態(tài)空間 。 Socket 目錄 摘要 .............................................................................................................................. I Abstract .................................................................................................... II 插圖索引 ................................................................................................. VI 附表索引 ................................................................................................ VII 第 1 章 概述 .............................................................................................................. 1 連連看游戲簡介 .............................................................................................. 1 狀態(tài)空間搜索簡介 .......................................................................................... 2 面向?qū)ο蠓椒ê喗?.......................................................................................... 3 論文內(nèi)容與結(jié)構(gòu) ......................................................................