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中的路径成本更好，如果是，从closed/open中删除它，然后用新的路径成本将它重新插入到open中。

次要问题：

有时有多个目标节点有一组目标节点，您正在寻找通向其中之一的路径。所以你可以选择if heuristicValue(activeTile) == 0 assuming the heuristic function is [admissible] 或者if activeTile is in targetStates，而不是if targetTile.equals(activeTile)。