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

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

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

刘大瑞,冯 镍

()四川大学计算机学院,四川成都610065

摘 要:为游戏中非玩家控制角色(设计自动寻路算法是人工智能研究领域的一大热点。首先模拟多目标游戏NPC)

然后以路径长度、路径安全程度和对游戏角色的耗费为评估目标,提出了基于多目标遗传算法的地图作为实验平台,

算法虽然比A*算法实时性差,但其对地图全局有很好的把握,在多目标环境下,其路径规划方法。经过实验验证,得到的路径存在明显的全局最优。

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

()中图分类号:TP312     文献标识码:A     文章编号:167278002014001004902---

的最优路径选择。

0 引言

随着游戏产业的快速发展,对游戏质量的要求逐步上玩家希望看到趣味性足、挑战性强的高质量游戏。为了升,

]1

(提高游戏质量,大量游戏引入了非玩家控制角色[NPC)

1 多目标路径规划遗传算法

游戏中的非玩家控制角色需要智能路径规划算法,为其提供最优行动路线,让其看上去更具智能性。然而,每不存在一种智能路径种智能路径规划算法都存在局限性,

规划算法适用所有游戏。然而,目前的计算机游戏种类众多,这导致游戏地图的多样性和复杂度较高,直接在游戏地图上测试寻路算法难度较大,而且测试结果不具有代表性

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

与玩家进行交互,以提高游戏的可玩性和真实性。因此,NPC的行为研究成为游戏设计者关心的重要因素。而在

游戏中,主要就是自主寻路,NPC的行为除与玩家交互外,其所选路径的质量决定其自身的智能性和游戏的真实性。

对于游戏N提出过许多方PC智能路径规划的研究,

2,3]4]

、、主要有A*算法及其改进算法[遗传算法[蚁群法,

5]6]

算法[和神经网络方法[等。但在实际应用中,游戏设计

这是由其较高的正确率和较好的实者普遍选择A*算法,

7]

随着游戏地图[的多样化,仅仅用路时性决定的。但是,

游戏地图中通常还需要径长短去评估路径质量是不够的,

考虑路径的安全性、路径的耗费等多个方面。在此情况由此诞生了许多不同的方法。下,A*算法就变得不适用,

8]

,其中,孙纯哲提出了双蚁群交叉算法[但该方法未考虑[],实时性差。此外,连续障碍物,XiaoJZ.Michalewicz9提 

图1 地图表示方法

综合以上原因,打算使用笔者设计的多目标地图编辑器进行游戏地图模拟,提供可操作的测试环境。首先,给出待测试地图组成元素,鉴于游戏场景的复杂性和多样选择6种地形作为模拟测试地图组成元素,其分别是性,

道路、障碍物、树林、深水、浅水和炮台;其次,由上面介绍的地形特性可看出,角色寻路需要考虑3个目标,以下给出对各目标的定义。

定义1:路径长度,即游戏角色从起点到终点走过的栅格数。使用

k1-

出了线性加权的改进A*算法,其只是将多个目标进行简单加权相加,得到启发函数,故该方法存在主观性和随意本文提出了一种多目标遗传算法的路性。针对以上情况,径规划方法。

本文为游戏中的N提出了一种多目标智能PC寻路,

并将其与传统寻路算法进行对比,突出其路径规划算法,

在游戏中智能自动寻路的优点。本文使用基于多目标的遗传算法优化路径,同时引入帕累托最优解集

[10]

作为寻

在综合考虑多个寻路目标平衡的基础上,获得满路结果,

足条件的最优解集。最后,从解集中,筛选满足游戏情景

fp)=1(

∑|nn

i=1

ii1+

()1

  表示所走过栅格总数。

,作者简介:刘大瑞(男,四川大学计算机学院硕士研究生,研究方向为数字娱乐与人机交互。1987-)

你可能喜欢

  • 遗传算法多目标优化
  • 多目标规划模型
  • 多目标规划
  • 遗传算法多目标优化matlab
  • 多目标规划应用实例

基于多目标遗传算法的游戏路径规划研究_刘大瑞相关文档

最新文档

返回顶部