推广

JPS寻路算法

iseeyu2年前 (2024-02-22)推广138

如上图所示,有两个要素:
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或者路径点寻路方式

附上一张对比图:

扫描二维码推送至手机访问。

版权声明:本文由西安泽虎代运营发布,如需转载请注明出处。

转载请注明出处https://www.0291.com.cn/post/56276.html

相关文章

支付宝生肖卡怎么玩(支付宝里面我的生肖怎么玩)

支付宝生肖卡怎么玩(支付宝里面我的生肖怎么玩)

生肖卡可以在集五福的过程中随机发放,各个渠道都有机会获得,例如随机福卡、AR扫福、蚂蚁森林、蚂蚁庄园、摇一摇、生活频道、支付宝搜品牌、福气店抽奖等等,可以在集福卡的过程中获得到生肖卡。...

我来分享网站设计师如何揣摩客户的设计要求。

我来分享网站设计师如何揣摩客户的设计要求。

不同的人有不同的审美,有不同的设计要求,对于网站来说,在面对每一个的页面设计中最难的两个方面是揣摩客户的设计要求以及寻找设计思路,当然了,网站设计的两点也是充分体现出设计师实战能力的两大参考点。 一、有一定想法的客户 其实这类客户也非常好“伺候”,他们会主动把想法告诉设计师,比如颜色的...

营销方案案例范文: 16个经典营销案例,让你拥有真正的营销 ...

营销方案案例范文: 16个经典营销案例,让你拥有真正的营销 ...

方案案例范文: 16个经典营销案例,让你拥有真正的营销《上》一、卖酒与狗的故事唐朝有一个卖酒的人,酿制的酒香味醇厚,做生意也很诚实,待客人殷勤周到,服务做得很好,店门外的酒字旗迎风招展。可问题是酒就是卖不出去,卖不掉的酒,放的时间一长就变酸了。卖酒的人很是不解,就是请教长辈...

【园区招商】招商工作流程

【园区招商】招商工作流程

点击上方蓝字,关注我们全文2643字,阅读时长约8分钟 现阶段,园区同质化竞争异常激烈,很多从事产业园的朋友都普遍会有以下两点体会:1、新园区设计越来越漂亮、设施越来越完备,价格还和老园区差不多,原有被不断蚕食。2、园区招商对人的要求越来越高,很多业绩一般、或者业务素养不高...

通过快手引网赚粉3招克敌制胜 短视频引网赚粉方法在这里。

通过快手引网赚粉3招克敌制胜 短视频引网赚粉方法在这里。

当今社会,互联网成为一种信息传递的载体,我们刚刚接触到网络时,无外乎只是文字形式出现,到后来文字照片形式,但是从几百到1000多文字对于阅读障碍懒惰的人极为不方便。 直到几年前智能手机的出现,才能让每个人通过录像。记录到精彩瞬间。 短视频的出现应该在17年9月份,笔者在朋友圈看到火山小视频...

抖音上热门规则及攻略!

抖音上热门规则及攻略!

  每个流量平台,包括淘宝、微信、微博、抖音,平台游戏规则都是不一样的,不懂游戏规则是玩不了的。 特别是想在这些平台上做营销,如果不熟悉和懂得利用平台规则,盲目操作,肯定不会有任何效果。 因为这些大平台都是比较个人营销行为的,很简单的道理:这是我的地盘,打广告做营销必需先通...

现在,非常期待与您的又一次邂逅

我们努力让每一部企业宣传片和抖音短视频成为商业大片