推广

JPS寻路算法

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

如上图所示,有两个要素:
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://0291.com.cn/post/56276.html

相关文章

拼多多砍价微信群500人:不仅仅是购物,更是一种社交体验

拼多多砍价微信群500人:不仅仅是购物,更是一种社交体验

你是否还在为拼多多砍价而烦恼?你是否还在一个个添加好友,请求砍价而感到疲惫?拼多多砍价微信群 500 人,为你提供一个全新的购物体验,让你在享受购物的乐趣的同时,也能感受到社交的温暖。 一、拼多多砍价微信群 500 人,让你轻松砍价 在拼多多砍价微信群 500 人中,你可以享受到...

抖音小店选品新技巧

抖音小店选品新技巧

做电商,选品是重中之重。 好产品自带流量,就算什么也不做,也能有自然流量出单;达人带货合作的成功率也更高。 那怎么才能选出这种有爆款潜质,需求飙升的产品呢? 下面要分享的这个抖音小店选品技巧,就可以让我们找到现在搜索量和需求量都在飙升的产品。 把这些产品上架到我们的小店当中,就...

淘数据怎么看热搜词(怎么查淘宝热搜关键词)

淘数据怎么看热搜词(怎么查淘宝热搜关键词)

可以打开你的淘宝主页,点开你的搜索框你会发现下面有一排关键词,这些都是热搜的关键词,在PC端上,你还可以点击更多按钮。...

2020年Q1抖音媒体广告投放分析!

2020年Q1抖音媒体广告投放分析!

抖音DAU已超过4亿,较去年同期的2.5亿,增长了60%,可见增长势头依然强劲。截至今年1月份,抖音用户男女比例趋于均衡,有61%的用户为35岁以下年轻群体,占比相较于去年有所下降。自去年开始抖音已开始向三四线及以下城市扩展市场,今年1月份一二线城市用户占比降至39%(2018.07占...

干货分享(干货分享是什么意思)

干货分享(干货分享是什么意思)

至少要保证满足这四大要素:“1. 分析自己的核心优势,选择网站建设的方向;2.了解当前的趋势,顺势而为往往能让自己占领至高点;3. 规划团队,计划团队成员的任务。4. 网站营销策划”。 1、分析自身企业所具备的优势,再去选择网站建设的方向! 做网站是需要有方向有目标的,否则会越做越迷茫。所以分析...

如何才能制作出符合大众用户审美的网站来。

如何才能制作出符合大众用户审美的网站来。

互联网发展的速度越来越快,随之企业进行营销型网站建设的标准也就越来越高,而越高的网站制作标准也就意味着网站的质量越上乘,能够被用户喜欢的几率也就越大,最终能够取得的成效也越高。这是由于网站的质量上升了,使得大众用户的审美观不断提升,相较之下,用户自然会更喜欢,更愿意使用优秀的网站。所以,网站建设点瑞...

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

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