Pathfinding help

[©reative]

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

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

[delirius]

when i get home i will look at it.

[delirius]

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

[©reative]

Originally Posted by delirius

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

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.

[delirius]

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
.
.
.
else--already on openList; check if this is a better path
.
.
.
end;
table.insert(openList, node); <---- this could be it!!!