1.强迫邻居:
就是指某个节点(x)上下左右有障碍,在由某方向经过这个节点的时候,如果有方向的分量垂直于障碍的方向,则在障碍一侧的斜向点就是节点(x)的强迫邻居
如上图所示,有两个要素:
a.带有搜索方向(剪头)
b.带有障碍(上下左右都行)
private Dir HaveStrictNeigh(Vector2 cur, Dir dir)
{
bool c1, c2;
switch (dir)
{
case Dir.Left:
c1 = !IsValidPos(MoveDir(cur, Dir.Up)) && IsValidPos(MoveDir(cur, Dir.UpLeft))&& IsValidPos(MoveDir(cur, Dir.Left));
c2 = !IsValidPos(MoveDir(cur, Dir.Down)) && IsValidPos(MoveDir(cur, Dir.DownLeft))&& IsValidPos(MoveDir(cur, Dir.Left));
if (c1 && c2)
{
return Dir.Left;
}
else if (c1)
return Dir.UpLeft;
else if (c2)
{
return Dir.DownLeft;
}
break;
case Dir.Up:
2.跳点
跳点需要满足下面三个条件之一:
a.节点是寻路的起点/终点
b.节点至少有一个强迫邻居
c.如果父节点在斜方向(意味着这是斜向搜索),节点的水平或垂直方向上有满足条件a,b的点
举个例子:
黄色节点的父节点是在斜方向,其对应分解成向上和向右两个方向,因为在右方向发现一个蓝色跳点,因此黄色节点也应被判断为跳点
(黄色点为起点,蓝色点为跳点)
寻路流程:
1.openlist取一个权值最低的节点,然后开始搜索
2.搜索时先进行 直线搜索 (上下左右四个方向搜索,直到出现跳点或者到边界),
3.再进行 斜向搜索 (四个斜方向搜索,只前进一步),如果有跳点就加入openlist,知道当前方向完成搜索。
4.如果斜方向没有出现跳点或者到边界,就用进一步的斜点,在直线搜索+斜向搜索,直到所有方向都完成
5.从openlist权值最低的节点进行搜索,直到openlist为空或者找到重点
_和A 相比,优缺点:_*
1.使用JPS算法比A 更快(绝大部分地图),内存占用更小,因为openlist少了很多节点(最差的情况和A
一样,最差的是每个障碍都不连续,中间都有缝隙,这样所有地方都是跳点了)
2.只适用于网格节点类型,不支持Navmesh或者路径点寻路方式
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。