【正文】 alse)。 resultnextstate=NULL。i3。 for(x=0。j++){ resultstate[i][j]=srcstate[i][j]。y3。 resultcurdistance=srccurdistance+1。} } 20 } if(tempy==2) return false。 return true。i++){ for(int j=0。x3。i7。 int temp[8]。為了保證算法的可行性，需要對不可達的 8 數(shù)碼問題進行過濾。顯然，后者的 h(n)不小于前者，因此本文中采用數(shù)碼 “ 不在位 ”的距離 和作為啟發(fā)函數(shù)。 另一方面， A*搜索算法是通過考察節(jié)點的代價值來決定 open 表的排序的，因此在表示當前狀態(tài)的 DATA 中還應(yīng)該有對當前節(jié)點代價值的描述。 算法設(shè)計 根據(jù)任務(wù)要求，本文采用 A*搜索算法 [12]。該游戲規(guī)則的說明位于主窗體界面的右側(cè) ， 如圖 47所示。 函數(shù)體對所有方塊元素進行了檢測，只有當該數(shù)字位置區(qū)域所容納的圖片方塊物件的 ID 與該區(qū)域下標數(shù)完全吻合，才證明這些方塊又返回源點位置，游戲勝利結(jié)束。當某一數(shù)字從一個位置移動去填補另一個位置的空缺時，其原先位置又變成了空缺區(qū)域了。只需要根據(jù)當前游戲一維數(shù)組的內(nèi)部數(shù)據(jù)，來對每一個數(shù)據(jù)進行繪制。選擇模塊含人工和機器兩個選項，而人工和機器下各有自己的功能模塊。 證明：證明過程分以下兩步進行： 先證明 A*算法一定能夠終止在某個目標節(jié)點上 。由于搜索圖為有限圖 ， 如果算法能找到解 ， 則會成功結(jié)束；如果算法找不到解 ， 則必然會由于 Open 表變空而結(jié)束。 可行性分析 在本節(jié)中主要介紹 A*算法的可行性。 功能需求分析 通過分析，該游戲需要完成的功能有界面的設(shè)計、數(shù)字的移動、最優(yōu)解的搜索。針對真種情況我用 Visual C++編寫了 8 數(shù)碼這款小游戲。 其核心思想是通過引入一個啟發(fā)式函數(shù) (或稱為評估函數(shù) )， 為了有利于回溯到早期路徑的搜索 ， 可以為評估函數(shù)增加一個深度因子 ， 如果能夠給定一個比較合適的評估函數(shù) ， 將會大大的減少搜索工作量。文檔包括應(yīng)用程序的工作成果或環(huán) 境設(shè)置數(shù)據(jù)等，可以是程序需要保存的任何內(nèi)容。它的子類有 CWinThread 類， CWnd 類、 CDocument 類，從 CCndTarget 類派生的類能在程序運行時動態(tài)創(chuàng)建對象 ， 并處理命令消息。 WizardBar 使得處理類、成員和資源更加方便。在開發(fā)程序時，可用 ClassWizard 建立程序所需要的類，包括消息處理和消息映射例程 (用于定位處理消息的代碼 )。 ClassView(類視圖 )：顯示項目中定義的 C++類，可以查看工程中定義的所有類，展開類還可以查看類的數(shù)據(jù)成員 、 成員函數(shù) 、 全局變量、函數(shù)和類型定義。通過 Developer Studio， 開發(fā)人員可以完成項目工程的創(chuàng)建、程序的編輯、修改、運行和調(diào)試等各種操作。 第三章：主要介紹了游戲的系統(tǒng)分析 ，包括：需求分析、功能分析、可行性分析等。本游戲在最優(yōu)解搜索部分通過在對各種算法的可行性和效率進行了比較，最終選擇 了 A*算法來實現(xiàn)該模塊的功能。當我們發(fā)現(xiàn)目標節(jié)點時 ， 可以同時找到從初始狀態(tài)到達目標狀態(tài)的一條最短路徑。用于搜索的方法 [13]主要有兩大類：一類是盲目搜索 ， 另一類是啟發(fā)式搜索。學(xué)習(xí)解決問題的方法及策略─玩 8 數(shù)碼游戲能學(xué)習(xí)推理思考能力 ， 因為嘗試不同的選擇 ， 到?jīng)Q定正確的一塊放下去，也就是經(jīng)過假設(shè) 、 判斷到選擇的過程 ， 能讓玩家學(xué)習(xí)運用邏輯來解決問題的方法。s main function modules of the design and implementation: to determine whether the solvability of the game, move the blank module, automatic presentation module, the search function to achieve the optimal solution, and mouse interaction the optimal solution which is mainly used to achieve A * shortest path algorithm. 【 Key words】 Digital Games MFC A * algorithm Shortest Path 1 第 1 章 緒 論 隨著世界經(jīng)濟的長足發(fā)展和計算機技術(shù)的日益成熟 ， 計算機被應(yīng)用到人類活動的各個領(lǐng)域，各種應(yīng)用軟件也相繼問世，這其中有相當一部分是游戲軟件。 III 基于 VC++的 8 數(shù)碼游戲設(shè)計與開發(fā) 摘 要 八數(shù)碼游戲是在 3 3方格盤上 ,放有八個數(shù)碼 ,剩下一個位置為空 ,每一空格其上下左右的數(shù)碼可移至空格。 本論文主要工作是該游戲的 主要的功能模塊的設(shè)計和實現(xiàn) ：判斷游戲是否有解，空白模塊移動，自動演示模塊，最優(yōu)解搜索功能的實現(xiàn)，及鼠標交互操作的功能。在各種操作系統(tǒng)中都附帶了一些小的游戲 ， 而這些游戲也成為電腦用戶軟件中不可或缺的一部分。 編譯本程序的目的一是對自己所學(xué)知識的鞏固 ， 二是希望可以給玩家?guī)砣碌母惺堋Ｋ?， 深度優(yōu)先搜索策略是不完備的。 所以，在八數(shù)碼游戲中，我選擇了啟發(fā)式搜索，即 A*算法來實現(xiàn) 最優(yōu)解的搜索功能。 在完成該游戲之后，還進行了部分的游戲數(shù)據(jù)測試，來判斷該游戲的功能是否正確的實現(xiàn)。 4 第 2 章 游戲開發(fā)工具 與關(guān)鍵技術(shù) 介紹 本章通過介紹 Visual C++和 MFC 的主要功能 和關(guān)鍵技術(shù)介紹，并 體現(xiàn)了這兩種工具在該游戲的開發(fā)過程中的優(yōu)勢。 在項目視圖中，每個視圖都有一個相應(yīng)的文件夾，包含了關(guān)于該項目的各種元素。 AppWizard 有為程序提供的功能性資源和代碼 ， 這樣就節(jié)省了用戶設(shè)計應(yīng)用程序框架的時間和精力 ， 用戶所要做的工作只是直接往框架中添加自己的處理代碼。 WizardBar(向?qū)Чぞ邨l ) WizardBar 是一個可停泊的工具條，用于快速訪問一些 Developer Studio 最實用的功能，比如 ClassWizard 或 ClassView 的一些功能。它封裝了 Windows API 的絕大多數(shù)功能，為用戶開發(fā) Windows 應(yīng)用程序建立了一個非常靈活的應(yīng)用程序框架。窗口框架類 CFrameWnd 和 CView 類是 CWnd 的子類，前者創(chuàng)建和維護窗口的邊框、菜單欄、工具欄、狀態(tài)欄，負責(zé)顯示和搜索用戶命令，后者負責(zé)為文檔提供一個或幾個視圖。其相對于廣度搜索 減少搜索的盲目性引，增加試探的準確性 。因為游戲的開發(fā)成本非常大，所以游戲的開發(fā)具有一定的風(fēng)險性，但是一些小游戲的開發(fā)具有成本小，編寫簡單的優(yōu)勢，所以這些小游戲在游戲開發(fā)中也占有一席之地。狀態(tài)轉(zhuǎn)換的規(guī)則：空格周圍的數(shù)移向空格 ， 我們可以看作是空格移動 ， 它最多可以有 4 個方向的移動 ， 即上、下、左、右。當空白滑塊位 8 于中間時，其可以向任意方 向移動；當空白滑塊位于邊界時，需要根據(jù)其邊界的位置，進行分析其可移動的方向。 我們分三步用以下三個定理來證明這一結(jié)論。 9 引理 2 在 A*算法終止前的任何時刻 ， Open 表中總存在節(jié)點 n’， 它是從初始節(jié)點S0 到目標節(jié)點的最佳路徑上的一個節(jié)點 ,且滿足 ： f(n’) ≤ f*(S0) 定理 2 對無限圖 ,若從初始節(jié)點 S0到目標節(jié)點 t 有路徑存在 ， 則 A*算法必然會結(jié)束。 游戲特色分析 該游戲看起來有點類似拼圖游戲，該游戲與拼圖游戲都是基于回溯算法的基礎(chǔ)上設(shè)計。 圖 43 鼠標左鍵流程圖 是 鼠標左鍵事件 結(jié)束 單擊移動功能中的方向鍵 判斷該空白塊是否可以移動 判斷是否到達邊界 移 動 是 否 結(jié) 束 空白模塊是否能移動 開 始 判斷移動方向趨勢 移動位置，修改數(shù)據(jù)狀態(tài) 12 詳細設(shè)計 詳細設(shè)計是對整個程序的整體設(shè)計 [2]，它包含窗體的設(shè)計、主窗體界面的設(shè)計、數(shù)字排列初始態(tài)和終態(tài)的設(shè)置、選擇功能及搜索過程的顯示等，以及本游戲最有特點的搜索最優(yōu)解和自動演示功能。 另外，該游戲還可以由玩家設(shè)置搜索深度，如果玩家輸入的數(shù)據(jù)初始態(tài)到達數(shù)據(jù)的目標態(tài)超過用戶設(shè)置的搜索深度，則按無解計算。 數(shù)據(jù)的檢測 前面實現(xiàn)的眾多功能都是圍繞著位置這一關(guān)鍵物件來運作的，而數(shù)字排序勝利狀態(tài)的檢測自然也不例外了。若有解則點擊自動演示按鈕進行演示，游戲?qū)⒆詣娱_始數(shù)字排列，并在搜索過程顯示的窗口中顯示數(shù)字移動過程。 為方便編程和表示，本文中 8 個格子內(nèi)的符號分別取 1— 8 的 8 個數(shù)字表示，空格用 0 表示。 表示問題的結(jié)構(gòu)體包括表示當前節(jié)點狀態(tài)的 DATA 和指向 open 表中下一個待擴展節(jié)點的指針 NEXT。 其中： h*(n)表示從當前節(jié)點 n 到目標節(jié)點 s_g 的最優(yōu)路徑的實際代價。 b) 判斷其是否已經(jīng)存在于 open 表中待擴展，如果出現(xiàn)過，并且新節(jié)點的代價值比其小，則應(yīng)將其從 open 表刪除，同時將新節(jié)點加入到 open 表；如果沒有出現(xiàn)過，則說明該節(jié)點為一個全新的節(jié)點，轉(zhuǎn) c。 具體代碼如下： int CJiuG::ComputeJO(JGState *jo) { int result=0。j++){ if(jostate[i][j]!=0){ temp[k]=jostate[i][j]。 return result。 } } } if(tempy==0) return false。 resultcurdistance=srccurdistance+1。y3。j++){ resultstate[i][j]=srcstate[i][j]。 for(x=0。i3。//設(shè)置前趨節(jié)點 21 resultnextstate=NULL。 tempy=y。 resultstate[tempx+1][tempy]=0。是記錄數(shù)字初始狀態(tài)的原始位置，及其目的位置，根據(jù)最短路徑算法，走一條最省時的路徑，然后連一條虛擬的線。 (false)。i++){ OnButtonShow()。 2．生成一個名為 close 的空表。 7．把 M 中不在 open 與 close 表里的點添加到 open 表里。//當前的距離，從初始節(jié)點開始 int state[3][3]。//Open 表 CPtrList CloseList。//左移 bool MoveRight(JGState *src,JGState *result)。//保存結(jié)果 25 JGState *curstep。//上一個節(jié)點的指針 struct JiuGongState *nextstate。 9．返回第 3 步。 起點 把 S 放入 open 表 Open 表是否為空表？ 是否有任何后繼節(jié)點為目標節(jié)點 把第一個節(jié)點 N 從 open 表移出。 } ()。 (false)。 自動演示功能的代碼部分如下： void CJiugongDlg::OnButtonAuto() {