A*算法在游戏设计中的应用谈

宇坤

摘要：应用C++语言+EasyX图形库设计一套地图类游戏，通过游戏方式将A*算法搜索最短路径引入其中，程序将A*算法的各个接口进行封装，实现面向对象程序设计思路。游戏操作应用消息处理机制，获取键盘消息来进行选择判断处理，游戏玩家需要提醒时，单击“提示”按钮，游戏自动调用A*算法，将最短路径进行模拟显示。

关键词：A*算法;EasyX图形库;C++

中图分类号：TP311        文献标识码：A        文章编号：1009-3044（2019）03-0082-02

1 总体设计

整个游戏设计工作包括：游戏思路设计、A*算法应用、游戏整体流程。

1）游戏设计思路

本游戏是一个地图类游戏，其操作与很多同类游戏都有共性，但也有一些不同的地方，启动后有一个提示和设置难度的界面，可以查看游戏玩法，设置游戏难度;游戏开始后通过方向键操控“图标”移动;在“地图一”模式下，不能碰到“陷阱”，否则游戏失败，且要保证在规定的时间和步数内到达终点;在“地图二”模式下，要躲开所有的子弹，否则游戏失败。

2）A*算法应用

A*算法应用在得到最少步数中，外部传递一个储存着地图数据的二维容器，利用A*算法，从起点开始，依次搜索开启列表，找到F值最小的点，添加到链表中，然后检验该点，重复操作直至到达终点，就得到该地图最短路徑的节点链表，并返回该链表，这样外部计算链表的长度就可以得到最小步数了。

3）游戏整体流程

游戏通过方向键进行移动【图标】，每走一步都要进行判断（位置坐标的判断），选择各种不同模式，加载不同地图和不同游戏规则，整体流程如图1所示。

2 数据结构设计

采用面向对象程序设计思路，对游戏中的处理过程进行多个类的封装，有利于接口函数的调用。

1）Home类：包含两个按钮button1，button2用于选择模式，图片img_home作为背景图片，鼠标信息m_home获取鼠标操作。DrawHome（） 绘制初始界面，按任意键结束，按ESC退出。DrawHomeButton（） 绘制按钮，并对点击按钮的操作做出不同反应。Home_Run（） 实现整个初始界面操作，返回不同值给主函数做以判断下一步操作。

2）MapGame类：包含一个地图矩阵，整形变量有地图行数（m）、列数（n）、难度系数（coef用于控制生成障碍物的数量）、地图左边距（d0x）、人物左边距（dx）、地图移动时间（tsleep）、地图移动次数（i1）。Setn（int setmode） 根据不同参数设置不同难度模式。ClearMatrix（） 清空地图矩阵。InitMatrix（） 生成随机（m*n）地图矩阵。InitMapBlock（） 在屏幕上绘制地图（1-9行）。MoveMapBlock（） 在屏幕上显示地图矩阵的移动。每隔tsleep秒移动一次。DrawCharacter（）、DrawInstruction（）、DrawButton（）、DrawSetMode（） 分别在屏幕上绘制人物、提示界面、按钮和难度设置界面。Operate（） 根据接收的键盘操作控制人物的移动。

3） Game2类：包含一个地图容器maze，一个路径链表path（储存A*算法得到的最短路径上的各个节点），整形变量有地图行数（_m）、列数（_n）、难度系数（coef）、格宽（_d）、首列左边距（_d0x）、首行右边距（_d0y）、人物行数（cur_m）、列数（cur_n）、游戏结束标志（_gameflag）、A*算法返回的最小步数（pathsize）、当前已走步数（cursize）、最大允许超过的步数（sizecoef）、当前得分（cur_score）、游戏秒数（_second）、允许时间（timecoef）。_Setn（int _setmode） 根据不同参数设置不同难度模式。_Getmaze（vector<vector<int>>&_maze） 从外部传递一个二维vector的地址，从而给Game2类的maze赋值。DrawButton（）、_DrawInstruction（）、_DrawSetMode（） 分别在屏幕上绘制按钮、提示界面、难度设置界面。_InitMap（） 生成随机地图，并用A*算法进行检查，直至生成合法的地图。_DrawMap（） 绘制地图与人物。_Operate（） 根据接收的键盘操作控制人物的移动。

4）Button类：包含四个整型变量left、right、top、bottom，分别表示按钮的左、上、右、下界。SetRange（int a， int b， int c， int d） 确定按钮的范围。DrawButton（int x） 在屏幕上绘制按钮，x取不同值对应按钮的不同颜色。Click（int _x， int _y， int x） 模拟点击按钮操作，_x、_y传入鼠标点击的位置，判断是否点中按钮，若点中则进行相关反应。x取不同值对应按钮的不同颜色。

5）Astar类：预先定义结构体POINT，有坐标x、y，值F、G、H，一个父节点POINT parent（取地址）。Astar类包含整型变量curx、cury（储存当前节点坐标，用于后一步判断），一个储存地图的二维vectormaze，两个储存结构体POINT指针的链表openList、closeList，分别记录待检验的节点和已经检验过的节点。Point *findPath（Point &startPoint， Point &endPoint， bool isIgnoreCorner）寻找起点到终点的最短路径，返回指向终点的指针（此时路径上每一节点的父节点都指向最短路径的前一节点）。std：：vector<Point *> getSurroundPoints（const Point *point， bool isIgnoreCorner） const寻找当前节点的周围节点，返回储存这些节点的容器。bool isCanreach（const Point *point， const Point *target， bool isIgnoreCorner） const判断某节点是否符合条件（与某一节点相邻、能走通、不超出地图、不是障碍物等）。符合则返回true。Point *isInList（const std：：list<Point *>&list， const Point *point） const判断开启/关闭列表中是否包含某节点，是则返回该点。Point *getLeastFpoint（bool isIgnoreCorner）从开启列表中返回周围节点中F值最小的节点。int calcG（Point *temp_start， Point *point） 计算G值。int calcH（Point *point， Point *end） 计算H值。int calcF（Point *point） 计算F值。

3 算法应用

地图加载时应用到A*算法，判断地图是否有合适的路径到达终点，单击【提示】功能时调用A*算法获取最短路径，代码如下：

4 结束语

完成本游戏的设计及编码，对面向对象程序设计的思路有了更深刻的理解，针对图形化界面的显示处理掌握了技巧（代码控制），进一步熟练运用EasyX图形库。A*算法的封装、应用（地图加载与路径提示）提升了一个台阶，也掌握了消息循环机制，除此之外，在游戏的编写过程中也用了很多数学知识，使得逻辑思维得到充分训练。

参考文献：

[1] 郭海锋，晁会勇，徐东伟.基于A*优化算法的停车场动态泊车研究[J].计算机测量与控制，2018，26（7）：225-228，305.

[2] 苟淞，周加乐，刘宏.智能循迹车及其路径规划的设计[J].科技创新与应用，2018（22）：92-93.

[3] 王小红，叶涛.基于改进A*算法机器人路径规划研究[J].计算机测量与控制，2018，26（7）：282-286.

[4] 张煜昕.基于EasyX图形库的多线程绘图应用[J].电脑知识与技术，2018，14（30）：226-228.

[5] 殷志坚，段晓磊.基于EasyX的俄罗斯方块游戏的设计和分析[J].科技传播，2015，7（21）：137，157.

【通联编辑：朱宝贵】