Broken A* Algorithm, could use some help

[pikuchan]

All right, so I've got a mostly working, partially correct version of the A* pathfinding algorithm that I have been working on. I realize that it's not fully complete yet, but I'm having some trouble. Currently, everything works almost perfectly. The algorithm is getting applied to an enemy to find the path to a player. The world is a procedurally generated dungeon with rooms and hallways. All of the tiles are marked as "walkable" or not within my tile map that is generated. It seems like if the enemy has to cross over an axis, the game enters an infinite loops and crashes once it consumes most of my memory. For example, if the pathfinding requires the enemy to go down, and then back up. For the life of me, I cannot figure out what I am doing wrong. Relevant code is pasted below, any help would be appreciated.

Code: Select all

function AStarPathfinding(originalMap, pointA, pointB)
  --extract the xy positions from the tables passed in
  local column1 = pointA.x
  local column2 = pointB.x

  local row1 = pointA.y
  local row2 = pointB.y

  local targetReached = false
  local route = {}

  --initialize our map
  local pathMap = InitPathFindingMap(originalMap)

  pathMap[row1][column1].pfValue = "open"
  local lowestFPoint = { row = row1, column = column1 }

    repeat

      --love.window.showMessageBox("Lowest F Main Initial Value", lowestFPoint.row .. " " .. lowestFPoint.column, "error")
      pathMap, lowestFPoint = MarkSurroundingOpen(pathMap, row1, column1, row2, column2)

      if pathMap[lowestFPoint.row][lowestFPoint.column].walkable == false then
        --love.window.showMessageBox("Unwalkable path found", lowestFPoint.row .. " " .. lowestFPoint.column, "error")
      end


      pathMap[lowestFPoint.row][lowestFPoint.column].pfValue="closed"
      table.insert(route, lowestFPoint)

      row1 = lowestFPoint.row
      column1 = lowestFPoint.column

      if (lowestFPoint.row == row2) and (lowestFPoint.column == column2) then
        targetReached = true
      end
    until targetReached == true

  return pathMap, route
end

Code: Select all

function InitPathFindingMap(originalMap)

  local modifiedMap = {}

  for x=1, #originalMap do
    modifiedMap[x] = {}
  end

  for row=1, #originalMap do
    local fullRow = originalMap[row]
    mapWidth = #fullRow
    for column=1, #fullRow do
      modifiedMap[row][column] = { value = originalMap[row][column].value, walkable = originalMap[row][column].walkable, pfValue="", parentRow=0, parentColumn=0, f = 0, g = 0, h = 0}
    end
  end

  return modifiedMap
end

Code: Select all

function MarkSurroundingOpen(map, row, column, row2, column2)
  local lowestF = 10000
  local lowestFPoint = {row = row, column = column}

  for colModifier = -1, 1 do
    for rowModifier = -1, 1 do
      if (rowModifier == 0) and (colModifier == 0) then
        local GValueToAdd = 0

      else
        local GValueToAdd = 0
        local HValue = 0

        local newColumn = column + colModifier
        local newRow = row + rowModifier
        --local lowestFPoint = {}

        map = MarkYXAsOpen(map, newRow, newColumn, row, column)

          if (rowModifier == 0) or (colModifier == 0) then
            GValueToAdd = 10
          else
            GValueToAdd = 14
          end

          local parentG = map[row][column].g

          map[newRow][newColumn].g = parentG + GValueToAdd
          map[newRow][newColumn].h = CalculateHValue(newColumn, column2, newRow, row2)
          map[newRow][newColumn].f = map[newRow][newColumn].g + map[newRow][newColumn].h

          if map[newRow][newColumn].walkable == true then
            if map[newRow][newColumn].f < lowestF then
              lowestF = map[newRow][newColumn].f
              lowestFPoint = { row = newRow, column = newColumn }
              --love.window.showMessageBox("Lowest F Opener", lowestFPoint.row .. " " .. lowestFPoint.column, "error")
            end
          end
      end 

    end 
  end  
    return map, lowestFPoint
end --end function

Code: Select all

function CalculateHValue(aX, bX, aY, bY)
  local hValue = 0


    hValue = hValue + math.abs(aX - bX)

    hValue = hValue + math.abs(aY - bY)


  hValue = hValue * 10

  return hValue
end

Code: Select all

function MarkYXAsOpen(map, row, column, prow, pcolumn )
  --love.window.showMessageBox("Mark as open hit", row .. column, "error")

  if map[row][column].walkable ==true and map[row][column].pfValue~="closed" then
    map[row][column].pfValue="open"
    map[row][column].parentColumn = pcolumn
    map[row][column].parentRow = prow
  else

  end

  return map
end

[pgimeno]

Could you maybe paste a simple self-contained .love demonstrating the problem? Turning your snippets into a working program in order to analyse and debug it is something I doubt anyone will try.

[bobismijnnaam]

The only thing that really stands out to me is that your algorithm runs until it finds a path. However if there isn't a path it has no way to terminate (except maybe the error message you have commented out - but that would only pause it for one iteration; after that, it would just continue). The rest of your code seems fine (as far as I can tell, anyway). Have you thought about the case when there is no path?

Edit:
Also, maybe it's me, but I think you have the wrong idea of what A* does (correct me if I'm wrong). Your iteration "saves" a new location in the variable route every iteration, but that makes no sense for A*. The shortest path can only be traced back from the destination once it's reached. That is, you first do a breadth-first search through all the positions, and when you find the destination, only then you can trace a path back to the start, using the parent row/column variables you set throughout your code.You probably have already seen this link, but just in case, have a look here: http://www.redblobgames.com/pathfinding ... ction.html. Especially the Early Exit demo is really insightful (it's interactive).