A*算法在游戲設(shè)計中的應(yīng)用談

宇坤

摘要：應(yīng)用C++語言+EasyX圖形庫設(shè)計一套地圖類游戲，通過游戲方式將A*算法搜索最短路徑引入其中，程序?qū)*算法的各個接口進(jìn)行封裝，實現(xiàn)面向?qū)ο蟪绦蛟O(shè)計思路。游戲操作應(yīng)用消息處理機制，獲取鍵盤消息來進(jìn)行選擇判斷處理，游戲玩家需要提醒時，單擊“提示”按鈕，游戲自動調(diào)用A*算法，將最短路徑進(jìn)行模擬顯示。

關(guān)鍵詞：A*算法;EasyX圖形庫;C++

中圖分類號：TP311? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? 文章編號：1009-3044（2019）03-0082-02

1 總體設(shè)計

整個游戲設(shè)計工作包括：游戲思路設(shè)計、A*算法應(yīng)用、游戲整體流程。

1）游戲設(shè)計思路

本游戲是一個地圖類游戲，其操作與很多同類游戲都有共性，但也有一些不同的地方，啟動后有一個提示和設(shè)置難度的界面，可以查看游戲玩法，設(shè)置游戲難度;游戲開始后通過方向鍵操控“圖標(biāo)”移動;在“地圖一”模式下，不能碰到“陷阱”，否則游戲失敗，且要保證在規(guī)定的時間和步數(shù)內(nèi)到達(dá)終點;在“地圖二”模式下，要躲開所有的子彈，否則游戲失敗。

2）A*算法應(yīng)用

A*算法應(yīng)用在得到最少步數(shù)中，外部傳遞一個儲存著地圖數(shù)據(jù)的二維容器，利用A*算法，從起點開始，依次搜索開啟列表，找到F值最小的點，添加到鏈表中，然后檢驗該點，重復(fù)操作直至到達(dá)終點，就得到該地圖最短路徑的節(jié)點鏈表，并返回該鏈表，這樣外部計算鏈表的長度就可以得到最小步數(shù)了。

3）游戲整體流程

游戲通過方向鍵進(jìn)行移動【圖標(biāo)】，每走一步都要進(jìn)行判斷（位置坐標(biāo)的判斷），選擇各種不同模式，加載不同地圖和不同游戲規(guī)則，整體流程如圖1所示。

2 數(shù)據(jù)結(jié)構(gòu)設(shè)計

采用面向?qū)ο蟪绦蛟O(shè)計思路，對游戲中的處理過程進(jìn)行多個類的封裝，有利于接口函數(shù)的調(diào)用。

1）Home類：包含兩個按鈕button1，button2用于選擇模式，圖片img_home作為背景圖片，鼠標(biāo)信息m_home獲取鼠標(biāo)操作。DrawHome（） 繪制初始界面，按任意鍵結(jié)束，按ESC退出。DrawHomeButton（） 繪制按鈕，并對點擊按鈕的操作做出不同反應(yīng)。Home_Run（） 實現(xiàn)整個初始界面操作，返回不同值給主函數(shù)做以判斷下一步操作。

2）MapGame類：包含一個地圖矩陣，整形變量有地圖行數(shù)（m）、列數(shù)（n）、難度系數(shù)（coef用于控制生成障礙物的數(shù)量）、地圖左邊距（d0x）、人物左邊距（dx）、地圖移動時間（tsleep）、地圖移動次數(shù)（i1）。Setn（int setmode） 根據(jù)不同參數(shù)設(shè)置不同難度模式。ClearMatrix（） 清空地圖矩陣。InitMatrix（） 生成隨機（m*n）地圖矩陣。InitMapBlock（） 在屏幕上繪制地圖（1-9行）。MoveMapBlock（） 在屏幕上顯示地圖矩陣的移動。每隔tsleep秒移動一次。DrawCharacter（）、DrawInstruction（）、DrawButton（）、DrawSetMode（） 分別在屏幕上繪制人物、提示界面、按鈕和難度設(shè)置界面。Operate（） 根據(jù)接收的鍵盤操作控制人物的移動。

3） Game2類：包含一個地圖容器maze，一個路徑鏈表path（儲存A*算法得到的最短路徑上的各個節(jié)點），整形變量有地圖行數(shù)（_m）、列數(shù)（_n）、難度系數(shù)（coef）、格寬（_d）、首列左邊距（_d0x）、首行右邊距（_d0y）、人物行數(shù)（cur_m）、列數(shù)（cur_n）、游戲結(jié)束標(biāo)志（_gameflag）、A*算法返回的最小步數(shù)（pathsize）、當(dāng)前已走步數(shù)（cursize）、最大允許超過的步數(shù)（sizecoef）、當(dāng)前得分（cur_score）、游戲秒數(shù)（_second）、允許時間（timecoef）。_Setn（int _setmode） 根據(jù)不同參數(shù)設(shè)置不同難度模式。_Getmaze（vector<vector<int>>&_maze） 從外部傳遞一個二維vector的地址，從而給Game2類的maze賦值。DrawButton（）、_DrawInstruction（）、_DrawSetMode（） 分別在屏幕上繪制按鈕、提示界面、難度設(shè)置界面。_InitMap（） 生成隨機地圖，并用A*算法進(jìn)行檢查，直至生成合法的地圖。_DrawMap（） 繪制地圖與人物。_Operate（） 根據(jù)接收的鍵盤操作控制人物的移動。

4）Button類：包含四個整型變量left、right、top、bottom，分別表示按鈕的左、上、右、下界。SetRange（int a， int b， int c， int d） 確定按鈕的范圍。DrawButton（int x） 在屏幕上繪制按鈕，x取不同值對應(yīng)按鈕的不同顏色。Click（int _x， int _y， int x） 模擬點擊按鈕操作，_x、_y傳入鼠標(biāo)點擊的位置，判斷是否點中按鈕，若點中則進(jìn)行相關(guān)反應(yīng)。x取不同值對應(yīng)按鈕的不同顏色。

5）Astar類：預(yù)先定義結(jié)構(gòu)體POINT，有坐標(biāo)x、y，值F、G、H，一個父節(jié)點POINT parent（取地址）。Astar類包含整型變量curx、cury（儲存當(dāng)前節(jié)點坐標(biāo)，用于后一步判斷），一個儲存地圖的二維vectormaze，兩個儲存結(jié)構(gòu)體POINT指針的鏈表openList、closeList，分別記錄待檢驗的節(jié)點和已經(jīng)檢驗過的節(jié)點。Point *findPath（Point &startPoint， Point &endPoint， bool isIgnoreCorner）尋找起點到終點的最短路徑，返回指向終點的指針（此時路徑上每一節(jié)點的父節(jié)點都指向最短路徑的前一節(jié)點）。std：：vector<Point *> getSurroundPoints（const Point *point， bool isIgnoreCorner） const尋找當(dāng)前節(jié)點的周圍節(jié)點，返回儲存這些節(jié)點的容器。bool isCanreach（const Point *point， const Point *target， bool isIgnoreCorner） const判斷某節(jié)點是否符合條件（與某一節(jié)點相鄰、能走通、不超出地圖、不是障礙物等）。符合則返回true。Point *isInList（const std：：list<Point *>&list， const Point *point） const判斷開啟/關(guān)閉列表中是否包含某節(jié)點，是則返回該點。Point *getLeastFpoint（bool isIgnoreCorner）從開啟列表中返回周圍節(jié)點中F值最小的節(jié)點。int calcG（Point *temp_start， Point *point） 計算G值。int calcH（Point *point， Point *end） 計算H值。int calcF（Point *point） 計算F值。

3 算法應(yīng)用

地圖加載時應(yīng)用到A*算法，判斷地圖是否有合適的路徑到達(dá)終點，單擊【提示】功能時調(diào)用A*算法獲取最短路徑，代碼如下：

4 結(jié)束語

完成本游戲的設(shè)計及編碼，對面向?qū)ο蟪绦蛟O(shè)計的思路有了更深刻的理解，針對圖形化界面的顯示處理掌握了技巧（代碼控制），進(jìn)一步熟練運用EasyX圖形庫。A*算法的封裝、應(yīng)用（地圖加載與路徑提示）提升了一個臺階，也掌握了消息循環(huán)機制，除此之外，在游戲的編寫過程中也用了很多數(shù)學(xué)知識，使得邏輯思維得到充分訓(xùn)練。

參考文獻(xiàn)：

[1] 郭海鋒，晁會勇，徐東偉.基于A*優(yōu)化算法的停車場動態(tài)泊車研究[J].計算機測量與控制，2018，26（7）：225-228，305.

[2] 茍淞，周加樂，劉宏.智能循跡車及其路徑規(guī)劃的設(shè)計[J].科技創(chuàng)新與應(yīng)用，2018（22）：92-93.

[3] 王小紅，葉濤.基于改進(jìn)A*算法機器人路徑規(guī)劃研究[J].計算機測量與控制，2018，26（7）：282-286.

[4] 張煜昕.基于EasyX圖形庫的多線程繪圖應(yīng)用[J].電腦知識與技術(shù)，2018，14（30）：226-228.

[5] 殷志堅，段曉磊.基于EasyX的俄羅斯方塊游戲的設(shè)計和分析[J].科技傳播，2015，7（21）：137，157.

【通聯(lián)編輯：朱寶貴】