function findpath(unitid,ex,ey,nearby_)
	local sx = MF_getvalue(unitid,XTILE)
	local sy = MF_getvalue(unitid,YTILE)
	
	local nearby = nearby_ or 1
	
	local path,s,uw = astar(sx,sy,ex,ey,nil,nearby)
	
	MF_setstring(unitid,PATH,path)
	MF_setvalue(unitid,XPATHTILE,sx)
	MF_setvalue(unitid,YPATHTILE,sy)
	MF_setvalue(unitid,PATHSTEP,0)
	
	return s,uw
end

function findpath_tostruct(unit,stype,minstatus_)
	local unitid = unit.id
	local minstatus = minstatus_ or 0
	local x,y = MF_getvalue(unitid,XTILE),MF_getvalue(unitid,YTILE)
	
	local s,nearby = findstruct(x,y,stype,minstatus)
	local uw = false
	local success = false
	
	if (s ~= nil) then
		local sx,sy = MF_getvalue(s.id,XTILE),MF_getvalue(s.id,YTILE)
		success,uw = findpath(unitid,sx,sy,nearby)
		
		return s,uw
	end
	
	return nil,nil
end

function findpath_todamaged(unit)
	local unitid = unit.id
	local x,y = MF_getvalue(unitid,XTILE),MF_getvalue(unitid,YTILE)
	
	local s = finddamaged(x,y)
	local uw = false
	local success = false
	
	if (s ~= nil) then
		local sx,sy = MF_getvalue(s.id,XTILE),MF_getvalue(s.id,YTILE)
		success,uw = findpath(unitid,sx,sy,2)
		
		return s,uw
	end
	
	return nil,nil
end

function findpath_toitem(unit,stype)
	local unitid = unit.id
	local x,y = MF_getvalue(unitid,XTILE),MF_getvalue(unitid,YTILE)

	local s = finditem(x,y,stype)
	local uw = false
	local success = false
	
	if (s ~= nil) then
		local sx,sy = MF_getvalue(s.id,XTILE),MF_getvalue(s.id,YTILE)
		success,uw = findpath(unitid,sx,sy)
		
		return s,uw
	end
	
	return nil,nil
end

function astar(sx,sy,ex,ey,maxlen,nearby_)
	local data = map.astar
	local success = false
	local nearby = nearby_ or 1
	local underwater = false
	
	data.parray = {}
	
	local cx = sx
	local cy = sy
	local tilelist = {}
	local dir = 0
	local done = false
	local result = ""
	local limit = maxlen or searchlimit
	local loops = 0
	local cost = 0
	local path = ""
	local walls = "1111"
	
	local tileid = gettileid(cx,cy)
	local code = "000000" .. getcode(cx,3) .. getcode(cy,3)
	table.insert(tilelist, code)
	
	data.parray[tileid] = {}
	data.parray[tileid][1] = ""
	data.parray[tileid][2] = 0
	
	while (done == false) and (loops < limit) do
		if (#tilelist > 0) then
			table.sort(tilelist)
		end
		local curr = tilelist[1]
		table.remove(tilelist, 1)
		
		cx,cy = codepos(curr,3)
		tileid = gettileid(cx,cy)
		
		path = data.parray[tileid][1] or "ERROR"
		cost = data.parray[tileid][2] or -1
		local tdata = data.marray[tileid] or {}
		walls = tdata[2] or "1111"
		
		loops = loops + 1
		
		if (cx ~= ex) or (cy ~= ey) then
			if (string.sub(walls, 1, 1) ~= "0") then
				data,tilelist = checktile(cx,cy,1,0,0,data,tilelist,ex,ey,cost,path,string.sub(walls, 1, 1))
			end
			
			if (string.sub(walls, 2, 2) ~= "0") then
				data,tilelist = checktile(cx,cy,0,-1,1,data,tilelist,ex,ey,cost,path,string.sub(walls, 2, 2))
			end
			
			if (string.sub(walls, 3, 3) ~= "0") then
				data,tilelist = checktile(cx,cy,-1,0,2,data,tilelist,ex,ey,cost,path,string.sub(walls, 3, 3))
			end
			
			if (string.sub(walls, 4, 4) ~= "0") then
				data,tilelist = checktile(cx,cy,0,1,3,data,tilelist,ex,ey,cost,path,string.sub(walls, 4, 4))
			end
		end
		
		local near = isnearby(cx,cy,ex,ey)
		
		if (near > 0) and (near <= nearby) then
			--MF_alert("success! " .. path)
			result = path
			done = true
			success = true
			
			local x,y = sx,sy
			
			for i=1,#result do
				local l = string.sub(result, i, i)
				local ox,oy = dirtopos(l)
				x = x + ox
				y = y + oy
				tileid = gettileid(x,y)
				if (data.marray[tileid] == nil) then
					underwater = true
				end
				--MF_debug(x,y)
			end
		elseif (loops >= limit) then
			MF_alert("Too long!" .. path)
			result = path
			done = true
			
			local x,y = sx,sy
			
			for i=1,#result do
				local l = string.sub(result, i, i)
				local ox,oy = dirtopos(l)
				x = x + ox
				y = y + oy
				tileid = gettileid(x,y)
				if (data.marray[tileid] == nil) then
					underwater = true
				end
				--MF_debug(x,y)
			end
		elseif (#tilelist == 0) then
			MF_alert("Nothing found!")
			done = true
		end
	end
	
	return result,success,underwater
end

function checktile(x,y,ox,oy,dir,data_,tilelist_,ex,ey,cost_,path_,wall)
	local data = data_
	local tilelist = tilelist_
	local cost = cost_
	local path = path_ .. tostring(dir)
	local cx = x + ox
	local cy = y + oy
	local tileid = gettileid(cx,cy)
	local blocked = false
	
	if (map.doors[tileid] ~= nil) then
		local d = map.doors[tileid]
		
		if (d[rot(dir)] ~= nil) then
			local doorid = d[rot(dir)]
			local powered = MF_getvalue(doorid,POWERED)
			
			if (powered == 0) then
				blocked = true
			end
		end
	end
	
	if inbounds(cx,cy) and (data.parray[tileid] == nil) and (blocked == false) then
		local dist = math.abs(ey - cy) + math.abs(ex - x)
		local tiledata = data.marray[tileid] or {}
		local costhere = tiledata[1] or 1
		local walls = tiledata[2] or "1111"
		
		local canmove,extracost = checkwalls(walls,dir)
		
		if (wall == "2") then
			extracost = extracost + 2
		end
		
		cost = cost + extracost
		local fullcost = cost + costhere
		
		if (costhere ~= 999) and canmove then
			if (data.parray[tileid] == nil) then
				data.parray[tileid] = {}
			end
			
			data.parray[tileid][1] = path
			data.parray[tileid][2] = fullcost
			
			local code = getcode(dist * 2 + fullcost * 5,6)
			code = code .. getcode(cx,3) .. getcode(cy,3)
			
			table.insert(tilelist, code)
		end
	end
	
	return data,tilelist
end

function checkwalls(w,d)
	local c = 0
	local rot = {3,4,1,2}
	
	local dir = rot[d+1]
	
	if (string.sub(w, dir, dir) ~= "0") then
		if (string.sub(w, dir, dir) == "2") then
			c = 5
		end
		
		return true,c
	end
	
	return false,c
end

function rot(d)
	local rot = {2,3,0,1}
	
	local r = rot[d+1] or -1
	
	return r
end