Broken A* Algorithm, could use some help
Posted: Sat Mar 19, 2016 3:41 pm
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
endCode: 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
endCode: 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