Prev Previous Post   Next Post Next
Old 04-20-2011, 01:30 PM
İreative's Avatar
İreative İreative is offline
Junior Member
Join Date: Jun 2010
Location: Minnesota, USA
Posts: 39
Default 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 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;
					focusNode = closedList[onList(closedList, focusNode.parentX, focusNode.parentY)];
		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;
							node.g = focusNode.g + 14;
						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;
							local score = 14;
						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;
					table.insert(openList, node);
	--failure if reached this far
	game.guiList.message = "I can't get there!";
	game.guiList.counter = 0;

function estimateMoveCost(startX, startY, endX, endY)
	return (math.abs(startX - endX) + math.abs(startY - endY)) * 10;

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;
		return false;

function onList(list, x, y)
	for index, value in ipairs(list) do
		if value.x == x and value.y == y then
			return index;
	return false;--failure if reached this far
Reply With Quote

Advertisement [Remove Advertisement]


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT -5. The time now is 02:16 PM.