【正文】 的功能。 編譯本程序的目的一是對(duì)自己所學(xué)知識(shí)的鞏固 ， 二是希望可以給玩家?guī)?lái)全新的感受。盲目搜索是指在不具有對(duì)待定問(wèn)題的任何有關(guān)信息的條件下 ， 按固定的步驟進(jìn)行的搜索 ， 如深度優(yōu)先搜索和廣度優(yōu)先搜索；啟發(fā)式搜索是指在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息 ， 這些信息可以指導(dǎo)搜索朝著最有希望的方向前進(jìn) ， 加速問(wèn)題的求解過(guò)程 ， 并找到最優(yōu)解 ， 如 A* 算法。所以 ， 深度優(yōu)先搜索策略是不完備的。因此 ， 這種策略是完備的。 所以，在八數(shù)碼游戲中，我選擇了啟發(fā)式搜索，即 A*算法來(lái)實(shí)現(xiàn) 最優(yōu)解的搜索功能。 簡(jiǎn)單介紹了該游戲開(kāi)發(fā)工具 Visual C++和 MFC，選擇這兩種開(kāi)發(fā)工具簡(jiǎn)化了游戲的界面的設(shè)計(jì)與實(shí)現(xiàn)。 在完成該游戲之后，還進(jìn)行了部分的游戲數(shù)據(jù)測(cè)試，來(lái)判斷該游戲的功能是否正確的實(shí)現(xiàn)。 第 四 章：主要是對(duì)游戲進(jìn)行設(shè)計(jì)，包括框架搭建、算法設(shè)計(jì)及分析。 4 第 2 章 游戲開(kāi)發(fā)工具 與關(guān)鍵技術(shù) 介紹 本章通過(guò)介紹 Visual C++和 MFC 的主要功能 和關(guān)鍵技術(shù)介紹，并 體現(xiàn)了這兩種工具在該游戲的開(kāi)發(fā)過(guò)程中的優(yōu)勢(shì)。 Developer Studio 采用標(biāo)準(zhǔn)的多窗口用戶界面，提供了大量實(shí)用工具以支持可視化編程 的特性，包括項(xiàng)目工作區(qū)、 AppWizard(應(yīng)用程序向?qū)?)、 ClassWizard(類向?qū)?)、 WizardBar(向?qū)Чぞ邨l )、Component Gallery(組件畫廊 )等。 在項(xiàng)目視圖中，每個(gè)視圖都有一個(gè)相應(yīng)的文件夾，包含了關(guān)于該項(xiàng)目的各種元素。 RourceView(資源視圖 )：顯示項(xiàng)目中所包含的資源文件 ， 展開(kāi)文件夾可顯示所有的資源類型。 AppWizard 有為程序提供的功能性資源和代碼 ， 這樣就節(jié)省了用戶設(shè)計(jì)應(yīng)用程序框架的時(shí)間和精力 ， 用戶所要做的工作只是直接往框架中添加自己的處理代碼。使用 ClassWizard，可以將成員函數(shù)或變量加入到一個(gè)類中，或修改已經(jīng)存在的函數(shù)和變量。 WizardBar(向?qū)Чぞ邨l ) WizardBar 是一個(gè)可停泊的工具條，用于快速訪問(wèn)一些 Developer Studio 最實(shí)用的功能，比如 ClassWizard 或 ClassView 的一些功能。 WizardBar 包含了 3 個(gè)相關(guān)的下拉列表框，分別是類 (Class)、過(guò)濾器 (Filter)和成員 (Member)。它封裝了 Windows API 的絕大多數(shù)功能，為用戶開(kāi)發(fā) Windows 應(yīng)用程序建立了一個(gè)非常靈活的應(yīng)用程序框架。 (2)CWinThread 類：是 CCmdTarget 的子類。窗口框架類 CFrameWnd 和 CView 類是 CWnd 的子類，前者創(chuàng)建和維護(hù)窗口的邊框、菜單欄、工具欄、狀態(tài)欄，負(fù)責(zé)顯示和搜索用戶命令，后者負(fù)責(zé)為文檔提供一個(gè)或幾個(gè)視圖。 關(guān)鍵技術(shù)介紹 該游戲主要的功能模塊是最優(yōu)解搜索功能。其相對(duì)于廣度搜索 減少搜索的盲目性引，增加試探的準(zhǔn)確性 。對(duì)于八數(shù)碼問(wèn)題的求解 ， 可以用錯(cuò)位碼的個(gè)數(shù)作為狀態(tài)描述好壞的一個(gè)度量 g(n)： 即節(jié)點(diǎn)的錯(cuò)位碼個(gè)數(shù) (即和目標(biāo)節(jié)點(diǎn)比較 , 位置不正確的數(shù)字個(gè)數(shù) )。因?yàn)橛螒虻拈_(kāi)發(fā)成本非常大，所以游戲的開(kāi)發(fā)具有一定的風(fēng)險(xiǎn)性，但是一些小游戲的開(kāi)發(fā)具有成本小，編寫簡(jiǎn)單的優(yōu)勢(shì)，所以這些小游戲在游戲開(kāi)發(fā)中也占有一席之地。 8 數(shù)碼游戲是廣受歡迎的一種智力游戲，能夠鍛煉人的思維能力 ， 動(dòng)手 能力。狀態(tài)轉(zhuǎn)換的規(guī)則：空格周圍的數(shù)移向空格 ， 我們可以看作是空格移動(dòng) ， 它最多可以有 4 個(gè)方向的移動(dòng) ， 即上、下、左、右。其中最主要模塊是實(shí)現(xiàn)數(shù)字移動(dòng)模塊和最優(yōu)解搜索模塊。當(dāng)空白滑塊位 8 于中間時(shí)，其可以向任意方 向移動(dòng)；當(dāng)空白滑塊位于邊界時(shí)，需要根據(jù)其邊界的位置，進(jìn)行分析其可移動(dòng)的方向。 A*算法是一個(gè)很重要的啟發(fā)式搜索算法。 我們分三步用以下三個(gè)定理來(lái)證明這一結(jié)論。因此 ,A*算法必然會(huì)結(jié)束。 9 引理 2 在 A*算法終止前的任何時(shí)刻 ， Open 表中總存在節(jié)點(diǎn) n’， 它是從初始節(jié)點(diǎn)S0 到目標(biāo)節(jié)點(diǎn)的最佳路徑上的一個(gè)節(jié)點(diǎn) ,且滿足 ： f(n’) ≤ f*(S0) 定理 2 對(duì)無(wú)限圖 ,若從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) t 有路徑存在 ， 則 A*算法必然會(huì)結(jié)束。 由定理 1 和定理 2 可知 ， 無(wú)論是對(duì)有限圖還是無(wú)限圖 ， A*算法都能夠找到某個(gè)目標(biāo)節(jié)點(diǎn)而結(jié)束。 游戲特色分析 該游戲看起來(lái)有點(diǎn)類似拼圖游戲，該游戲與拼圖游戲都是基于回溯算法的基礎(chǔ)上設(shè)計(jì)。具體的模塊設(shè)計(jì)如圖 41 所示。 圖 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)演示功能。先載入一個(gè)內(nèi)存位圖，再?gòu)脑匆晥D像位圖中選擇適當(dāng)?shù)膮^(qū)域?qū)⑵淇截惖絻?nèi)存位圖中，當(dāng)所有這些圖像方塊都繪制到內(nèi)存位圖后，再一次性地將整體圖像從內(nèi)存位圖拷貝到屏幕去。 另外，該游戲還可以由玩家設(shè)置搜索深度，如果玩家輸入的數(shù)據(jù)初始態(tài)到達(dá)數(shù)據(jù)的目標(biāo)態(tài)超過(guò)用戶設(shè)置的搜索深度，則按無(wú)解計(jì)算。 空白模塊的移動(dòng)是通過(guò)鼠標(biāo)左鍵移動(dòng)。 數(shù)據(jù)的檢測(cè) 前面實(shí)現(xiàn)的眾多功能都是圍繞著位置這一關(guān)鍵物件來(lái)運(yùn)作的，而數(shù)字排序勝利狀態(tài)的檢測(cè)自然也不例外了。 自動(dòng)演示 自動(dòng)演示是由 游戲自動(dòng)完成的。若有解則點(diǎn)擊自動(dòng)演示按鈕進(jìn)行演示，游戲?qū)⒆詣?dòng)開(kāi)始數(shù)字排列，并在搜索過(guò)程顯示的窗口中顯示數(shù)字移動(dòng)過(guò)程。 15 圖 47 游戲規(guī)則 算法分析 問(wèn)題描述 8 數(shù)碼問(wèn)題又稱 9 宮問(wèn)題，與游戲 “ 華容道 ” 類似。 為方便編程和表示，本文中 8 個(gè)格子內(nèi)的符號(hào)分別取 1— 8 的 8 個(gè)數(shù)字表示，空格用 0 表示。但要在計(jì)算機(jī)上通過(guò)編程解決該問(wèn)題，還應(yīng)當(dāng)解決該問(wèn)題在計(jì)算機(jī)上表示的方式，并設(shè)計(jì)合適的啟發(fā)函數(shù)，以提高搜索效率。 表示問(wèn)題的結(jié)構(gòu)體包括表示當(dāng)前節(jié)點(diǎn)狀態(tài)的 DATA 和指向 open 表中下一個(gè)待擴(kuò)展節(jié)點(diǎn)的指針 NEXT。 根據(jù) A*算法的定義，當(dāng)前節(jié)點(diǎn)的代價(jià)值由估價(jià)函數(shù)給出，即： f(n)=ｇ (n)+h(n) 其中： g(x)是從初始節(jié)點(diǎn)到節(jié)點(diǎn) x 的最小代價(jià)； h(n)是啟發(fā)函數(shù)。 其中： h*(n)表示從當(dāng)前節(jié)點(diǎn) n 到目標(biāo)節(jié)點(diǎn) s_g 的最優(yōu)路徑的實(shí)際代價(jià)。 (3)規(guī)則庫(kù)設(shè)計(jì) 0 在某一位置時(shí)，能選擇向左、向右、向上、向下移動(dòng)中的哪幾種策略進(jìn)行移動(dòng)，主要是由當(dāng)前 0 所處位置（更具體地說(shuō)是當(dāng)前位置的行列號(hào)）和其祖父節(jié)點(diǎn)（為提高搜索效率，新擴(kuò)展的節(jié)點(diǎn)應(yīng)當(dāng)至少不為其祖父節(jié)點(diǎn)）所決定的。 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。以往的算法都以未找到解決方案且 open 表為空來(lái)作為當(dāng)前給定的初始與終結(jié)狀態(tài)互不可達(dá)的判斷依據(jù)。 具體代碼如下： int CJiuG::ComputeJO(JGState *jo) { int result=0。 //除去 0，將其余 8 個(gè)數(shù)依次加入到數(shù)組中 for(i=0。j++){ if(jostate[i][j]!=0){ temp[k]=jostate[i][j]。i++){ for(j=i+1。 return result。x++){ for(y=0。 } } } if(tempy==0) return false。j3。 resultcurdistance=srccurdistance+1。 } bool CJiuG::MoveRight(JGState *src,JGState *result) //右移 { int x,y,tempx,tempy。y3。 for(int i=0。j++){ resultstate[i][j]=srcstate[i][j]。 resultprestate=src。 for(x=0。y++){ if(srcstate[x][y]==0){ tempx=x。i3。 } } resultstate[tempx][tempy]=srcstate[tempx1][tempy]。//設(shè)置前趨節(jié)點(diǎn) 21 resultnextstate=NULL。x3。 tempy=y。i++){ for(int j=0。 resultstate[tempx+1][tempy]=0。 return true。是記錄數(shù)字初始狀態(tài)的原始位置，及其目的位置，根據(jù)最短路徑算法，走一條最省時(shí)的路徑，然后連一條虛擬的線。 (false)。 (false)。 m_nstep=0。i++){ OnButtonShow()。 } 路徑搜索的實(shí)現(xiàn) 最后介紹一下搜索函數(shù) [10]的原理，首先得到源數(shù)組，將其轉(zhuǎn)換成 WORD 型，與目標(biāo)比較，如果相同完成，不同就交換一下數(shù)據(jù)和空格位置，加入二叉樹，搜索下一個(gè)結(jié)果，直到?jīng)]有步可走了，在搜索剛剛搜索到的位置的子位置，這樣直到找到目標(biāo)結(jié)果為止，該程序的實(shí)現(xiàn)在函數(shù) bool CJiuG::Search()中 ,其原理圖如圖41 所示 。 2．生成一個(gè)名為 close 的空表。 成功 失敗 是 否 是 否 24 4．選擇 open 上的第一個(gè)結(jié)點(diǎn)，把它添加到 close 里并命名為 n，且從 open中刪除。 7．把 M 中不在 open 與 close 表里的點(diǎn)添加到 open 表里。 要想得到最優(yōu) 解和較高的搜索效率 的就需要使用 A*算法 搜索，九宮的所以排列有 9！種，也就是 362880 種排法，數(shù)據(jù)量是非常大的，我使用的 A*搜索， 相對(duì)于廣度優(yōu)先算法可以減少 很多 節(jié)點(diǎn)占用 的內(nèi)存， 提高了搜索效率 。//當(dāng)前的距離，從初始節(jié)點(diǎn)開(kāi)始 int state[3][3]。//定義九宮結(jié)構(gòu) class CJiuG { public: JGState StateInit。//Open 表 CPtrList CloseList。//搜索深度 int ComputeJO(JGState *jo)。//左移 bool MoveRight(JGState *src,JGState *result)。 virtual ~CJiuG()。//保存結(jié)果 25 JGState *curstep。//目標(biāo)狀態(tài) JGState StateCur。//上一個(gè)節(jié)點(diǎn)的指針 struct JiuGongState *nextstate。但是 ， 對(duì)于這種搜索方式 ， 使用正確的評(píng)估函數(shù)是相當(dāng)重要的 ， 評(píng)估函數(shù)選擇的正確與否與搜索的效率直接相關(guān)。 9．返回第 3 步。 6．把 n 結(jié)點(diǎn)擴(kuò)展，生成其后續(xù)狀態(tài)集 M，注意 M 中不能有 n 的祖先。 起點(diǎn) 把 S 放入 open 表 Open 表是否為空表？ 是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn) 把第一個(gè)節(jié)點(diǎn) N 從 open 表移出。 A*算法在人工智能中是基于 A 算法的一種典型的啟發(fā)式搜索，主要是對(duì)估價(jià)函數(shù)加以特別的定義和描述時(shí)，從而得到一種具有較強(qiáng)的啟發(fā)能力