途径动态寻路算法 [英] Approaches to a Dynamic Pathfinding Algorithm

问题描述

我的A *实现非常适用于我的静态环境。 如果我现在想用一个充满活力的环境中工作，即一定的费用之间，而我们是从开始到结束遍历我的节点改变。

My A* implementation works well for my static environment. If I would now like to work with a dynamic environment, i.e. certain costs between my nodes change while we are traversing from the start to the finish.

这是我的阅读到目前为止，我已经找到了LPA *，D *和D *精简版的算法，可以帮助我。那么我的最坏的情况将是实现所有，看看有什么效果最好。

From my reading so far I have found the LPA*, D* and D* Lite algorithm that could help me. Well my worst case scenario would be to implement all and see what works best.

是否有比较这些算法的性能做了任何研究吗？ 我读了这些文章至今只专注于单一算法的时间和因为他们的实验环境不同，很难做一个比较。

Is there any research done on comparing the capabilities of these algorithms? The papers that I have read so far just focus on a single algorithm at a time and since their experiment environments are different, it is hard to make a comparison.

**一些背景资料：我使用C ++和我的环境是一个三维场景，我的搜索​​图被重新presented使用navmeshes

**Some background information: I'm using C++ and my environment is a 3d scene with my search graph being represented using navmeshes.

推荐答案

它已经有一段时间，因为你问，所以也许你已经有时间去尝试他们... ...但是这是非常值得的D * - 精简版纸（http://www.aaai.org/Papers/AAAI/2002/AAAI02-072.pdf）有一节末，实验结果的，与LPA性能比较*，D *和A *。

It's been some time since you asked, so maybe you've already had time to try them all... But for what it's worth, the D*-Lite paper (http://www.aaai.org/Papers/AAAI/2002/AAAI02-072.pdf) has a section at the end, Experimental results, comparing performance with LPA*, D* and A*.

这篇关于途径动态寻路算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！