Heath's Blog

There is no end, it is just the beginning! - A Game Developer's Notes

解决A*寻路中边缘行走问题

     用碰撞体来约束世界范围已经用得很广泛了,玩家与世界边缘的交互问题也容易用碰撞面的法线和玩家朝向来解决。然而对于一个基于A* PathFinding的游戏,貌似还没有人去考虑和解决这个问题。最初考虑这个问题,是因为游戏中加入了AWSD的移动方式,当碰到阻挡就静止不动了,加上有时阻挡刷得与场景不太贴合,造成玩家在移动上的不爽快。考虑下图的情况,蓝色三角是角色,红色线段给出了前进方向和终点(游戏中配置为角色朝向上5m处)。

Image(9)[6]

     我想了两种方案,最初的方案灵感来自光线反射,如下图所示。

Image(10)

     因为阻挡格子是轴对齐的,通过法向量n可以得到b点的反射向量e'-o,将|e'-o|限定在一个固定值,此时如果e'不在阻挡里面,就将它作为新的终点。该方案的实验结果不太令人满意,当角色离阻挡较近时断续感太明显,因为|e' - b|的长度较短。另外它不能处理e'在阻挡里的情况,被卡住不动的概率依然较大。

     第二种方案是根据移动趋向在一个轴向找一个可达试探点,然后用限制了搜索空间(搜索节点在50以内)的A*算法找到一条到试探点的路径,如下图。

Image(11)

     设diff_x = 终点x - 起点x,diff_y = 终点y - 起点y,当diff_x > diff_y,认定为趋向x方向上移动,在这种情况下在终点y轴向上±10个格子内去找到一个最接近终点的无阻挡点(称它为可达试探点)。由于试探点与玩家当前点极有可能是直线不连通的,而且它们不可能太远,所以使用了一个将搜索节点个数限制在50以内A*来得到一条路径。该方案大部分情况都能在边缘找到合理点,但如果玩家垂直面朝阻挡内移动且不能在限制搜索范围内找到可达点,角色就会卡住不动,这种情况就只能让玩家自己调整一下朝向了。

posted on 2013-05-04 23:49 Heath 阅读(1535) 评论(0)  编辑 收藏 引用 所属分类: Game Development


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理