ios - 快速实现中的 A*路径

Question

我一直在关注这个教程http://www.raywenderlich.com/4970/how-to-implement-a-pathfinding-with-cocos2d-tutorial实现用 Objective C 编写的 A*pathing。

我的问题是，它似乎永远无法找到到达结束位置的路径，因此永远循环。我也在使用 JSTileMap。

我的类(class)

class ShortestPathStep: NSObject {
    var gScore: Int!
    var hScore: Int!
    var position: CGPoint!
    var parent: ShortestPathStep?

    init(loc: CGPoint) {
        super.init()
        gScore = 0
        hScore = 0
        position = loc

        parent = nil


    }
    func isEqualPath(other: ShortestPathStep) -> Bool {
        return CGPointEqualToPoint(self.position!,other.position!)
    }

    required init?(coder aDecoder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }
   func fScore() -> Int {
        return self.gScore! + self.hScore!
    }
}
 func startPathfinding(startPoint:CGPoint, endPoint:CGPoint) { // take in values of CGPoint not tiled coordinate system
    var layer : TMXLayer = map.layerNamed("World1")
    var currentTile = layer.tileAt(hero.position)
    var initialPosition = layer.coordForPoint(currentTile.position)
    var endPosition = layer.coordForPoint(endPoint)
    var pathFound = false
    //self.openList = []
    //self.closedList = []
    insertInOpenSteps(ShortestPathStep(loc: initialPosition))
    do {
            println(openList.count)
            var currentStep = openList.objectAtIndex(0) as ShortestPathStep
          //println(currentStep)
            closedList.addObject(currentStep)
            openList.removeObjectAtIndex(0)
            println(currentStep.position)
            if CGPointEqualToPoint(currentStep.position, endPosition) {
                println("I found a path")
                // this part never runs
                pathFound = true
                openList = []
                closedList = []
                var tmpStep: ShortestPathStep! = currentStep
                do {
                    println(tmpStep.gScore)
                    println(tmpStep.hScore)
                } while tmpStep != nil
                break
            }
            var adjacentTiles = walkableAdjacentTiles(currentStep.position)
            for adjacentNodes in adjacentTiles {
                var step : ShortestPathStep! = ShortestPathStep(loc: adjacentNodes.CGPointValue())
                println(adjacentNodes.CGPointValue())
                if closedList.containsObject(adjacentNodes) {
                    step = nil
                    continue
                 }
               var moveCost = costToMoveFromStep(currentStep as ShortestPathStep, toAdjacentStep: step)
               var index = openList.indexOfObject(step)
               if index == NSNotFound {
                    step.parent = currentStep as ShortestPathStep
                    step.gScore = currentStep.gScore + moveCost
                    step.hScore = computeHScoreFromCoord(step.position, toCoord: endPosition)
                    insertInOpenSteps(step)
                    step = nil
                }

               else {
                    step = openList.objectAtIndex(index) as ShortestPathStep
                    if (currentStep.gScore + moveCost) < step.gScore {
                        step.gScore = currentStep.gScore + moveCost
                        insertInOpenSteps(step)
                        openList.removeObjectAtIndex(index)
                        step = nil
                    }
                }
            }

            println(openList.count)
        } while openList.count > 0

        if CGPointEqualToPoint(initialPosition, endPoint) {
           println("You are there already")
        }
}
func computeHScoreFromCoord(fromCoord:CGPoint,toCoord:CGPoint) -> Int {
        // Here we use the Manhattan method, which calculates the total number of step moved horizontally and vertically to reach the
        // final desired step from the current step, ignoring any obstacles that may be in the way
        return abs(Int(toCoord.x - fromCoord.x)) + abs(Int(toCoord.y - fromCoord.y))
    }

    func isValidTile(location:CGPoint) -> Bool {
        var node = self.nodeAtPoint(location)
        if node.name == "collision" {
            return true
        }
        else {
            return true
        }
    }

    func walkableAdjacentTiles(tileLoc:CGPoint) -> NSMutableArray {
        var tmp : NSMutableArray = [] // 0 = not walkable 1 = walkable  (left,right,up,down)
        var layer : TMXLayer = map.layerNamed("World1")
        var position = layer.coordForPoint(hero.position)
        var right: Bool = isValidTile(CGPoint(x: position.x + 1, y: position.y))
        var left: Bool = isValidTile(CGPoint(x: position.x - 1, y: position.y))
        var up: Bool = isValidTile(CGPoint(x: position.x , y: position.y + 1))
        var down: Bool = isValidTile(CGPoint(x: position.x, y: position.y - 1))

        var p : CGPoint
        if left {
            var p = CGPointMake(position.x - 1, position.y)
            tmp.addObject(NSValue(CGPoint: p))

          //  layer.removeTileAtCoord(p)
        }
        if right {
            var p = CGPointMake(position.x + 1, position.y)
            tmp.addObject(NSValue(CGPoint: p))

         //   layer.removeTileAtCoord(p)
        }
        if up {
            var p = CGPointMake(position.x, position.y + 1)
            tmp.addObject(NSValue(CGPoint: p))

           // layer.removeTileAtCoord(p)
        }
        if down {
            var p = CGPointMake(position.x, position.y - 1)
             tmp.addObject(NSValue(CGPoint: p))

         //   layer.removeTileAtCoord(p)
        }
        return tmp

    }
    func insertInOpenSteps(step: ShortestPathStep) {
        var stepFScore = step.fScore()
        var count = openList.count
        var i = 0
        for i; i < count; i++ {
            if stepFScore <= self.openList.objectAtIndex(i).fScore() {
                break
            }
        }
        self.openList.insertObject(step, atIndex: i)
    }

Answer 1

这里的代码有一个错误:

var tmpStep: ShortestPathStep! = currentStep
do {
    println(tmpStep.gScore)
    println(tmpStep.hScore)
} while tmpStep != nil
break

由于您在任何时候都没有更改 tmpStep 的值，因此您永远无法确定它是否为空。此外，您正在强制展开 tmpStep，如果 tmpStep 变为 nil，这将导致运行时错误。

阅读 ray wenderlich 指南后，我建议对您的代码进行以下更改:

var tmpStep: ShortestPathStep? = currentStep;
do {
    println(tmpStep?.gScore)
    println(tmpStep?.hScore)
    tmpStep = tmpStep?.parent // Changes the value of tmpStep to traverse the list. 
} while tmpStep != nil

这应该可以解决您的问题。

希望对您有所帮助。

---

更新:

从您的源代码中，我可以看到路径查找不起作用的许多问题:

---

1:如前所述，您需要更改为以下行:

var tmpStep: ShortestPathStep? = currentStep
do {
    println(tmpStep?.gScore)
    println(tmpStep?.hScore)
    tmpStep = tmpStep?.parent
} while tmpStep != nil
break

---

2:在您的 walkableAdjacentTiles 函数中，您需要更改此行:

var position = layer.coordForPoint(hero.position)

到

var position = tileLoc

为了不断更新邻接表，否则算法只看一个位置，永远不会完成路径。

---

3:在您的startPathfinding 函数开始时，您需要确保清除关闭和打开列表。

func startPathfinding(startPoint:CGPoint, endPoint:CGPoint) { // take in values of CGPoint not tiled coordinate system
    self.openList.removeAllObjects()
    self.closedList.removeAllObjects()
    // Rest of code here.

---

4:最后，您在这一行检查了不正确的包含:

var step : ShortestPathStep! = ShortestPathStep(loc: adjacentNodes.CGPointValue())

    if closedList.containsObject(adjacentNodes) {
        step = nil
        continue
    }

这需要检查步骤，而不是邻接表

for adjacentNodes in adjacentTiles {
    var step : ShortestPathStep! = ShortestPathStep(loc: adjacentNodes.CGPointValue())

    if closedList.containsObject(step) {
        step = nil
        continue
    } 

---

这应该进行必要的更改以使算法正常工作。如果还有问题，请告诉我。