【正文】 IV The Design and Development of 8 Digital Game Based on VC++ Abstract Digital games are eight 3 3 grid on the plate, placed eight digital, leaving a position is empty, its top and bottom of each box can be moved around the digital given the initial position and target location, requiring a series of digital mobile, the initial state into a goal state. As the game development tools, Visual C++ has a visual programming interface, the detailed tips, and plete help documentation, made me less in the software development process take a lot of detours, improve the efficiency of my is one of a set of written specifically for Microsoft Windows Programming C++ based class library that encapsulates the vast majority of Windows API functions for users to develop Windows applications created a very flexible application framework. This thesis work is the game39。s main function modules of the design and implementation: to determine whether the solvability of the game, move the blank module, automatic presentation module, the search function to achieve the optimal solution, and mouse interaction the optimal solution which is mainly used to achieve A * shortest path algorithm. 【 Key words】 Digital Games MFC A * algorithm Shortest Path 1 第 1 章 緒 論 隨著世界經(jīng)濟(jì)的長(zhǎng)足發(fā)展和計(jì)算機(jī)技術(shù)的日益成熟 ， 計(jì)算機(jī)被應(yīng)用到人類活動(dòng)的各個(gè)領(lǐng)域，各種應(yīng)用軟件也相繼問世，這其中有相當(dāng)一部分是游戲軟件。使用游戲軟 件自然是為了滿足人們對(duì)娛樂性的要求，而有些軟件大都采用 3D 設(shè)計(jì)對(duì)系統(tǒng)配置的要求較高。 在眾多游戲軟件中，也不乏一些小游戲的身影 ， 它們對(duì)系統(tǒng)的配置要求較低。能夠滿足人們對(duì)娛樂性的需求 ， 是人們?cè)谕瓿晒ぷ?娛樂時(shí)候的最好選擇?，F(xiàn)在越來越多的人投入到這種小游戲的開發(fā)當(dāng)中， 它已經(jīng)成為一類必不可少的游戲軟件。在各種操作系統(tǒng)中都附帶了一些小的游戲 ， 而這些游戲也成為電腦用戶軟件中不可或缺的一部分。如數(shù)碼游戲 、 掃雷等。 課題背景及意義 背景說明 8 數(shù)碼游戲操作能培養(yǎng)手眼協(xié)調(diào)能力─游戲需要耐心的操作 ， 以及手眼協(xié)調(diào)能力 ， 只要一不協(xié)調(diào)就不能將數(shù)據(jù)塊放在正確的位置。學(xué)習(xí)解決問題的方法及策略─玩 8 數(shù)碼游戲能學(xué)習(xí)推理思考能力 ， 因?yàn)閲L試不同的選擇 ， 到?jīng)Q定正確的一塊放下去，也就是經(jīng)過假設(shè) 、 判斷到選擇的過程 ， 能讓玩家學(xué)習(xí)運(yùn)用邏輯來解決問題的方法。 本程序使用的是微軟最新開發(fā)的軟件： Visual C++， VC++比 C 更簡(jiǎn)潔，為可視化界面操作，利用類實(shí)現(xiàn)各種不同的功能。 課題意義 在人工智能領(lǐng)域中 ， 八數(shù)碼問題一直都是一個(gè)游戲難題。介紹了八數(shù)碼問題 , 然后在啟發(fā)式搜索算法上對(duì) A* 算法定義進(jìn)行了解釋 ， 并在其旨在提高搜索效率的方面作了比較 詳盡的介紹 ， 詳細(xì)描述了基于圖搜索算法的解決此類問題的一種啟發(fā)式搜索算法 A* 算法。再依據(jù)這種算法用可視化編程語言 VC+ + 來實(shí)現(xiàn)八數(shù)碼問題的求解過程 ， 取得了預(yù)期的搜索解 ， 提高了搜索效率。 編譯本程序的目的一是對(duì)自己所學(xué)知識(shí)的鞏固 ， 二是希望可以給玩家?guī)砣碌母惺堋? 八數(shù)碼游戲的研究現(xiàn)狀 在信息社會(huì)里，人們?cè)絹碓揭蕾囉谒阉骷夹g(shù)獲取有用的信息，搜索是人工智能中的一個(gè)基本問題，是推理不可分割的一部分，它直接關(guān)系到智能系統(tǒng)的性能和運(yùn)行效率。在人工智能領(lǐng)域 ， 所提供的每種問題求解方法，都需要某種對(duì)解答 2 的搜索 ， 從提出問題 (即初始狀態(tài) )到問題的解決 (即最終狀態(tài) )， 有個(gè)求解的過程 ，也就是搜索過程。用于搜索的方法 [13]主要有兩大類：一類是盲目搜索 ， 另一類是啟發(fā)式搜索。盲目搜索是指在不具有對(duì)待定問題的任何有關(guān)信息的條件下 ， 按固定的步驟進(jìn)行的搜索 ， 如深度優(yōu)先搜索和廣度優(yōu)先搜索；啟發(fā)式搜索是指在搜索中加入了與問題有關(guān)的啟發(fā)性信息 ， 這些信息可以指導(dǎo)搜索朝著最有希望的方向前進(jìn) ， 加速問題的求解過程 ， 并找到最優(yōu)解 ， 如 A* 算法。 八數(shù)碼游戲的研究現(xiàn)狀主要是如何選擇更更快速 、 更高效地找到問題的解答。深度優(yōu)先搜索是按照一定的順 序先搜索完一個(gè)分支 ， 再搜索另一個(gè)分支 ， 以至找到目標(biāo)為止。由于一個(gè)有解的問題可能含有無窮分支 ， 該搜索如果誤入無窮分枝 (即深度無限 )， 則不可能找到目標(biāo)節(jié)點(diǎn)。所以 ， 深度優(yōu)先搜索策略是不完備的。另外 ， 應(yīng)用此策略得到的解不一定是最佳解。廣度優(yōu)先搜索是從初始狀態(tài)一層一層向下找 ， 直到找到目標(biāo)為止。當(dāng)我們發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí) ， 可以同時(shí)找到從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的一條最短路徑。因此 ， 這種策略是完備的。以上兩種搜索有一個(gè)很大的缺陷 ， 就是它們都是在一個(gè)給定的狀態(tài)空間中窮舉 ， 極容易遇到以下問題：搜索中易出現(xiàn)循環(huán) ， 即訪問某一個(gè)狀態(tài)后又來訪 問該狀態(tài)；搜索路徑不佳便無法得到較好的中間狀態(tài)集 (即中間狀態(tài)集的元素?cái)?shù)量過大 )；搜索過程中訪問了過多的無用狀態(tài) ， 這些狀態(tài)對(duì)最后的結(jié)果無幫助。 通過比較顯示出啟發(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)。 所以，在八數(shù)碼游戲中，我選擇了啟發(fā)式搜索，即 A*算法來實(shí)現(xiàn) 最優(yōu)解的搜索功能。 本論文的研究?jī)?nèi)容 本文深入分析了課題的背景及意義、八數(shù)碼游戲的現(xiàn)狀和發(fā)展趨勢(shì)、 對(duì)游戲的需求分析 (講述游戲的功能和對(duì)操作進(jìn)行分析 )、游戲特色進(jìn)行了分析說明 。在前人的研究基礎(chǔ)上結(jié)合算法處理對(duì) 8 數(shù)碼游戲進(jìn)行設(shè)計(jì)。本游戲在最優(yōu)解搜索部分通過在對(duì)各種算法的可行性和效率進(jìn)行了比較，最終選擇 了 A*算法來實(shí)現(xiàn)該模塊的功能。 簡(jiǎn)單介紹了該游戲開發(fā)工具 Visual C++和 MFC，選擇這兩種開發(fā)工具簡(jiǎn)化了游戲的界面的設(shè)計(jì)與實(shí)現(xiàn)。通過系統(tǒng)的分析和策劃，實(shí)現(xiàn)了游戲的主要功能。本論文主要工作內(nèi)容是該游戲的 主 要的功能模塊的設(shè)計(jì)和實(shí)現(xiàn)，如：判斷游戲是否有解，空白模塊移動(dòng)，自動(dòng)演示模塊，最優(yōu)解搜索功能的實(shí)現(xiàn)，及鼠標(biāo)交互 3 操作的功能。 其中最優(yōu)解搜索功能主要是使用 了 A*算法來實(shí) 現(xiàn)最短路徑搜索。 在完成該游戲之后，還進(jìn)行了部分的游戲數(shù)據(jù)測(cè)試，來判斷該游戲的功能是否正確的實(shí)現(xiàn)。 論文結(jié)構(gòu) 第一章：主要介紹了課題的研究課題研究背景和意義、 八數(shù)碼游戲的發(fā)展現(xiàn)狀 、以及論文的研究?jī)?nèi)容，并介紹了本游戲的主要工作。 第二章：主要是對(duì)游戲主要開發(fā)工具 VisualC++、 MFC 的概述 、使用的主要技術(shù)。 第三章：主要介紹了游戲的系統(tǒng)分析 ，包括：需求分析、功能分析、可行性分析等。 第 四 章：主要是對(duì)游戲進(jìn)行設(shè)計(jì)，包括框架搭建、算法設(shè)計(jì)及分析。 第 五 章：主要是進(jìn)行游戲的實(shí)現(xiàn)，包括游戲的界面、核心功能、用戶交互操作的實(shí)現(xiàn)。 第 六 章：主要介紹了游戲的部分?jǐn)?shù)據(jù)測(cè)試 ，以檢測(cè)游戲的主要功能是否能夠準(zhǔn)確執(zhí)行 。 第 七 章：對(duì)自己所做的工作進(jìn)行總結(jié)，同時(shí)對(duì)數(shù)碼游戲做了展望。 4 第 2 章 游戲開發(fā)工具 與關(guān)鍵技術(shù) 介紹 本章通過介紹 Visual C++和 MFC 的主要功能 和關(guān)鍵技術(shù)介紹，并 體現(xiàn)了這兩種工具在該游戲的開發(fā)過程中的優(yōu)勢(shì)。 Visual C++概述 Visual C++[3]為用戶提供了一個(gè)可視化、通用的應(yīng)用程序集成開發(fā)環(huán)境 ——Developer Studio(也俗稱 Visual Studio)。 Developer Studio 包含了一個(gè)文本編輯器、資源編輯器、工程編譯工具、一個(gè)增量連接器、源代碼瀏覽器、集成調(diào)試工具以及一套聯(lián)機(jī)文檔 (MSDN)。通過 Developer Studio， 開發(fā)人員可以完成項(xiàng)目工程的創(chuàng)建、程序的編輯、修改、運(yùn)行和調(diào)試等各種操作。 Developer Studio 采用標(biāo)準(zhǔn)的多窗口用戶界面，提供了大量實(shí)用工具以支持可視化編程 的特性，包括項(xiàng)目工作區(qū)、 AppWizard(應(yīng)用程序向?qū)?)、 ClassWizard(類向?qū)?)、 WizardBar(向?qū)Чぞ邨l )、Component Gallery(組件畫廊 )等。 項(xiàng)目工作區(qū) 在 Developer Studio 中，項(xiàng)目工作區(qū)用于組織項(xiàng)目、元素以及項(xiàng)目信息在屏幕上的顯示方式。在一個(gè)項(xiàng)目工作區(qū)中，可以處理一個(gè)工程和它所包含的文件、一個(gè)工程的子工程、多個(gè)相互獨(dú)立的工程、多個(gè)相互依賴的工程。 項(xiàng)目工作區(qū)底部有一組項(xiàng)目視圖切換選項(xiàng)卡 (包括 3 種視圖 )，用于從不同的角度查看項(xiàng)目中包含的工程和聯(lián)機(jī)文檔。 在項(xiàng)目視圖中，每個(gè)視圖都有一個(gè)相應(yīng)的文件夾，包含了關(guān)于該項(xiàng)目的各種元素。 3 種視圖的含義如下所述。 FileView(文件視圖 )：顯示所創(chuàng)建的工程 ， 展開文件夾可以查看工程中所包含的文件。 ClassView(類視圖 )：顯示項(xiàng)目中定義的 C++類，可以查看工程中定義的所有類，展開類還可以查看類的數(shù)據(jù)成員 、 成員函數(shù) 、 全局變量、函數(shù)和類型定義。 RourceView(資源視圖 )：顯示項(xiàng)目中所包含的資源文件 ， 展開文件夾可顯示所有的資源類型。 AppWizard(應(yīng)用程序向?qū)?) AppWizard 是一個(gè)標(biāo)準(zhǔn)的 C++源 代碼生成器，它首先通過一系列的對(duì)話框來提示用戶輸入所需創(chuàng)建的程序信息。接著用戶還可以指定其具有一些特性，如多文檔接口或工具條 、 是否對(duì)數(shù)據(jù)庫、 OLE 的支持等，然后 AppWizard 生成一些文件，這些文件構(gòu)成程序的框架。 由于 AppWizard 生成的程序是一個(gè)基本的 Windows 程序，用戶可以直接編 5 譯并運(yùn)行。 AppWizard 有為程序提供的功能性資源和代碼 ， 這樣就節(jié)省了用戶設(shè)計(jì)應(yīng)用程序框架的時(shí)間和精力 ， 用戶所要做的工作只是直接往框架中添加自己的處理代碼。 ClassWizard(類向?qū)?) ClassWizard 是一個(gè)交互式工具，用來建立新的類、定制類 ， 把消息映射成類成員函數(shù)，或者把控制框映射為類變量成員。 ClassWizard 所能識(shí)別的類必須在 ClassWizard 數(shù)據(jù)庫文件 (.CLW)中登記。在開發(fā)程序時(shí)，可用 ClassWizard 建立程序所需要的類，包括消息處理和消息映射例程 (用于定位處理消息的代碼 )。使用 ClassWizard，可以將成員函數(shù)或變量加入到一個(gè)類中，或修改已經(jīng)存在的函數(shù)和變量。 Wizard 使函數(shù)或變量放在何處，如何稱呼它們以及其他一些細(xì)節(jié)問題大大簡(jiǎn)化。 使用 ClassWizard 可 以實(shí)現(xiàn)創(chuàng)建新類，映射消息到函數(shù)，新建或刪除消息處理函數(shù)，查看已被處理