algorithm - A* 寻路——我想我已经用伪代码记下了，需要验证

Question

他们说，把别人说的话拿过来，然后重复一遍是验证概念基础(理解)的最佳形式。所以，我一直在阅读有关 A* 的内容并将其翻译成伪代码，我想我明白了。任何人都可以验证和/或提供有关此实现是否有效的提示吗？

对不起，如果这很匆忙，我正在休息;)

openList.ClearTiles
closeList.clearTiles
path.clearTiles

openList.Add startTile

While openList.Count > 0 and PathFound = false
    activeTile = openList.GetTileWithLowestPathCost
    openList.remove activeTile
    closeList.add activeTile

    if targetTile.equals(activeTile)
       pathFound = true
    else
       for each activeTile.neighbors as nTile
           if nTile not in openList and not in closeList and IsMovable
              nTile.parent = activeTile
              nTile.hueristic = computeHeuristic
              nTile.movementCost = computeMovementCost
              nTile.pathCost = nTile.hueristic + nTile.movementCost

              openList.add nTile
           elseif isMovable = false
              closelist.add nTile
           endif
       next
    endif
endwhile

if pathFound = true        
   while activeTile.parent is not nothing
       path.insertAtZero activeTile
       activeTile = activeTile.parent
   endwhile
endif

Answer 1

你的伪代码有一个主要问题和一个小问题。

主要问题:
当您找到nTile 时，它可能处于closed 状态或open 状态，在您的实现中- 您忽略它并跳过它。但是，如果它处于关闭或打开状态，您应该检查您刚刚发现的路径成本是否更好然后是关闭或打开，如果是，则将其从 closed/open 中移除，并使用新的路径成本将其重新插入到 open。

小问题:
有时目标节点不止一个[有一组目标节点，你正在寻找到其中一个的路径]。因此，您可以检查 if targetTile.equals(activeTile) 而不是 if heuristicValue(activeTile) == 0 [假设启发式函数是 admissible] 或检查 activeTile 是否在 targetStates 中。