【正文】 訪問操作權(quán)限 創(chuàng)建用于中介的內(nèi)存設(shè)備環(huán)境以及與其其關(guān)聯(lián)的內(nèi)存位圖 在內(nèi)存位圖中進行數(shù)字的拼湊繪制 14 移動方向，進行移動處理。 空白模塊的移動是通過鼠標左鍵移動。 數(shù)據(jù)的移動 對于空白方塊的移動，將用如下方法 ： 在原始初始化好的地圖數(shù)據(jù)的基礎(chǔ)上，先將分割后的數(shù)據(jù)區(qū)域中數(shù)字為 0 的一塊地方設(shè)置成為可移動模塊，以便騰出一個方塊位置，供相鄰的數(shù)字移動。 另外，該游戲還可以由玩家設(shè)置搜索深度，如果玩家輸入的數(shù)據(jù)初始態(tài)到達數(shù)據(jù)的目標態(tài)超過用戶設(shè)置的搜索深度，則按無解計算。 數(shù)據(jù)輸入與輸出 該游戲的數(shù)據(jù)輸入是通過鍵盤進行操作的，限制只能輸入 0~8 的數(shù)字。先載入一個內(nèi)存位圖，再從源視圖像位圖中選擇適當?shù)膮^(qū)域?qū)⑵淇截惖絻?nèi)存位圖中，當所有這些圖像方塊都繪制到內(nèi)存位圖后，再一次性地將整體圖像從內(nèi)存位圖拷貝到屏幕去。 圖 44 主窗體界面 圖像的繪制 游戲區(qū)域的視圖繪制 [6]較為簡單。 圖 43 鼠標左鍵流程圖 是 鼠標左鍵事件 結(jié)束 單擊移動功能中的方向鍵 判斷該空白塊是否可以移動 判斷是否到達邊界 移 動 是 否 結(jié) 束 空白模塊是否能移動 開 始 判斷移動方向趨勢 移動位置，修改數(shù)據(jù)狀態(tài) 12 詳細設(shè)計 詳細設(shè)計是對整個程序的整體設(shè)計 [2]，它包含窗體的設(shè)計、主窗體界面的設(shè)計、數(shù)字排列初始態(tài)和終態(tài)的設(shè)置、選擇功能及搜索過程的顯示等，以及本游戲最有特點的搜索最優(yōu)解和自動演示功能。流程圖如圖 42 所示。具體的模塊設(shè)計如圖 41 所示。 10 第 4 章 游戲功能模塊設(shè)計 系統(tǒng)模塊設(shè)計 8 數(shù)碼游戲程序的整體功能模塊 [6]，里面包含數(shù)據(jù)輸入、功能選擇 、輸出模塊等。 游戲特色分析 該游戲看起來有點類似拼圖游戲，該游戲與拼圖游戲都是基于回溯算法的基礎(chǔ)上設(shè)計。 假設(shè) A*算法未能終止在最佳路徑上 ， 而是終止在某個目標節(jié)點 t 處 ， 則有 f(t)=g(t)f*(S0) 但由引理 2 可知 ， 在 A*算法結(jié)束前 ,必有最佳路徑上的一個節(jié)點 n’在 Open表中 ， 且有 f(n’) ≤ f*(S0)f(t), 這時 ， A*算法一定會選擇 n’來擴展 ,而不可能選擇 t， 從而也不會去測試目標節(jié)點 t， 這就與假設(shè) A*算法終止在 目標節(jié)點 t 相矛盾。 由定理 1 和定理 2 可知 ， 無論是對有限圖還是無限圖 ， A*算法都能夠找到某個目標節(jié)點而結(jié)束。 定理 3： A*算法是可采納的 ， 即若存在從初始節(jié)點 S0到目標節(jié)點 Sg 的路徑 ， 則 A*算法必能結(jié)束在最佳路徑上。 9 引理 2 在 A*算法終止前的任何時刻 ， Open 表中總存在節(jié)點 n’， 它是從初始節(jié)點S0 到目標節(jié)點的最佳路徑上的一個節(jié)點 ,且滿足 ： f(n’) ≤ f*(S0) 定理 2 對無限圖 ,若從初始節(jié)點 S0到目標節(jié)點 t 有路徑存在 ， 則 A*算法必然會結(jié)束。因此 ,算法必定會成功結(jié)束。因此 ,A*算法必然會結(jié)束。 證明： 首先證明算法必定會結(jié)束。 我們分三步用以下三個定理來證明這一結(jié)論。 一般來說 ， 對任意一個狀態(tài)空間圖 ,當從初始節(jié)點到目標節(jié)點有路徑存在時 ，如果搜索算法能在有限步內(nèi)找到一條從初始節(jié)點到目標節(jié)點的最佳路徑 ， 并在此路徑上結(jié)束 ， 則稱該搜索算法是可納的。 A*算法是一個很重要的啟發(fā)式搜索算法。通過比較，該游戲選擇了 A*算法來實現(xiàn)該功能。當空白滑塊位 8 于中間時，其可以向任意方 向移動；當空白滑塊位于邊界時，需要根據(jù)其邊界的位置，進行分析其可移動的方向。所以，可以把這些功能劃分為區(qū)域，設(shè)計成按鈕的形式，通過鼠標交互功能呢，實現(xiàn)用戶的各種功能操作。其中最主要模塊是實現(xiàn)數(shù)字移動模塊和最優(yōu)解搜索模塊。 玩家可以選擇人工，自主進行空格的移動以達到最終狀態(tài)排列；也 可以選擇機器功能讓電腦自動進行排列 ，實現(xiàn)數(shù)字的最終狀態(tài)排列。狀態(tài)轉(zhuǎn)換的規(guī)則：空格周圍的數(shù)移向空格 ， 我們可以看作是空格移動 ， 它最多可以有 4 個方向的移動 ， 即上、下、左、右。 操作特性分析 八數(shù)碼是在 3 3 方格盤上 ,放有八個數(shù)碼 ， 剩下一個位置為空 ， 每一空格其上下左右的數(shù)碼可移至空格。 8 數(shù)碼游戲是廣受歡迎的一種智力游戲，能夠鍛煉人的思維能力 ， 動手 能力。成為人們在工作之余不可或缺的好伙伴。因為游戲的開發(fā)成本非常大，所以游戲的開發(fā)具有一定的風險性，但是一些小游戲的開發(fā)具有成本小，編寫簡單的優(yōu)勢，所以這些小游戲在游戲開發(fā)中也占有一席之地。則評估函數(shù)為 f(n )=g(n)+h(n)： 表示從初始節(jié)點到節(jié)點 n的一條最佳路徑的實際代價 h(n)加上從節(jié)點 n到目標節(jié)點的一條最佳路徑的代價之和 ， 最終可以找到一條從初始節(jié)點到目標節(jié)點的最佳路徑的代價。對于八數(shù)碼問題的求解 ， 可以用錯位碼的個數(shù)作為狀態(tài)描述好壞的一個度量 g(n)： 即節(jié)點的錯位碼個數(shù) (即和目標節(jié)點比較 , 位置不正確的數(shù)字個數(shù) )。然后 , 搜索就可能沿著某個被認為是最有希望的邊緣區(qū)段向外擴展 。其相對于廣度搜索 減少搜索的盲目性引，增加試探的準確性 。 A*算法 是一種常用的啟發(fā)式搜索算法 。 關(guān)鍵技術(shù)介紹 該游戲主要的功能模塊是最優(yōu)解搜索功能。 (4)文檔類 CDocument 類：是 CCmdTarget 類的子類，負責封裝和維護文檔。窗口框架類 CFrameWnd 和 CView 類是 CWnd 的子類，前者創(chuàng)建和維護窗口的邊框、菜單欄、工具欄、狀態(tài)欄，負責顯示和搜索用戶命令，后者負責為文檔提供一個或幾個視圖。應用程序類 CWinApp 是 CWinThread 的子類，封裝了初始化、運行、終止應用程序 的代碼。 (2)CWinThread 類：是 CCmdTarget 的子類。 6 MFC 類庫包括： (1)CCmdTarget 類：是 CObject 類的子類，它是 MFC 庫中所有具有消息映射屬性的類的公共基類。它封裝了 Windows API 的絕大多數(shù)功能，為用戶開發(fā) Windows 應用程序建立了一個非常靈活的應用程序框架。這些代碼包括由 Visual C++自帶的組件和從用戶工程中增 加到 Gallery 中去的用戶自定義組件。 WizardBar 包含了 3 個相關(guān)的下拉列表框，分別是類 (Class)、過濾器 (Filter)和成員 (Member)。 實用 WizardBar 還可以增加一個新類，建立一個新的函數(shù)或方法，跳到一個已存在的函數(shù)或方法。 WizardBar(向?qū)Чぞ邨l ) WizardBar 是一個可停泊的工具條，用于快速訪問一些 Developer Studio 最實用的功能，比如 ClassWizard 或 ClassView 的一些功能。 使用 ClassWizard 可 以實現(xiàn)創(chuàng)建新類，映射消息到函數(shù)，新建或刪除消息處理函數(shù)，查看已被處理的消息并跳到消息處理代碼處，定義成員變量。使用 ClassWizard，可以將成員函數(shù)或變量加入到一個類中，或修改已經(jīng)存在的函數(shù)和變量。 ClassWizard 所能識別的類必須在 ClassWizard 數(shù)據(jù)庫文件 (.CLW)中登記。 AppWizard 有為程序提供的功能性資源和代碼 ， 這樣就節(jié)省了用戶設(shè)計應用程序框架的時間和精力 ， 用戶所要做的工作只是直接往框架中添加自己的處理代碼。接著用戶還可以指定其具有一些特性，如多文檔接口或工具條 、 是否對數(shù)據(jù)庫、 OLE 的支持等，然后 AppWizard 生成一些文件，這些文件構(gòu)成程序的框架。 RourceView(資源視圖 )：顯示項目中所包含的資源文件 ， 展開文件夾可顯示所有的資源類型。 FileView(文件視圖 )：顯示所創(chuàng)建的工程 ， 展開文件夾可以查看工程中所包含的文件。 在項目視圖中，每個視圖都有一個相應的文件夾，包含了關(guān)于該項目的各種元素。在一個項目工作區(qū)中，可以處理一個工程和它所包含的文件、一個工程的子工程、多個相互獨立的工程、多個相互依賴的工程。 Developer Studio 采用標準的多窗口用戶界面，提供了大量實用工具以支持可視化編程 的特性，包括項目工作區(qū)、 AppWizard(應用程序向?qū)?)、 ClassWizard(類向?qū)?)、 WizardBar(向?qū)Чぞ邨l )、Component Gallery(組件畫廊 )等。 Developer Studio 包含了一個文本編輯器、資源編輯器、工程編譯工具、一個增量連接器、源代碼瀏覽器、集成調(diào)試工具以及一套聯(lián)機文檔 (MSDN)。 4 第 2 章 游戲開發(fā)工具 與關(guān)鍵技術(shù) 介紹 本章通過介紹 Visual C++和 MFC 的主要功能 和關(guān)鍵技術(shù)介紹，并 體現(xiàn)了這兩種工具在該游戲的開發(fā)過程中的優(yōu)勢。 第 六 章：主要介紹了游戲的部分數(shù)據(jù)測試 ，以檢測游戲的主要功能是否能夠準確執(zhí)行 。 第 四 章：主要是對游戲進行設(shè)計，包括框架搭建、算法設(shè)計及分析。 第二章：主要是對游戲主要開發(fā)工具 VisualC++、 MFC 的概述 、使用的主要技術(shù)。 在完成該游戲之后，還進行了部分的游戲數(shù)據(jù)測試，來判斷該游戲的功能是否正確的實現(xiàn)。本論文主要工作內(nèi)容是該游戲的 主 要的功能模塊的設(shè)計和實現(xiàn)，如：判斷游戲是否有解，空白模塊移動，自動演示模塊，最優(yōu)解搜索功能的實現(xiàn)，及鼠標交互 3 操作的功能。 簡單介紹了該游戲開發(fā)工具 Visual C++和 MFC，選擇這兩種開發(fā)工具簡化了游戲的界面的設(shè)計與實現(xiàn)。在前人的研究基礎(chǔ)上結(jié)合算法處理對 8 數(shù)碼游戲進行設(shè)計。 所以，在八數(shù)碼游戲中，我選擇了啟發(fā)式搜索，即 A*算法來實現(xiàn) 最優(yōu)解的搜索功能。 通過比較顯示出啟發(fā)式搜索的優(yōu)越性 ： 一方面 ， 當發(fā)現(xiàn)目標節(jié)點時 ， 可以同時找到從初始狀態(tài)到達目標狀態(tài)的一條最短路徑 ； 另一方面 ， 由于搜索不是盲目的 ， 因此不需要擴展每一層的所有節(jié)點 ， 只需要擴展最有希望到達目標的節(jié)點即可。因此 ， 這種策略是完備的。廣度優(yōu)先搜索是從初始狀態(tài)一層一層向下找 ， 直到找到目標為止。所以 ， 深度優(yōu)先搜索策略是不完備的。深度優(yōu)先搜索是按照一定的順 序先搜索完一個分支 ， 再搜索另一個分支 ， 以至找到目標為止。盲目搜索是指在不具有對待定問題的任何有關(guān)信息的條件下 ， 按固定的步驟進行的搜索 ， 如深度優(yōu)先搜索和廣度優(yōu)先搜索；啟發(fā)式搜索是指在搜索中加入了與問題有關(guān)的啟發(fā)性信息 ， 這些信息可以指導搜索朝著最有希望的方向前進 ， 加速問題的求解過程 ， 并找到最優(yōu)解 ， 如 A* 算法。在人工智能領(lǐng)域 ， 所提供的每種問題求解方法，都需要某種對解答 2 的搜索 ， 從提出問題 (即初始狀態(tài) )到問題的解決 (即最終狀態(tài) )， 有個求解的過程 ，也就是搜索過程。 編譯本程序的目的一是對自己所學知識的鞏固 ， 二是希望可以給玩家?guī)砣碌母惺?。介紹了八數(shù)碼問題 , 然后在啟發(fā)式搜索算法上對 A* 算法定義進行了解釋 ， 并在其旨在提高搜索效率的方面作了比較 詳盡的介紹 ， 詳細描述了基于圖搜索算法的解決此類問題的一種啟發(fā)式搜索算法 A* 算法。 本程序使用的是微軟最新開發(fā)的軟件： Visual C++， VC++比 C 更簡潔，為可視化界面操作，利用類實現(xiàn)各種不同的功能。 課題背景及意義 背景說明 8 數(shù)