#1




Pathfinding help
I'm trying to implement pathfinding into Colonization. However, this is effectively the first real thing I've ever programmed, and I'm in highschool, so I haven't taken any indepth computer classes. In other words, I am vastly unexperienced. I've written and rewritten the algorithm a number of times, even downloaded an A* implementation from the web, but everything has some problem or other. The simulator isn't actually kicking out any errors, there are just some issues. I extracted the script from delirious' Tiled library, and it almost worked. I need help. The map is only 10x10 tiles (100 total, so very smalleven an inefficient algorithm will work for me), and it's not vital that the path even be the shortest. Movement includes diagonal, but it wouldn't have to if a script wasn't suited for that. Below is my most recent attempt which, again, isn't working (it seems to loop infinitely, and I think the openList grows beyond 100, which shouldn't happen since there are only that many tiles. I also think it includes duplicates, which the onList() function should prevent), and I can't figure out why. Any help would be greatly appreciated
Code:
function findPath(startX, startY, endX, endY) local openList = {}; local closedList = {}; local node = {}; node.x = startX; node.y = startY; node.g = 0;move cost from parent tile node.h = estimateMoveCost(node.x, node.y, endX, endY);guess of move cost to target node.sum = node.g + node.h; node.parentX = startX; node.parentY = startY; table.insert(openList, node); while #openList > 0 do table.sort(openList, function(a, b) return a.h < b.h; end); local focusNode = openList[1]; print(gridToIndex(focusNode.x, focusNode.y), focusNode.h); table.remove(openList, 1); table.insert(closedList, focusNode); if focusNode.x == endX and focusNode.y == endY thenfound path! print("Found path!"); local pathList = {}; while 1 do table.insert(pathList, 1, gridToIndex(focusNode.x, focusNode.y)); if focusNode.x == startX and focusNode.y == startY then return pathList; else focusNode = closedList[onList(closedList, focusNode.parentX, focusNode.parentY)]; end end end for u = 1, 1, 1 doacross x for v = 1, 1, 1 doacross y if passable(focusNode.x + u, focusNode.y + v, endX, endY) == true and onList(closedList, focusNode.x + u, focusNode.y + v) == false then local onOpenList = onList(openList, focusNode.x + u, focusNode.y + v); if onOpenList == false then node.x = focusNode.x + u; node.y = focusNode.y + v; if u == 0 or v == 0 thenorthagonal node.g = focusNode.g + 10; elsediagonal node.g = focusNode.g + 14; end node.h = estimateMoveCost(node.x, node.y, endX, endY); node.sum = node.g + node.h; node.parentX = focusNode.x; node.parentY = focusNode.y; elsealready on openList; check if this is a better path if u == 0 or v == 0 thenorthagonal local score = 10; else local score = 14; end if focusNode.g + score < openList[onOpenList].g thenbetter path node = openList[onOpenList]; node.g = focusNode.g + score; node.sum = node.g + node.h; node.parentX = focusNode.x; node.parentY = focusNode.y; end end table.insert(openList, node); end end end end failure if reached this far game.guiList.message = "I can't get there!"; game.guiList.counter = 0; end function estimateMoveCost(startX, startY, endX, endY) return (math.abs(startX  endX) + math.abs(startY  endY)) * 10; end function passable(x, y, targetX, targetY) if x > 0 and x < 101 and y > 0 and y < 101 and game.mapList[gridToIndex(x, y)] == 0 then return true; elseif x == targetX and y == targetY thensince target will always be a building or other "obstacle", must return true or else target will never be added to open list return true; else return false; end end function onList(list, x, y) for index, value in ipairs(list) do if value.x == x and value.y == y then return index; end end return false;failure if reached this far end 
Advertisement  [Remove Advertisement] 

#2




when i get home i will look at it.

#3




I found this lin ein function passable:
if x > 0 and x < 101 and y > 0 and y < 101 and game.mapList[gridToIndex(x, y)] == 0 are you sure, that you have map 101x101 
#4




Thanks! Indeed, that was an error I had missed. However, the problem persists. Out of curiosity, I added a print() function which displays the length of openList. Though this number should never be above 100 (that's the size of my map), it quickly escalates into the thousands. The most logical reason would be a problem with my onList(list, x, y) function, which would return false if there was no other tile with the same coordinates, and an index number if there was (thus preventing duplicates), but I don't see any issues with that function. I am at a loss.

#5




function onList looks ok to me.
Check your function passable. Especially first line of code there. and game.mapList[gridToIndex(x, y)] == 0 Next i thin i found logical error in function findPath. You always add node to list, even if it already is on. local onOpenList = onList(openList, focusNode.x + u, focusNode.y + v); if onOpenList == false then . . . elsealready on openList; check if this is a better path . . . end; table.insert(openList, node); < this could be it!!! 
«
Previous Thread

Next Thread
»
Thread Tools  Search this Thread 
Display Modes  


All times are GMT 5. The time now is 10:49 AM.