首页 > 编程语言 >HPA* (Near Optimal hierarchical Path-finding)算法的效果图

HPA* (Near Optimal hierarchical Path-finding)算法的效果图

时间:2024-05-02 09:11:06浏览次数:32  
标签:路径 Near 效果图 算法 hierarchical 红色 Path HPA

本文中的图全部来自:

https://mohitsharma0690.blogspot.com/2016/01/hierarchical-pathfinding.html



图的说明:

Here is an example of how clusters are created in an open space environment. The white squares represent walkable grids. Non-walkable grid spaces are marked with black (missing here). The nodes marked as grey are part of the abstract graphs. The red lines are the edges in the abstract graph. All of the edges are bidirectional.



使用A* 算法的效果图,从红色点到绿色点寻找路径:

image



使用HPA* 算法后寻找路径的效果图:

image

我们可以看到,最后的HPA* 寻找路径一定在红色线上(不同块之间的路径一定在红色线上,也就是黄色路径一定和部分红色线重合,启始块和目标块的内部路径不在红色线上,这里的分割块就是算法描述中的cluster)


要知道这样一个问题,如果cluster分割块的size过大,也就是分割块过多的情况下,那么HPA* 的寻找路径一定和A* 算法的寻找路径有较大的不同,根据上图我们可以看到,如果红色的网格过于稀疏那么HPA* 算法的黄色线由于必须和部分红色线重合,因此会和原始的A* 算法的黄色线有较大的差别。





标签:路径,Near,效果图,算法,hierarchical,红色,Path,HPA
From: https://www.cnblogs.com/devilmaycry812839668/p/18169931

相关文章

  • [转载] RPATH/LD_LIBRARY_PATH/RUNPATH
    原文地址:https://zhuanlan.zhihu.com/p/534778561rpath和runpath都是用来指定搜索动态链接库的目录的,如果不清楚动态链接库是什么,可见静态库vs动态库。动态链接库(sharedlibraries)作为库并不像静态库一样和可执行文件绑定,而是在运行时加载。但,可执行文件在运行时怎么知道库的......
  • 全景剖析阿里云容器网络数据链路(七):Terway DataPath V2(Terway≥1.8.0)
    作者:余凯前言近几年,企业基础设施云原生化的趋势越来越强烈,从最开始的IaaS化到现在的微服务化,客户的颗粒度精细化和可观测性的需求更加强烈。容器网络为了满足客户更高性能和更高的密度,也一直在高速的发展和演进中,这必然对客户对云原生网络的可观测性带来了极高的门槛和挑战。为......
  • Quick Go To Selected File Path - 快速路径跳转 - vscode 插件推荐
    QuickGoToSelectedFilePath-快速路径跳转-vscode插件推荐差个插件的快捷键是Ctrl+E一直找一个鼠标点就过去的,一直没找到比较通用的,这个算是比较不错的~QuickGoToSelectedFilePathhttps://marketplace.visualstudio.com/items?itemName=duXing.quick-go-to-s......
  • 笔记本1050ti运行DLinear模型遇到的问题
    1、windows没法运行shgitbash可以,但我需要在conda环境中,使用sh运行脚本,所以应该在安装conda后,先配环境变量,然后在gitbash窗口中执行condainitbash,就可以用在bash窗口中通过condaactivate进入conda环境了。2、运行sh,报错加载不到模块看报错最后一行上面的模块,pipuninsta......
  • [题解][2021浙江CCPC] Shortest Path Query
    题目描述输入一张无向图,对于无向图的每条边u,v,w,将u和v转换成二进制后,u是v的前缀。给出q次询问,每次输入s,t,求s到t的最短距离。题解从题目数据而言,n为1e5,m为2e5,显然一般的多源最短路算法无法完成。考虑此题的特殊性质:由于边仅可能从u连向以u为前缀的v,那么若建立一颗以1为根的完......
  • vscode debug: #include errors detected. Please update your includePath
    比如说文件树如下-src-x.cpp-x.hpp那么在x.cpp中直接#include"x.hpp"是没问题的,因为这个按相对路径来说可以直接搜到 但是如果文件树如下-src-x.cpp-head-x.hpp由于x.cpp和x.hpp不在同一个文件夹下,所以需要按相对路径如下#include".......
  • sys.meta_path的作用
    `sys.meta_path`是Python导入系统中的一个关键特性,它是一个列表,包含了所有的元路径查找器(metapathfinders)。这些查找器在导入模块时会被依次查询,以便找到对应的模块。当你在Python中导入一个模块时,解释器会按照以下步骤进行:1.检查`sys.modules`缓存,看看模块是否已经被导......
  • Converge: QoE-driven Multipath Video Conferencing over WebRTC 概略
    这是一片2023sigcomm的文章。论文指出多摄像头(multiplecamera)和高分辨率(highresolution)场景下,视频会议的QoE还有提升空间,而作者将提升QoE的目光转到多路传输(multipath)上。所以总体来看这是一篇利用多路传输来优化视频会议体验的文章。常用的多路协议包括MPTCP,MPQUIC,MPRTP经过......
  • Visual Studio Code 检测到#include 错误,请更新includepath。已为此翻译单元 禁用波
    以上问题的出现是因为visualstudiocode的环境没有配置好在界面中按ctrl+shft+p输入Cconfiguration选择上图蓝色框 在上面红色框填上正确的路径(如果没有这个路径要在https://sourceforge.net/projects/mingw-w64/下载MinGW,具体操作b站有可以去看看照着下载)因为用的是c......
  • path.resolve、path.join、path.posix.join对比分析以及适用场景举例
    path.resolve、path.join、path.posix.join对比分析以及适用场景举例path.resolve、path.join和path.posix.join都是Node.js中用于处理和操作文件路径的方法,但它们各自有特定的功能和使用场景。以下是它们的对比分析和适用场景举例:1.path.resolve([...paths])功能:path.......