I have been following this tutorial http://www.raywenderlich.com/4970/how-to-implement-a-pathfinding-with-cocos2d-tutorial to implement the A*pathing which is written in objective C.
My problem is that it never seems to be able to find a path to the ending Location and thus loops forever. I am also using JSTileMap.
My 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)
}
There is an error with your code around here:
var tmpStep: ShortestPathStep! = currentStep
do {
println(tmpStep.gScore)
println(tmpStep.hScore)
} while tmpStep != nil
break
As you are not changing the value of tmpStep at any point then you are never going to be able to determine it is null. Also, you are force unwrapping tmpStep which will cause a runtime error if tmpStep does become nil.
After reading the ray wenderlich guide I recommend the following changes to your code:
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
This should fix your issue.
Hope it helps.
From your source code I can see a number of issues of why the path finding isn't working:
1: as mentioned before, you need to change to these lines:
var tmpStep: ShortestPathStep? = currentStep
do {
println(tmpStep?.gScore)
println(tmpStep?.hScore)
tmpStep = tmpStep?.parent
} while tmpStep != nil
break
2: In your walkableAdjacentTiles function, you need to change this line:
var position = layer.coordForPoint(hero.position)
to
var position = tileLoc
In order to keep updating the adjacency list, otherwise the algorithm just purely looks at one single position and never completes the path.
3: At the beginning of your startPathfinding function, you need to make sure you're clearing the closed and open lists.
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: and finally, you're checking an incorrect contains on this line:
var step : ShortestPathStep! = ShortestPathStep(loc: adjacentNodes.CGPointValue())
if closedList.containsObject(adjacentNodes) {
step = nil
continue
}
This needs to be checking the step, not the adjacency list
for adjacentNodes in adjacentTiles {
var step : ShortestPathStep! = ShortestPathStep(loc: adjacentNodes.CGPointValue())
if closedList.containsObject(step) {
step = nil
continue
}
This should make the necessary changes to make the algorithm work. Let me know if there are any more problems.