基于vc的8數碼游戲設計與開發畢業論文-資料下載頁

【導讀】基于VC++的8數碼游戲開發

　　

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