一种战棋游戏的AI算法设计与实现浅析.doc

第 26 卷 第 2 期 2011 年 11 月 西藏大学学报(自然科学版） Vol.26 No.2 JOURNAL OF TIBET UNIVERSITY Nov. 2011 一种战棋游戏的 AI 算法设计与实现浅析 格桑多吉 王玉龙 郭 鑫 （西藏大学工学院 西藏拉萨 850000） 摘要：文章描述了利用改进 A* 算法实现的战棋游戏 AI 设计。对战棋游戏基本元素进行了分析，并给 出了算法设计的整体思路，采用 C++实现了战棋游戏基本元素的数据结构，用类广度优先算法实现了对棋 子可走范围的计算，用类折半查找和模糊行为确定了行动的选取和实施的目标，用逆遍历栈的方法确定 一条到目标格的合适路径。 关键词：战棋游戏；AI；算法 中图分类号：TP18 文献标识码：A 文章编号：1005-5738（2011）02-102-05 引 言 游戏，作为一种新型的电子艺术手段，具有传统艺术手段（小说、戏剧、电影、美术等）所不具备的极强 的人物代入感，深刻影响着游戏玩家的世界观、价值观甚至审美观。其在精神领域所体现的巨大褒贬作用 以及对于感情的宣泄效果是传统艺术所望尘莫及的。在我国实现现代化、宣扬社会主义文化的进程中，这 种新兴电子艺术所产生的巨大影响力是不可忽视的,因此应该不断提高目前国内业界相对欠缺或落后的 游戏理念、游戏算法以及各种相关的技术，使其为祖国的社会主义文化事业服务。 本文描述了以弘扬反抗侵略、不屈外辱、保家卫国的伟大民族精神为主线的藏汉双语版创新战棋型 游戏“江孜保卫战”的基本算法设计和实现方法。 战棋型游戏类似于传统棋类游戏，是玩家双方在“棋盘”上轮流控制自己的“棋子”进行战斗的一种电 脑游戏，其英文简写为“TRPG”[1]。不同的是，战棋游戏的“棋子”一般为具有一定属性的人物或生物，其“棋 盘”一般为一定行数和列数的网格，每个网格有一定属性。每个“棋子”具有行动优先级，在固定回合每方 只能控制固定的“棋子”行动。本文所指的战棋游戏作为抽象范例，只具有最基本的元素。 1 相关术语 1.1 单位：即通常棋类游戏里的“棋子”。 1.2 格子：也称“格”，棋盘由一系列规则排列的格子组成，每个单位占据一个格子，并且以格为单位进行 收稿日期：201 1 - 09- 25 基金项目：201 0 年度国家大学生创新性实验计划项目“藏汉双语版创新战棋型游戏‘江孜保卫战’”阶段性成果，项目号： 1 01 06941 9 第一作者简介：格桑多吉，男，藏族，西藏日喀则人，西藏大学工学院副教授，主要研究方向为藏文信息处理。 1.3 移动力：单位拥有的移动能力，单位每移动一格，将消耗一定的移动力，也称“速度”。 1.4 模糊行为：指电脑采取的行动并不固定，而是具有一定的随机性。在设定的几率（一般低于 20%）内电 脑将随机采取某种行为，反之则采取程序预先设定好的行为。 2 AI 的算法实现及 C++代码 2.1 整体思路 A* 算法在人工智能中是一种典型的启发式有哪些信誉好的足球投注网站算法，是最好优先算法的一种[2]。利用改进 A* 算法实 现了战棋游戏 AI（Artificial Intelligence，简称 AI）设计。首先对战棋游戏基本元素进行了分析，接着 给出了算法设计的整体思路，然后设计并用 C++ 实现了战棋游戏基本元素的数据结构。用类广度优先算 法实现了对棋子可走范围的计算[3]，用类折半查找和模糊行为确定了选取的行动和行动实施的目标[4]，用 逆遍历栈的方法确定出一条到目标格的合适路径。下面给出了相关实现代码。 ①用类广度优先遍历确定此单位的行走范围，将范围中的格入栈，并置 flag 为 1； ②分析范围内所有敌人的综合情况，利用类折半查找方式确定目标格和实施的动作； ③从目标格到当前所在格逆推出一条可走路径，并沿此路径走到目标格，实施动作。 2.2 单位信息的存储 单位具有编号、移动力、生命值的属性，故采用结构体储存。其代码如下： typedef struct role{ int row;//棋子所在格的行数 inr column;//棋子所在格的列数 int speed;//移动力 }role; role role1;//role1 为电脑所要控制行动的单位[5] 2.3 棋盘格子信息的存储 由于每个格子具有行数、列数、消耗多少移动力的属性，故采用二维结构体数组存储[6]。为了扩展单 位可行走区域的方便，给每个格增加两个属性，即是否已扩展标志 flag 和是否有人标志 block。其代码 如下： typedef struct mapTile{ int decrease;//存储消耗 int flag;//0 为未扩展 int block; //0 为无人，其余为所在单位的编号 }map; map map[100][100];//设棋盘长宽都