基于多目标遗传算法的游戏路径规划研究

龙源期刊网 http://www.qikan.com.cn

基于多目标遗传算法的游戏路径规划研究 作者:刘大瑞 冯镍

来源:《软件导刊》2014年第01期

摘要:为游戏中非玩家控制角色(NPC )设计自动寻路算法是人工智能研究领域的一大热点。首先模拟多目标游戏地图作为实验平台,然后以路径长度、路径安全程度和对游戏角色的耗费为评估目标,提出了基于多目标遗传算法的路径规划方法。经过实验验证,算法虽然比A*算法实时性差,但其对地图全局有很好的把握,在多目标环境下,其得到的路径存在明显的全局最优。

关键词:多目标优化;遗传算法;游戏NPC ;路径规划

中图分类号:TP312 文献标识码:A 文章编号文章编号:16727800(2014)001004902 作者简介作者简介:刘大瑞(1987-),男,四川大学计算机学院硕士研究生,研究方向为数字娱乐与人机交互。

0 引言

随着游戏产业的快速发展,对游戏质量的要求逐步上升,玩家希望看到趣味性足、挑战性强的高质量游戏。为了提高游戏质量,大量游戏引入了非玩家控制角色[1](NPC )与玩家进行交互,以提高游戏的可玩性和真实性。因此,NPC 的行为研究成为游戏设计者关心的重要因素。而在游戏中,NPC 的行为除与玩家交互外,主要就是自主寻路,其所选路径的质量决定其自身的智能性和游戏的真实性。

对于游戏NPC 智能路径规划的研究,提出过许多方法,主要有A*算法及其改进算法[2,3]、遗传算法[4]、蚁群算法[5]和神经网络方法[6]等。但在实际应用中,游戏设计者普遍选择A*算法,这是由其较高的正确率和较好的实时性决定的。但是,随着游戏地图[7]的多样化,仅仅用路径长短去评估路径质量是不够的,游戏地图中通常还需要考虑路径的安全性、路径的耗费等多个方面。在此情况下,A*算法就变得不适用,由此诞生了许多不同的方法。其中,孙纯哲提出了双蚁群交叉算法[8],但该方法未考虑连续障碍物,实时性差。此外,Xiao J,Z.Michalewicz[9]提出了线性加权的改进A*算法,其只是将多个目标进行简单加权相加,得到启发函数,故该方法存在主观性和随意性。针对以上情况,本文提出了一种多目标遗传算法的路径规划方法。

本文为游戏中的NPC 寻路,提出了一种多目标智能路径规划算法,并将其与传统寻路算法进行对比,突出其在游戏中智能自动寻路的优点。本文使用基于多目标的遗传算法优化路径,同时引入帕累托最优解集[10]作为寻路结果,在综合考虑多个寻路目标平衡的基础上,获得满足条件的最优解集。最后,从解集中,筛选满足游戏情景的最优路径选择。


相关范文

  1. 路径规划的智能控制

    (综述报告) 考 核 科 目 :机电系统智能控制 学生所在院(系):机电学院 学生所在学科 :机学生姓名 学号 : 学生类别 :工考 核 结 果 械制学 造 阅卷人 智能控制在机器人领域的应用 遗传算法在移动机器人路径规划上的研究 摘要:近些年来机器人技术飞速发展,对机器人运动的控制要求越来越高,机 ...

  2. 多机器人路径规划方法研究

    第21卷 第1期 文章编号:100325850(2008) 0120051203 电脑开发与应用(总53 ) ・51・ 多机器人路径规划方法研究 Study on M ulti -robots Pa th Plann i ng M ethod 贾润亮 安建成 (太原理工大学 太原 030024) [ ...

  3. 车辆路径问题的模型及算法研究综述

    管 理 工 程 学 报 Vol119,No11 JournalofIndustrialEngineeringΠEngineeringManagement 2005年第1期 外论评介 车辆路径问题的模型及算法研究综述 刘云忠,宣慧玉 (西安交通大学管理学院,陕西西安710049) 摘要:本文在文献[1 ...

  4. 一起来探究机器人的智能避障算法

    一起来探究机器人的智能避障算法 目前智能机器人的避障根据环境信息的掌握程度可以分为障碍物信息已知.障碍物信息部分未知或完全未知两种. 实际生活中,绝大多数的情况下,机器人所处的环境都是动态的.可变的.未知的,为了解决上述问题,人们引入了计算机和人工智能等领域的一些算法.同时得益于处理器计算能力的提高 ...

  5. 智能机器人导航控制技术综述-

    智能移动机器人导航控制技术综述* 李成进1,王芳2 (1海军驻昆明地区军事代表办事处,云南 昆明, 2航天科工智能机器人有限责任公司,北京 100074) 摘 要:智能移动机器人在制造业.服务业.军事.星际探测等领域获得了广泛的应用,导航是智能移动机器人实现自主控制需要解决的重要问题.对不同领域智能 ...

  6. 基于多目标规划的车辆路径问题及其算法优化

    基于多目标规划的车辆路径问题及 其算法优化 摘要:针对带时间窗的车辆路径问题,通过引入模糊层次分析法,首先建立了考虑多目标的全面性的数学模型,然后运用了基于改进型的模拟退火算法,采取实时优化的求解策略,最后通过仿真实验进行计算.由计算结果可以得出本文设计的改进型模拟退火算法运算速度快.计算效率高等特 ...

  7. 移动机器人路径规划算法研究

    南京师范大学 硕士学位论文 移动机器人路径规划算法研究 姓名:蔡文彬 申请学位级别:硕士 专业:计算机软件与理论 指导教师:朱庆保 20100507 摘要 摘要 在全局已知环境下,用传统蚁群算法进行机器人路径规划具有收敛速度慢,容易陷入局部最优等缺点.为此,本文首先根据对真实蚂蚁的研究成果,提出了一 ...

  8. 一种求解TSP问题的并行遗传算法

    第22卷 第2期 文章编号:1006-9348(2005) 02-0082-04 计 算 机 仿 真 2005年2月 一种求解TSP 问题的并行遗传算法 侯建花, 杨长青 (成都理工大学, 四川成都610059) 摘要:遗传算法(G A ) 是一种基于自然群体遗传机制的有效搜索算法, 由于它在搜索空 ...

  9. 移动机器人的发展现状及其趋势

    2001年第3期<机器人技术与应用> 移动机器人的发展现状及其趋势 ◆徐国华谭民 中科院自动化研究所 -.引言 机器人的应用越来越广泛,几乎渗透到所有领域.移动机器人是机器人学中的一个重要分支.早在60年代,就已经开始了关于移动机器人的研究.关于移动机器人的研究涉及许多方面,首先,要考虑 ...