【正文】 .............................................................. 29 測試總結(jié) ......................................................................................................... 30 第 7 章 總結(jié)和展望 .................................................................................................... 31 參考文獻 ...................................................................................................................... 32 致 謝 .............................................................................................. 錯誤 !未定義書簽。 課題背景及意義 背景說明 8 數(shù)碼游戲操作能培養(yǎng)手眼協(xié)調(diào)能力─游戲需要耐心的操作 ， 以及手眼協(xié)調(diào)能力 ， 只要一不協(xié)調(diào)就不能將數(shù)據(jù)塊放在正確的位置。廣度優(yōu)先搜索是從初始狀態(tài)一層一層向下找 ， 直到找到目標(biāo)為止。 第二章：主要是對游戲主要開發(fā)工具 VisualC++、 MFC 的概述 、使用的主要技術(shù)。 FileView(文件視圖 )：顯示所創(chuàng)建的工程 ， 展開文件夾可以查看工程中所包含的文件。 實用 WizardBar 還可以增加一個新類，建立一個新的函數(shù)或方法，跳到一個已存在的函數(shù)或方法。 (4)文檔類 CDocument 類：是 CCmdTarget 類的子類，負責(zé)封裝和維護文檔。成為人們在工作之余不可或缺的好伙伴。通過比較，該游戲選擇了 A*算法來實現(xiàn)該功能。 定理 3： A*算法是可采納的 ， 即若存在從初始節(jié)點 S0到目標(biāo)節(jié)點 Sg 的路徑 ， 則 A*算法必能結(jié)束在最佳路徑上。 圖 44 主窗體界面 圖像的繪制 游戲區(qū)域的視圖繪制 [6]較為簡單。當(dāng)所有數(shù)字方塊的排列順序與游戲開始設(shè)置的排列順序完全一致時，游戲就勝利結(jié)束了。 3 8 2 1 0 5 7 6 4 圖 48 初始狀態(tài) 圖 49 目標(biāo)狀態(tài) 1 2 3 8 0 4 7 5 6 則要求以圖 48 為初始狀態(tài)，通過交換 0 和 0 的上、下、左、右四個方位的數(shù)字（每次只能和其中 一個交換），達到圖 49 所示目標(biāo)狀態(tài)。 在 8 數(shù)碼問題中，常用的啟發(fā)函數(shù)為： “ 不在位 ” 數(shù)碼個數(shù)，或數(shù)碼 “ 不在位 ” 的距離和。 int k=0。 for(x=0。 resultnextstate=NULL。 resultstate[tempx][tempy+1]=0。j3。 for(int i=0。 自動演示功能的代碼部分如下： void CJiugongDlg::OnButtonAuto() { 22 // TODO: Add your control notification handler code here if(m_binitdown==false||m_bobjdown==false){ MessageBox(初始狀態(tài)或者目標(biāo)狀態(tài)沒有輸入 !!!,錯誤警告 )。 } ()。 9．返回第 3 步。//保存結(jié)果 25 JGState *curstep。//Open 表 CPtrList CloseList。 7．把 M 中不在 open 與 close 表里的點添加到 open 表里。i++){ OnButtonShow()。是記錄數(shù)字初始狀態(tài)的原始位置，及其目的位置，根據(jù)最短路徑算法，走一條最省時的路徑，然后連一條虛擬的線。 tempy=y。i3。j++){ resultstate[i][j]=srcstate[i][j]。 resultcurdistance=srccurdistance+1。 return result。 具體代碼如下： int CJiuG::ComputeJO(JGState *jo) { int result=0。 其中： h*(n)表示從當(dāng)前節(jié)點 n 到目標(biāo)節(jié)點 s_g 的最優(yōu)路徑的實際代價。 為方便編程和表示，本文中 8 個格子內(nèi)的符號分別取 1— 8 的 8 個數(shù)字表示，空格用 0 表示。 數(shù)據(jù)的檢測 前面實現(xiàn)的眾多功能都是圍繞著位置這一關(guān)鍵物件來運作的，而數(shù)字排序勝利狀態(tài)的檢測自然也不例外了。 圖 43 鼠標(biāo)左鍵流程圖 是 鼠標(biāo)左鍵事件 結(jié)束 單擊移動功能中的方向鍵 判斷該空白塊是否可以移動 判斷是否到達邊界 移 動 是 否 結(jié) 束 空白模塊是否能移動 開 始 判斷移動方向趨勢 移動位置，修改數(shù)據(jù)狀態(tài) 12 詳細設(shè)計 詳細設(shè)計是對整個程序的整體設(shè)計 [2]，它包含窗體的設(shè)計、主窗體界面的設(shè)計、數(shù)字排列初始態(tài)和終態(tài)的設(shè)置、選擇功能及搜索過程的顯示等，以及本游戲最有特點的搜索最優(yōu)解和自動演示功能。 9 引理 2 在 A*算法終止前的任何時刻 ， Open 表中總存在節(jié)點 n’， 它是從初始節(jié)點S0 到目標(biāo)節(jié)點的最佳路徑上的一個節(jié)點 ,且滿足 ： f(n’) ≤ f*(S0) 定理 2 對無限圖 ,若從初始節(jié)點 S0到目標(biāo)節(jié)點 t 有路徑存在 ， 則 A*算法必然會結(jié)束。當(dāng)空白滑塊位 8 于中間時，其可以向任意方 向移動；當(dāng)空白滑塊位于邊界時，需要根據(jù)其邊界的位置，進行分析其可移動的方向。因為游戲的開發(fā)成本非常大，所以游戲的開發(fā)具有一定的風(fēng)險性，但是一些小游戲的開發(fā)具有成本小，編寫簡單的優(yōu)勢，所以這些小游戲在游戲開發(fā)中也占有一席之地。窗口框架類 CFrameWnd 和 CView 類是 CWnd 的子類，前者創(chuàng)建和維護窗口的邊框、菜單欄、工具欄、狀態(tài)欄，負責(zé)顯示和搜索用戶命令，后者負責(zé)為文檔提供一個或幾個視圖。 WizardBar(向?qū)Чぞ邨l ) WizardBar 是一個可停泊的工具條，用于快速訪問一些 Developer Studio 最實用的功能，比如 ClassWizard 或 ClassView 的一些功能。 在項目視圖中，每個視圖都有一個相應(yīng)的文件夾，包含了關(guān)于該項目的各種元素。 在完成該游戲之后，還進行了部分的游戲數(shù)據(jù)測試，來判斷該游戲的功能是否正確的實現(xiàn)。所以 ， 深度優(yōu)先搜索策略是不完備的。在各種操作系統(tǒng)中都附帶了一些小的游戲 ， 而這些游戲也成為電腦用戶軟件中不可或缺的一部分。 III 基于 VC++的 8 數(shù)碼游戲設(shè)計與開發(fā) 摘 要 八數(shù)碼游戲是在 3 3方格盤上 ,放有八個數(shù)碼 ,剩下一個位置為空 ,每一空格其上下左右的數(shù)碼可移至空格。學(xué)習(xí)解決問題的方法及策略─玩 8 數(shù)碼游戲能學(xué)習(xí)推理思考能力 ， 因為嘗試不同的選擇 ， 到?jīng)Q定正確的一塊放下去，也就是經(jīng)過假設(shè) 、 判斷到選擇的過程 ， 能讓玩家學(xué)習(xí)運用邏輯來解決問題的方法。當(dāng)我們發(fā)現(xiàn)目標(biāo)節(jié)點時 ， 可以同時找到從初始狀態(tài)到達目標(biāo)狀態(tài)的一條最短路徑。 第三章：主要介紹了游戲的系統(tǒng)分析 ，包括：需求分析、功能分析、可行性分析等。 ClassView(類視圖 )：顯示項目中定義的 C++類，可以查看工程中定義的所有類，展開類還可以查看類的數(shù)據(jù)成員 、 成員函數(shù) 、 全局變量、函數(shù)和類型定義。 WizardBar 使得處理類、成員和資源更加方便。文檔包括應(yīng)用程序的工作成果或環(huán) 境設(shè)置數(shù)據(jù)等，可以是程序需要保存的任何內(nèi)容。針對真種情況我用 Visual C++編寫了 8 數(shù)碼這款小游戲。 可行性分析 在本節(jié)中主要介紹 A*算法的可行性。 證明：證明過程分以下兩步進行： 先證明 A*算法一定能夠終止在某個目標(biāo)節(jié)點上 。只需要根據(jù)當(dāng)前游戲一維數(shù)組的內(nèi)部數(shù)據(jù)，來對每一個數(shù)據(jù)進行繪制。 函數(shù)體對所有方塊元素進行了檢測，只有當(dāng)該數(shù)字位置區(qū)域所容納的圖片方塊物件的 ID 與該區(qū)域下標(biāo)數(shù)完全吻合，才證明這些方塊又返回源點位置，游戲勝利結(jié)束。 算法設(shè)計 根據(jù)任務(wù)要求，本文采用 A*搜索算法 [12]。顯然，后者的 h(n)不小于前者，因此本文中采用數(shù)碼 “ 不在位 ”的距離 和作為啟發(fā)函數(shù)。 int temp[8]。x3。 return true。 resultcurdistance=srccurdistance+1。j++){ resultstate[i][j]=srcstate[i][j]。i3。 (false)。 ()。 算法的具體實現(xiàn) 九宮問題的求解方法就是交換空格 (0)位置，直至到達目標(biāo)位置為止。 public: int m_ndepth。//當(dāng)前狀態(tài) CPtrList OpenList。把 M添加到 G 中，并讓他們成為 n 的后繼。i=()。 自動演示的原理是：此功能是根據(jù)圖的寬度優(yōu)先算法實現(xiàn)的。y++){ if(srcstate[x][y]==0){ tempx=x。 for(int i=0。j3。 resultstate[tempx][tempy1] = 0。 } } result=result%2。 判斷有無解 ，通過 返回 0 為偶，返回 1 為奇 .， 判斷是否有路徑。 (2)啟發(fā)函數(shù)的設(shè)計 根據(jù) A*算法的定義，啟發(fā)函數(shù)應(yīng)滿足： h(n)≤ h*(n)。開始時，規(guī)則給定一個初始狀態(tài)和一個目標(biāo)狀態(tài)，并要求被試者對棋 格內(nèi)的符號經(jīng)過若干次移動由初始狀態(tài)達到目標(biāo)狀態(tài)，這個過程中只有空格附近的符號可以朝空格的方向移動，且每次只能移動一個符號。并且在作真正的位置移動 前，需判斷其是否到了邊界而不能移動，當(dāng)檢測到?jīng)]有到達邊界時才開始作真正的移動操作。 輸入模塊 初始狀態(tài) 目標(biāo)狀態(tài) 輸出模塊 步數(shù)輸出 最優(yōu)解 八數(shù)碼游戲 選擇模塊 人工 機器 自動演示 數(shù)字移動 自動演示 顯示走步 11 圖 42 邊界判斷流程圖 鼠標(biāo)交互設(shè)計 鼠標(biāo)左 鍵單擊事件，鼠標(biāo)左鍵事件 [7]是點擊可移動的數(shù)據(jù)塊，使得數(shù)據(jù)塊可進行移動，如果達到邊界，則不可移動；反之，則可以繼續(xù)移動，如圖 43所示。 引理 1： 對無限圖 ， 如果從初始節(jié)點 S0到目標(biāo)節(jié)點 Sg有路徑存在 ， 且 A*算法不終止的話 ,則從 Open 表中選出的節(jié)點必將具有任意大的 f 值。 數(shù)字移動分析，通過分析空白滑塊的可移動方向，設(shè)計程序。 7 第 3 章 游戲的系統(tǒng)分析 需求分析 當(dāng)前各種游戲軟件層出不窮。 (3)CWnd 類：窗口類，是 CcmdTarget 類的子類，從 CWnd 派生的類可以擁有自己的窗口，并對它進行控制。執(zhí)行對話框數(shù)據(jù)檢驗、創(chuàng)建新類時，會自動加入方法和屬性 ， 建立整個類對象的框架模型 ，處理現(xiàn)有的類和類庫。 項目工作區(qū)底部有一組項目視圖切換選項卡 (包括 3 種視圖 )，用于從不同的角度查看項目中包含的工