android
Prev Previous Post   Next Post Next
  #1  
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

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
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 08:33 PM.