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 in-depth computer classes. In other words, I am vastly unexperienced. I've written and re-written 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 small--even 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 then--found 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 do--across x
for v = -1, 1, 1 do--across 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 then--orthagonal
node.g = focusNode.g + 10;
else--diagonal
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;
else--already on openList; check if this is a better path
if u == 0 or v == 0 then--orthagonal
local score = 10;
else
local score = 14;
end
if focusNode.g + score < openList[onOpenList].g then--better 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 then--since 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