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