Fast Grid-Based Path Finding for Video Games
Fast Grid-Based Path Finding for Video Games
复制标题
视频游戏基于网格的快速路径查找
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
R. Lawrence
中科院分区：
文献类型：
--
作者：
William Lee;R. Lawrence
在许多视频游戏和虚拟世界中，需要基于网格的路径查找来移动代理。随着地图大小和代理数量的增加，重要的是开发在内存和时间上有效的路径查找算法。在这项工作中，我们提出了一个算法称为DBA*，使用预先计算的路径数据库，以减少时间来解决搜索问题。当使用DragonTM的基准地图进行评估时，DBA* 需要更少的内存和搜索时间，并且执行比同类实时搜索算法更少的预计算。此外，它的次优性小于3%，这比DragonTM中使用的PRA* 实现更好。
Grid-based path finding is required in many video games and virtual worlds to move agents. With both map sizes and the number of agents increasing, it is important to develop path finding algorithms that are efficient in memory and time. In this work, we present an algorithm called DBA* that uses a database of pre-computed paths to reduce the time to solve search problems. When evaluated using benchmark maps from Dragon AgeTM, DBA* requires less memory and time for search, and performs less pre-computation than comparable real-time search algorithms. Further, its suboptimality is less than 3%, which is better than the PRA* implementation used in Dragon AgeTM.