# A* pathfinding not finding shortest path with weird behavior [closed]

The A* pathfinding algorithm works fine most of the time but in some specific cases, it seems to not use the shortest path.

For example,

Legend

• N = Start point
• E = Endpoint
• | = obstacle
• (-) supposed movement path
• = How it moves

• D = move down
• U = move up

         _ _ _ _
|     |
|   | |
N(-)(-)(-)U|E
D         U|
D         U|
D > > > >>U|


End of diagram and assume that all the other paths are blocked and that the three (-) (-) (-) direction is the shortest path to the end. In this specific instance, it chooses to take the longer path represented by >>>>> UUUUU instead of (-)x3.

    func startPathfinding(startPoint:CGPoint, endPoint:CGPoint) {
var layer : TMXLayer = map.layerNamed("World1")
var currentTile = layer.tileAt(startPoint)
var initialPosition = getTileCoordinate(startPoint)//layer.coordForPoint(startPoint) //startPoint
var endPosition = getTileCoordinate(endPoint)//layer.coordForPoint(endPoint)             //endPoint

self.openList = []
self.closedList = []
var tempGScore = 0

insertInOpenSteps(ShortestPathStep(loc: initialPosition))
var nodesProcessed = 0

if isValidTile(startPoint) == false || isValidTile(endPoint) == false {
println("BUG!")
return
}
do {
if nodesProcessed > 3000 {
println("Stopping!")
break
}

var currentStep = openList.objectAtIndex(0) as ShortestPathStep
println(currentStep.position)
openList.removeObjectAtIndex(0)
if CGPointEqualToPoint(currentStep.position, endPosition) {
println("I found a path")
constructPathAndStartAnimationFromStep(currentStep)
var tmpStep: ShortestPathStep! = currentStep
do {
tmpStep = tmpStep.parent
} while tmpStep != nil
self.openList = []
self.closedList = []
break
}
nodesProcessed = nodesProcessed + 1
var step : ShortestPathStep! = ShortestPathStep(loc: adjacentNodes.CGPointValue())
if closedList.containsObject(step)   {
//   step = nil
continue
}
var moveCost = costToMoveFromStep(currentStep as ShortestPathStep, toAdjacentStep: step)

var index = openList.indexOfObject(step)
if index == Foundation.NSNotFound {

step.parent = currentStep as ShortestPathStep
step.gScore = currentStep.gScore + moveCost
step.hScore = computeHScoreFromCoord(step.position, toCoord: endPosition)
insertInOpenSteps(step)

}

else {
step = openList.objectAtIndex(index) as ShortestPathStep

if (currentStep.gScore + moveCost) < step.gScore {

step.gScore = currentStep.gScore + moveCost
openList.removeObjectAtIndex(index)
insertInOpenSteps(step)

}
}
}

} while openList.count > 0

}

var tmp : NSMutableArray = [] // 0 = not walkable 1 = walkable  (left,right,up,down)
var layer : TMXLayer = map.layerNamed("World1")
var position = tileLoc
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 {
p = CGPointMake(position.x - 1, position.y)
}
if right {

p = CGPointMake(position.x + 1, position.y)

}
if up {
p = CGPointMake(position.x, position.y - 1)
}
if down {
p = CGPointMake(position.x, position.y + 1)

}
return tmp
}
func insertInOpenSteps(step: ShortestPathStep) {
var stepFScore = step.fScore()

var count = openList?.count
var i = 0

for i; i < count; i++ {
var test = self.openList.objectAtIndex(i) as ShortestPathStep
if stepFScore <= self.openList.objectAtIndex(i).fScore() {
break
}
}
self.openList?.insertObject(step, atIndex: i)
}
func computeHScoreFromCoord(fromCoord:CGPoint,toCoord:CGPoint) -> Int {

var x = abs(toCoord.x - fromCoord.x)
var y = abs(toCoord.y - fromCoord.y)
var hScore = x + y
return Int(hScore)
}
func costToMoveFromStep(fromStep: ShortestPathStep, toAdjacentStep: ShortestPathStep) -> Int {
return 1
}

• Are you missing an End in you diagram (E)? – Vaillancourt Mar 20 '15 at 20:05
• Edited that error – Wraithseeker Mar 20 '15 at 20:10
• This is an excellent use-case for unit tests... – BlueRaja - Danny Pflughoeft Mar 20 '15 at 20:29
• Some code comments would help. – Anko Mar 20 '15 at 22:08

Cant comment so Ill leave as answer instead. I like the implementation of A* from this page: http://www.redblobgames.com/pathfinding/a-star/introduction.html. It goes step by step on how to build a path finding algorithm from the simplest and gradually increases complexity.

I scanned over your implementation and it is not clear to me where the bug is. But however, you should not use arrays for your openlist and closedlist. Because array.removeAtIndex() and array.getLowestPriority() is a O(n) operation. The openlist should be a priority queue data structure and closeList should be a set or hashmap. Otherwise you will get a big speed hit. The bug you are facing might be due to your openlist not properly returning the lowest value, or perhaps when the goal tile is reached the algorithm did not pick the correct behaviour. I suggest rewrite your function entirely, the A* really isnt that hard, from the link above, it is basically this:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
current = frontier.get()

if current == goal:
break

for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current