A * Pathfinding - я думаю, что он в псевдокоде, нужна проверка - PullRequest
Новая
       41

A * Pathfinding - я думаю, что он в псевдокоде, нужна проверка

1 голос
/ 17 февраля 2012

Они говорят, что взятие того, что кто-то сказал, и повторение этого - лучшая форма проверки основ концепции (понимания). Итак, я читал об 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

1 Ответ

0 голосов
/ 17 февраля 2012

Ну, одна серьезная проблема с вашим псевдокодом и одна незначительная проблема.

Основная проблема:
Когда вы найдете nTile, это может быть уже closed или open,и в вашей реализации - вы игнорируете это и пропускаете это.Однако, если он закрыт или открыт, вам следует проверить, может быть, стоимость пути, которую вы только что нашли, лучше , чем стоимость пути в closed или open, и, если она есть, удалите ее.из closed / open и заново вставьте его в open с новой стоимостью пути.

Незначительная проблема:
Иногда существует более одного целевого узла [существует набор изцелевые узлы, вы ищете путь к одному из них].Таким образом, вместо if targetTile.equals(activeTile) вы можете проверить if heuristicValue(activeTile) == 0 [при условии, что эвристическая функция допустима] или проверить if activeTile is in targetStates.

...