【導(dǎo)讀】基于VC++的8數(shù)碼游戲開發(fā)

　　

【正文】 (j=0。j3。j++){ if(jostate[i][j]!=0){ temp[k]=jostate[i][j]。 k++。 } } } //判斷奇偶性 for(i=0。i7。i++){ for(j=i+1。j8。j++){ if(temp[i]temp[j]) result++。 } } result=result%2。 return result。 19 } 移動(dòng)模塊的具體實(shí)現(xiàn) 空格移動(dòng) [16]的代碼比較簡單，只要計(jì)算是否會(huì)移動(dòng)到框外面就可以了，并在移動(dòng)的時(shí)候順便計(jì)算一下是不是已經(jīng)是目標(biāo)結(jié)果，這是用來給用戶手工移動(dòng)是給與提示用的，代碼： bool CJiuG::MoveLeft(JGState *src,JGState *result) //左移 { int x,y,tempx,tempy。 for(x=0。x3。x++){ for(y=0。y3。y++){ if(srcstate[x][y]==0){ tempx=x。 tempy=y。 } } } if(tempy==0) return false。 for(int i=0。i3。i++){ for(int j=0。j3。j++){ resultstate[i][j]=srcstate[i][j]。} } resultstate[tempx][tempy] = srcstate[tempx][tempy1]。 resultstate[tempx][tempy1] = 0。 resultcurdistance=srccurdistance+1。 resultprestate=src。 resultnextstate=NULL。 return true。 } bool CJiuG::MoveRight(JGState *src,JGState *result) //右移 { int x,y,tempx,tempy。 for(x=0。x3。x++){ for(y=0。y3。y++){ if(srcstate[x][y]==0){ tempx=x。 tempy=y。} } 20 } if(tempy==2) return false。 for(int i=0。i3。i++){ for(int j=0。j3。j++){ resultstate[i][j]=srcstate[i][j]。 } } resultstate[tempx][tempy]=srcstate[tempx][tempy+1]。 resultstate[tempx][tempy+1]=0。 resultcurdistance=srccurdistance+1。 resultprestate=src。 resultnextstate=NULL。 return true。 } bool CJiuG::MoveUp(JGState *src,JGState *result) //上移，上面的左移，右移，下面的下移，結(jié)構(gòu)一樣 { int x,y,tempx,tempy。 for(x=0。x3。x++) //尋找空格位置 { for(y=0。y3。y++){ if(srcstate[x][y]==0){ tempx=x。 tempy=y。 } } } if(tempx==0) //判斷是否可移 return false。 for(int i=0。i3。i++){ for(int j=0。j3。j++){ resultstate[i][j]=srcstate[i][j]。 } } resultstate[tempx][tempy]=srcstate[tempx1][tempy]。 resultstate[tempx1][tempy]=0。 resultcurdistance=srccurdistance+1。//深度加一 resultprestate=src。//設(shè)置前趨節(jié)點(diǎn) 21 resultnextstate=NULL。 return true。 } bool CJiuG::MoveDown(JGState *src,JGState *result) //下移 { int x,y,tempx,tempy。 for(x=0。x3。x++){ for(y=0。y3。y++){ if(srcstate[x][y]==0){ tempx=x。 tempy=y。 } } } if(tempx==2) return false。 for(int i=0。i3。i++){ for(int j=0。j3。j++){ resultstate[i][j]=srcstate[i][j]。 } } resultstate[tempx][tempy]=resultstate[tempx+1][tempy]。 resultstate[tempx+1][tempy]=0。 resultcurdistance=srccurdistance+1。 resultprestate=src。 resultnextstate=NULL。 return true。 } 自動(dòng)演示模塊的具體實(shí)現(xiàn) 自動(dòng)演示是由系統(tǒng)自動(dòng)完成的。玩家在能力不足時(shí)或想知道怎么能完成時(shí)，點(diǎn)擊菜單中的自動(dòng)演示，系統(tǒng)將自動(dòng)完成數(shù)字排序。 自動(dòng)演示的原理是：此功能是根據(jù)圖的寬度優(yōu)先算法實(shí)現(xiàn)的。是記錄數(shù)字初始狀態(tài)的原始位置，及其目的位置，根據(jù)最短路徑算法，走一條最省時(shí)的路徑，然后連一條虛擬的線。當(dāng)玩家點(diǎn)擊此項(xiàng)時(shí)，系統(tǒng)將自動(dòng)開始演示。 自動(dòng)演示功能的代碼部分如下： 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)沒有輸入 !!!,錯(cuò)誤警告 )。 (false)。 (false)。 return。 } (false)。 (false)。 (false)。 (false)。 (false)。 (false)。 m_nstep=0。 if(()==0){ MessageBox(無解或還沒有搜索 ,警告 )。 } for(int i=0。i=()。i++){ OnButtonShow()。 Sleep(1000)。 } ()。 ()。 } 路徑搜索的實(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 所示 。 23 圖 51 路徑搜索流程圖 算法描述與實(shí)現(xiàn) 算法描述 該游戲的最優(yōu)解搜索功能主要使用了 A*算法 [11]。 A*算法在人工智能中是基于 A 算法的一種典型的啟發(fā)式搜索，主要是對(duì)估價(jià)函數(shù)加以特別的定義和描述時(shí)，從而得到一種具有較強(qiáng)的啟發(fā)能力的有序搜索法 . 同時(shí)， A*算法也是一種最好優(yōu)先的算法 . 只不過要加上一些約束條件罷了 . 由于在一些問題求解時(shí)，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問題， A*就是解決此類問題 的 . 其中 A*算法的流程描述如下： 1．首先生成一個(gè)搜索的圖 G， 這個(gè)圖開始只有初始狀態(tài) n0。生成一個(gè)叫 open的表 ， 把 n0 添加到這個(gè)表里。 2．生成一個(gè)名為 close 的空表。 3．如果 open 為空 ， 則失敗退出。 起點(diǎn) 把 S 放入 open 表 Open 表是否為空表？ 是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn) 把第一個(gè)節(jié)點(diǎn) N 從 open 表移出。并把他放入 closed 表中 擴(kuò)展 N，把它的后繼節(jié)點(diǎn)放入 open表的末端，提供返回到 N 的指針。 成功 失敗 是 否 是 否 24 4．選擇 open 上的第一個(gè)結(jié)點(diǎn)，把它添加到 close 里并命名為 n，且從 open中刪除。 5．如果 n 是終態(tài)，那么問題得到解退出，否則到第 7 步。 6．把 n 結(jié)點(diǎn)擴(kuò)展，生成其后續(xù)狀態(tài)集 M，注意 M 中不能有 n 的祖先。把 M添加到 G 中，并讓他們成為 n 的后繼。 7．把 M 中不在 open 與 close 表里的點(diǎn)添加到 open 表里。 8．在 open 表里按啟發(fā)函數(shù)的大小重排 open 表。 9．返回第 3 步。 算法的具體實(shí)現(xiàn) 九宮問題的求解方法就是交換空格 (0)位置，直至到達(dá)目標(biāo)位置為止。 要想得到最優(yōu) 解和較高的搜索效率 的就需要使用 A*算法 搜索，九宮的所以排列有 9！種，也就是 362880 種排法，數(shù)據(jù)量是非常大的，我使用的 A*搜索， 相對(duì)于廣度優(yōu)先算法可以減少 很多 節(jié)點(diǎn)占用 的內(nèi)存， 提高了搜索效率 。 A*算法屬于 啟發(fā)式搜索 ，其 的優(yōu)越性 在于 ： 一方面 ， 當(dāng)發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí) ，可以同時(shí)找到從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的一條最短路徑 ； 另一方面 ， 由于搜索不是盲目的 ， 因此不需要擴(kuò)展每一層的所有節(jié)點(diǎn) ， 只需要擴(kuò)展最有希望到達(dá)目標(biāo)的節(jié)點(diǎn)即可。但是 ， 對(duì)于這種搜索方式 ， 使用正確的評(píng)估函數(shù)是相當(dāng)重要的 ， 評(píng)估函數(shù)選擇的正確與否與搜索的效率直接相關(guān)。 A*算法的具體 類結(jié)構(gòu)如下： typedef struct JiuGongState{ int curdistance。//當(dāng)前的距離，從初始節(jié)點(diǎn)開始 int state[3][3]。 struct JiuGongState *prestate。//上一個(gè)節(jié)點(diǎn)的指針 struct JiuGongState *nextstate。//下一個(gè)節(jié)點(diǎn)的指針 }JGState。//定義九宮結(jié)構(gòu) class CJiuG { public: JGState StateInit。//初始狀態(tài) JGState StateObj。//目標(biāo)狀態(tài) JGState StateCur。//當(dāng)前狀態(tài) CPtrList OpenList。//Open 表 CPtrList CloseList。//Close 表 CPtrList ResultList。//保存結(jié)果 25 JGState *curstep。 public: int m_ndepth。//搜索深度 int ComputeJO(JGState *jo)。//計(jì)算狀態(tài)的奇偶性 CJiuG()。 virtual ~CJiuG()。 bool MoveLeft(JGState *src,JGState *result)。//左移 bool MoveRight(JGState *src,JGState *result)。//右移 bool MoveUp(JGState *