擅长:python、mysql、java
<p>似乎这个实现是不正确的,因为它正在移动到距离目标最近(就像乌鸦一样)的被检查的单元格中还没有的<em>,而它应该尝试<em>并在找到障碍物时撤销路径以找到最佳障碍物。请看维基百科上的<a href="https://en.wikipedia.org/wiki/File%3aAstar_progress_animation.gif" rel="nofollow">nice animation</a>来了解这个想法。在</p>
<p>这里的问题是关于如何计算<code>cell.f</code>,也许你在做微积分时没有加上当前单元格的分数,一般来说A*应该采取步骤<a href="http://i.imgur.com/7dxdFsb.png" rel="nofollow">marked in red here</a>并生成类似这样的次优路径。在</p>
<p>由于空间被划分为离散的单元,当连续世界中的最佳路径(总是乌鸦在飞)正好在两个离散的移动之间时,它会尽可能地用这个奇怪的路径来近似它。在</p>
<p>我认为有两种方法:</p>
<ol>
<li>修正算法(<a href="https://en.wikipedia.org/wiki/A%2a_search_algorithm#Pseudocode" rel="nofollow">here the pseudocode</a>)为每个计算的单元格保持正确的距离值(在粘贴的单元格中没有关于如何计算<code>cell.f</code>的信息)。在</li>
<li>使用Djikstra<strong>Djikstra</strong>,它应该很容易实现,只需对当前算法做一些修改。事实上,A*只是它的一个优化版本。在</li>
</ol>