0
\$\begingroup\$

NOTE I have read through this thread and have tried the implemented answer

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)
        closedList.addObject(currentStep)
        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
        }
        var adjacentTiles = walkableAdjacentTiles(currentStep.position)
        for adjacentNodes in adjacentTiles {
            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

    }

    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 = 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)
        tmp.addObject(NSValue(CGPoint: p))
    }
    if right {

         p = CGPointMake(position.x + 1, position.y)
        tmp.addObject(NSValue(CGPoint: p))

    }
    if up {
        p = CGPointMake(position.x, position.y - 1)
        tmp.addObject(NSValue(CGPoint: p))
    }
    if down {
        p = CGPointMake(position.x, position.y + 1)
         tmp.addObject(NSValue(CGPoint: p))

    }
    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
    }
\$\endgroup\$

closed as off-topic by bummzack, BlueRaja - Danny Pflughoeft, Anko, congusbongus, MichaelHouse Mar 25 '15 at 20:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about debugging a problem in your project must present a concise selection of code and context so as to allow a reader to diagnose the issue without needing to read all of your code or to engage in extensive back-and-forth dialog. For more information, see this meta thread." – bummzack, BlueRaja - Danny Pflughoeft, Anko, congusbongus, MichaelHouse
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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 
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.