吴拥民,张 斌

(1.闽江学院计算机科学系,福州350108;2.网龙网络有限公司程序研发部,福州350003)

虚拟场景中有宽度物体移动路径的优化方法

吴拥民1,2,张 斌2

(1.闽江学院计算机科学系,福州350108;2.网龙网络有限公司程序研发部,福州350003)

提出一种虚拟场景中有宽度物体移动路径的优化方法,在地图掩码数据经过寻路算法搜索后,得到一组连续路径节点组成的节点集,从起始节点出发,沿着路径节点找出离起始节点最远且没有障碍物遮挡的可见节点,作为下一个起点,循环往复直至节点集的终止节点,并顺序连接这些可见节点,即可得到优化路径。通过合并节点集中的多余节点,使路径更平滑,从而减少物体移动过程中改变方向的次数,解决有宽度物体无法通过狭窄通道后,须重新计算路径的问题,达到了更好的用户体验效果。

虚拟场景;寻路算法;优化方法;有宽度物体;最远可见节点;节点合并

1 概述

随着电子游戏的不断发展,在虚拟的游戏场景中,经常需要实现虚拟物体从一点向另一点移动的功能。在该过程中,要判断是否有可行路线,以及最优路线选择等,这便是寻路过程。寻路算法的基本思路就是图的遍历算法与最短路径算法,遍历算法分为广度优先搜索[1]与深度优先搜索[2],最短路径算法分为非启发式的Dijkstra搜索[3]与启发式的A*搜索[4]。

启发式的A*搜索算法被广泛用于电子游戏中。文献[5]介绍了该算法在网络游戏中的具体实现方法。文献[6]在启发式的A*搜索算法基础上,以Bresenham算法获取直线路径的节点集合,对A*搜索算法的寻路效率提高极为有限。……