【文章內(nèi)容簡介】 的消息并跳到消息處理代碼處，定義成員變量。執(zhí)行對話框數(shù)據(jù)檢驗(yàn)、創(chuàng)建新類時(shí)，會(huì)自動(dòng)加入方法和屬性 ， 建立整個(gè)類對象的框架模型 ，處理現(xiàn)有的類和類庫。 WizardBar(向?qū)Чぞ邨l ) WizardBar 是一個(gè)可停泊的工具條，用于快速訪問一些 Developer Studio 最實(shí)用的功能，比如 ClassWizard 或 ClassView 的一些功能。 WizardBar 還可以自動(dòng)跟蹤用戶 程序的上下文，例如，當(dāng)文本編輯器中的光標(biāo)從一個(gè)函數(shù)移動(dòng)到 另一個(gè)函數(shù)時(shí)， WizardBar 的顯示會(huì)自動(dòng)更新。 實(shí)用 WizardBar 還可以增加一個(gè)新類，建立一個(gè)新的函數(shù)或方法，跳到一個(gè)已存在的函數(shù)或方法。 WizardBar 使得處理類、成員和資源更加方便。 WizardBar 包含了 3 個(gè)相關(guān)的下拉列表框，分別是類 (Class)、過濾器 (Filter)和成員 (Member)。 Component Gallery(組件畫廊 ) Component Gallery 是一個(gè)組件庫，保存著可以共享和重用的代碼。這些代碼包括由 Visual C++自帶的組件和從用戶工程中增 加到 Gallery 中去的用戶自定義組件。 MFC 應(yīng)用程序框架 MFC 簡介： MFC[4](Microsoft Foundation Class)是由微軟公司編寫的一套專門用于 Windows 編程的 C++ 基礎(chǔ)類庫 ， VC++ 編程基本上都是圍繞著 MFC 類庫來進(jìn)行的。它封裝了 Windows API 的絕大多數(shù)功能，為用戶開發(fā) Windows 應(yīng)用程序建立了一個(gè)非常靈活的應(yīng)用程序框架。其中 CObject 是 MFC 類庫的根類。 6 MFC 類庫包括： (1)CCmdTarget 類：是 CObject 類的子類，它是 MFC 庫中所有具有消息映射屬性的類的公共基類。它的子類有 CWinThread 類， CWnd 類、 CDocument 類，從 CCndTarget 類派生的類能在程序運(yùn)行時(shí)動(dòng)態(tài)創(chuàng)建對象 ， 并處理命令消息。 (2)CWinThread 類：是 CCmdTarget 的子類。 CWinThread 是所有線程類的基類，封裝了應(yīng)用程序操作的多線程功能。應(yīng)用程序類 CWinApp 是 CWinThread 的子類，封裝了初始化、運(yùn)行、終止應(yīng)用程序 的代碼。 (3)CWnd 類：窗口類，是 CcmdTarget 類的子類，從 CWnd 派生的類可以擁有自己的窗口，并對它進(jìn)行控制。窗口框架類 CFrameWnd 和 CView 類是 CWnd 的子類，前者創(chuàng)建和維護(hù)窗口的邊框、菜單欄、工具欄、狀態(tài)欄，負(fù)責(zé)顯示和搜索用戶命令，后者負(fù)責(zé)為文檔提供一個(gè)或幾個(gè)視圖。視圖的作用是為修改、查詢文檔等任務(wù)提供人機(jī)交互的界面。 (4)文檔類 CDocument 類：是 CCmdTarget 類的子類，負(fù)責(zé)封裝和維護(hù)文檔。文檔包括應(yīng)用程序的工作成果或環(huán) 境設(shè)置數(shù)據(jù)等，可以是程序需要保存的任何內(nèi)容。 關(guān)鍵技術(shù)介紹 該游戲主要的功能模塊是最優(yōu)解搜索功能。在該功能中，通過分析比較，選擇了 A*算法來實(shí)現(xiàn)該功能。 A*算法 是一種常用的啟發(fā)式搜索算法 。 所謂啟發(fā)式搜索就是在搜索中要對每一個(gè)搜索的位置進(jìn)行評估，從中選擇最好、可能容易到達(dá)目標(biāo)的位置，再從這個(gè)位置向前進(jìn)行搜索，這樣就可以在搜索中省略大量無關(guān)的結(jié)點(diǎn)，提高了效率。其相對于廣度搜索 減少搜索的盲目性引，增加試探的準(zhǔn)確性 。 A*算法是 利用一個(gè)評估函數(shù) ， 對狀態(tài)空間中的搜索中的每一個(gè)搜索位置的價(jià)值進(jìn)行評估 ， 來決定每一次擴(kuò)展中 ， 哪一個(gè)是最有希望到達(dá)目標(biāo)的節(jié)點(diǎn)。然后 , 搜索就可能沿著某個(gè)被認(rèn)為是最有希望的邊緣區(qū)段向外擴(kuò)展 。 其核心思想是通過引入一個(gè)啟發(fā)式函數(shù) (或稱為評估函數(shù) )， 為了有利于回溯到早期路徑的搜索 ， 可以為評估函數(shù)增加一個(gè)深度因子 ， 如果能夠給定一個(gè)比較合適的評估函數(shù) ， 將會(huì)大大的減少搜索工作量。對于八數(shù)碼問題的求解 ， 可以用錯(cuò)位碼的個(gè)數(shù)作為狀態(tài)描述好壞的一個(gè)度量 g(n)： 即節(jié)點(diǎn)的錯(cuò)位碼個(gè)數(shù) (即和目標(biāo)節(jié)點(diǎn)比較 , 位置不正確的數(shù)字個(gè)數(shù) )。另外 ， 為了避免由于過分的優(yōu)化試探而進(jìn)入到無目的的漫游 ， 加上一個(gè)深度因子 h(n)： 即搜索中節(jié)點(diǎn) n 的深度。則評估函數(shù)為 f(n )=g(n)+h(n)： 表示從初始節(jié)點(diǎn)到節(jié)點(diǎn) n的一條最佳路徑的實(shí)際代價(jià) h(n)加上從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和 ， 最終可以找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑的代價(jià)。 7 第 3 章 游戲的系統(tǒng)分析 需求分析 當(dāng)前各種游戲軟件層出不窮。因?yàn)橛螒虻拈_發(fā)成本非常大，所以游戲的開發(fā)具有一定的風(fēng)險(xiǎn)性，但是一些小游戲的開發(fā)具有成本小，編寫簡單的優(yōu)勢，所以這些小游戲在游戲開發(fā)中也占有一席之地。在這類小游戲中 主要是 益智類游戲，它以游戲方法簡單的特點(diǎn)得到大家的 認(rèn)可。成為人們在工作之余不可或缺的好伙伴。針對真種情況我用 Visual C++編寫了 8 數(shù)碼這款小游戲。 8 數(shù)碼游戲是廣受歡迎的一種智力游戲，能夠鍛煉人的思維能力 ， 動(dòng)手 能力。 ， 功能描述 該數(shù)碼游戲的基本功能：對于這個(gè)具有移動(dòng)拼湊功能的游戲，其功能描述如下：玩家通過手動(dòng)設(shè)置數(shù)字的初始狀態(tài)和最終狀態(tài)，玩家主要是對設(shè)置的初始狀態(tài)進(jìn)行移動(dòng)，使其最終排列成為玩家設(shè)置的最終狀態(tài)排列，玩家也可以選擇機(jī)器功能讓電腦自動(dòng)進(jìn)行排列，并可以自動(dòng)演示其搜索過程，玩家還可以自己設(shè)置搜索的深度，一旦超過玩家設(shè)置的深度則算無 解。 操作特性分析 八數(shù)碼是在 3 3 方格盤上 ,放有八個(gè)數(shù)碼 ， 剩下一個(gè)位置為空 ， 每一空格其上下左右的數(shù)碼可移至空格。問題給定初始位置和目標(biāo)位置 ， 要求通過一系列的數(shù)碼移動(dòng) ， 將初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)。狀態(tài)轉(zhuǎn)換的規(guī)則：空格周圍的數(shù)移向空格 ， 我們可以看作是空格移動(dòng) ， 它最多可以有 4 個(gè)方向的移動(dòng) ， 即上、下、左、右。九宮重排問題的求解方法 ,就是從給定的初始狀態(tài)出發(fā) ， 不斷地空格上下左右的數(shù)碼移至空格 ， 將一個(gè)狀態(tài)轉(zhuǎn)化成其它狀態(tài) ,直到產(chǎn)生目標(biāo)狀態(tài)。 玩家可以選擇人工，自主進(jìn)行空格的移動(dòng)以達(dá)到最終狀態(tài)排列；也 可以選擇機(jī)器功能讓電腦自動(dòng)進(jìn)行排列 ，實(shí)現(xiàn)數(shù)字的最終狀態(tài)排列。 功能需求分析 通過分析，該游戲需要完成的功能有界面的設(shè)計(jì)、數(shù)字的移動(dòng)、最優(yōu)解的搜索。其中最主要模塊是實(shí)現(xiàn)數(shù)字移動(dòng)模塊和最優(yōu)解搜索模塊。 界面設(shè)計(jì)分析，該游戲可以由用戶實(shí)現(xiàn)輸入數(shù)據(jù)初始狀態(tài)和目標(biāo)狀態(tài) 、 選擇實(shí)現(xiàn)方式、移動(dòng)功能、選擇自動(dòng)演示、設(shè)置搜索深度的功能。所以，可以把這些功能劃分為區(qū)域，設(shè)計(jì)成按鈕的形式，通過鼠標(biāo)交互功能呢，實(shí)現(xiàn)用戶的各種功能操作。 數(shù)字移動(dòng)分析，通過分析空白滑塊的可移動(dòng)方向，設(shè)計(jì)程序。當(dāng)空白滑塊位 8 于中間時(shí)，其可以向任意方 向移動(dòng)；當(dāng)空白滑塊位于邊界時(shí)，需要根據(jù)其邊界的位置，進(jìn)行分析其可移動(dòng)的方向。 最優(yōu)解搜索分析，通過分析各種 搜索算法 [10]的特點(diǎn)，選擇合適的搜索算法，提高搜索效率。通過比較，該游戲選擇了 A*算法來實(shí)現(xiàn)該功能。 可行性分析 在本節(jié)中主要介紹 A*算法的可行性。 A*算法是一個(gè)很重要的啟發(fā)式搜索算法。如果一般圖搜索過程進(jìn)行如下限制 ,則它就成為 A*算法： (1) 把 OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù) f(x)= g(x)+h(x)的值從小到大進(jìn)行排序 ； (2) g(x)是對 g*(x)的估計(jì) ,g(x)0； (3) h(x)是 h*(x)的下界 ， 即對所有的 x 均有： h(x)≤ h*(x) 其中 ,g*(x)是從初始節(jié)點(diǎn)到節(jié)點(diǎn) x 的最小代價(jià) ， h*(x)是節(jié)點(diǎn) x 到目標(biāo)節(jié)點(diǎn)的最小代價(jià) ， 若有多個(gè)目標(biāo)節(jié)點(diǎn) ， 則為其中最小的一個(gè)。 一般來說 ， 對任意一個(gè)狀態(tài)空間圖 ,當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在時(shí) ，如果搜索算法能在有限步內(nèi)找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑 ， 并在此路徑上結(jié)束 ， 則稱該搜索算法是可納的。 A*算法是可納的 ， 即它能在有限步內(nèi)終止并找到最優(yōu)解。 我們分三步用以下三個(gè)定理來證明這一結(jié)論。 定理 1 對有限圖 ， 如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg 有路徑存在 ， 則算法 A*一定成功結(jié)束。 證明： 首先證明算法必定會(huì)結(jié)束。由于搜索圖為有限圖 ， 如果算法能找到解 ， 則會(huì)成功結(jié)束；如果算法找不到解 ， 則必然會(huì)由于 Open 表變空而結(jié)束。因此 ,A*算法必然會(huì)結(jié)束。 然后證明算法一定會(huì)成功結(jié)束 ， 由于至少存在一條由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑 ,設(shè)此路徑 S0= n0,n1 ,…,nk =Sg 算法開始時(shí) ， 節(jié)點(diǎn) n0 在 Open 表中 ， 而且路徑中任一節(jié)點(diǎn) ni 離開 Open 表后 ,其后繼節(jié)點(diǎn) ni+1 必然進(jìn)入 Open 表 ， 這樣 ， 在 Open 表變?yōu)榭罩?， 目標(biāo)節(jié)點(diǎn)必然出現(xiàn)在 Open 表中。因此 ,算法必定會(huì)成功結(jié)束。 引理 1： 對無限圖 ， 如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在 ， 且 A*算法不終止的話 ,則從 Open 表中選出的節(jié)點(diǎn)必將具有任意大的 f 值。 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 對無限圖 ,若從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) t 有路徑存在 ， 則 A*算法必然會(huì)結(jié)束。 證明： (反證法 )假設(shè) A*算法不結(jié)束 ， 又引理 1 知 Open 表中的節(jié)點(diǎn)有任意大的 f 值 ， 這與引理 2 的結(jié)論相矛盾 ， 因此 ,A*算法只能成功結(jié)束。 定理 3： A*算法是可采納的 ， 即若存在從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg 的路徑 ， 則 A*算法必能結(jié)束在最佳路徑上。 證明：證明過程分以下兩步進(jìn)行： 先證明 A*算法一定能夠終止在某個(gè)目標(biāo)節(jié)點(diǎn)上 。 由定理 1 和定理 2 可知 ， 無論是對有限圖還是無限圖 ， A*算法都能夠找到某個(gè)目標(biāo)節(jié)點(diǎn)而結(jié)束。 再證明 A*算法只能終止在最佳路徑上 (反證法 )。 假設(shè) A*算法未能終止在最佳路徑上 ， 而是終止在某個(gè)目標(biāo)節(jié)點(diǎn) t 處 ， 則有 f(t)=g(t)f*(S0) 但由引理 2 可知 ， 在 A*算法結(jié)束前 ,必有最佳路徑上的一個(gè)節(jié)點(diǎn) n’在 Open表中 ， 且有 f(n’) ≤ f*(S0)f(t), 這時(shí) ， A*算法一定會(huì)選擇 n’來擴(kuò)展 ,而不可能選擇 t， 從而也不會(huì)去測試目標(biāo)節(jié)點(diǎn) t， 這就與假設(shè) A*算法終止在 目標(biāo)節(jié)點(diǎn) t 相矛盾。因此 ， A*算法只能終止在最佳路徑上。 游戲特色分析 該游戲看起來有點(diǎn)類似拼圖游戲，該游戲與拼圖游戲都是基于回溯算法的基礎(chǔ)上設(shè)計(jì)。但該游戲的實(shí)現(xiàn)不同于拼圖游戲：該游戲是用戶輸入一些沒有規(guī)律數(shù)據(jù)，再由用戶輸入數(shù)據(jù)的最終排列狀態(tài)，選擇人工則由玩家自己進(jìn)行空白模塊移動(dòng)，而選擇機(jī)器則可以由機(jī)器自動(dòng)搜索最優(yōu)解；而拼圖游戲是把圖像分割，然后打亂圖像，再由玩家拼成原來的圖像。 10 第 4 章 游戲功能模塊設(shè)計(jì) 系統(tǒng)模塊設(shè)計(jì) 8 數(shù)碼游戲程序的整體功能模塊 [6]，里面包含數(shù)據(jù)輸入、功能選擇 、輸出模塊等。選擇模塊含人工和機(jī)器兩個(gè)選項(xiàng)，而人工和機(jī)器下各有自己的功能模塊。具體的模塊設(shè)計(jì)如圖 41 所示。 圖 41 8數(shù)碼游戲模塊圖 移動(dòng)模塊和鼠標(biāo)交互模塊流程圖設(shè)計(jì) 移動(dòng)模塊設(shè)計(jì) 8 數(shù)碼游戲選擇人工按鈕時(shí)，需要判斷空白模塊的移動(dòng)方向趨勢，如果可以則按玩家的選擇移動(dòng)空白模塊，如果不能則不允許移動(dòng)，并給出提示。流程圖如圖 42 所示。 輸入模塊 初始狀態(tài) 目標(biāo)狀態(tài) 輸出模塊 步數(shù)輸出 最優(yōu)解 八數(shù)碼游戲 選擇模塊 人工