• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Intelligence and AI in Games, IEEE Transactions on >Optimization Using Boundary Lookup Jump Point Search
【24h】

Optimization Using Boundary Lookup Jump Point Search

机译：使用边界查找跳转点搜索进行优化

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Cache-based path-finding algorithms lose much of their advantage in dynamic environments where fast online search algorithms are required. Jump point search (JPS) is such a fast algorithm. It works by eliminating most map nodes from evaluation during path expansion. Boundary lookup jump point search (BL-JPS) is a modification that improves the speed of JPS. BL-JPS records the positions of obstacle boundaries and uses these via direct lookup to eliminate much of the iteration involved in searching for jump points in the JPS algorithm. Two sets of experiments are presented, demonstrating the effects of BL-JPS in both static and dynamic environments. The effects of different approaches to cache rebuilding for JPS+ in dynamic environments are also evaluated. Results show that BL-JPS is generally much faster than JPS. It is slower than JPS+ in static environments, but in dynamic environments, BL-JPS outperforms JPS+ for a single search. When multiple paths are searched, the effects of cache rebuilding gradually dominate the effects of search speed, resulting in JPS+ again becoming faster. However, combining JPS+ with BL-JPS provides a very fast path-finding algorithm (BL-JPS+) that outperforms JPS+ over a range of map types and numbers of paths searched.
机译：在需要快速在线搜索算法的动态环境中，基于缓存的路径查找算法失去了很多优势。跳点搜索（JPS）是一种快速的算法。它通过在路径扩展期间从评估中消除大多数地图节点来工作。边界查找跳跃点搜索（BL-JPS）是一种改进，可以提高JPS的速度。 BL-JPS记录障碍物边界的位置，并通过直接查找使用这些障碍物，从而消除了JPS算法中搜索跳跃点所涉及的许多迭代。提出了两组实验，演示了BL-JPS在静态和动态环境中的效果。还评估了动态环境中JPS +的不同缓存重建方法的效果。结果表明，BL-JPS通常比JPS快得多。在静态环境中，它比JPS +慢，但是在动态环境中，对于一次搜索，BL-JPS优于JPS +。当搜索多个路径时，缓存重建的影响逐渐主导了搜索速度的影响，从而导致JPS +再次变得更快。但是，将JPS +与BL-JPS结合使用可提供一种非常快速的路径查找算法（BL-JPS +），该算法在一系列地图类型和搜索的路径数量上胜过JPS +。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号