include("/../maptravel/npc.xml");
include("/../maptravel/maps.xml");

	
function travel2(_dest,_move,_function)
	
	player:update()
	local mapname = {}
	for k,v in pairs(maps) do
		if getZoneId() == v.zoneid then mapname = v.zone end
	end

	local path = {}
	if type(_dest) == "table" then -- _dest are coords
		if _dest.X ~= nil then
			dest = {_dest.X,_dest.Z,_dest.Y}
		else
			dest = _dest
		end
	elseif type(_dest) == "number" then -- _dest is NPC id	
		for k,v in pairs(NPC) do
			if _dest == v.id then
				if v.Y == nil then v.Y = 0 end
				dest = {v.X , v.Z , v.Y}
			end
		end
	end

	--=== determine location ===--
	local closest = 1;
	for i,v in pairs(mapname) do
		local oldClosestWp = mapname[closest];
		if v.Y == nil then
			if( distance(player.X, player.Z, oldClosestWp.X, oldClosestWp.Z) > distance(player.X, player.Z, v.X, v.Z) ) then
				closest = i;
			end		
		else
			if( distance(player.X, player.Z, player.Y, oldClosestWp.X, oldClosestWp.Z, oldClosestWp.Y) > distance(player.X, player.Z, player.Y, v.X, v.Z, v.Y) ) then
				closest = i;
			end
		end
		travellocation = closest
	end	

	--=== determine destination ===--
	local closest = 1;
	for i,v in pairs(mapname) do
		local oldClosestWp = mapname[closest];
		if v.Y == nil then
			if( distance(dest[1], dest[2], oldClosestWp.X, oldClosestWp.Z) > distance(dest[1], dest[2], v.X, v.Z)	) then
			closest = i;
			end
		else
			if( distance(dest[1], dest[2],dest[3], oldClosestWp.X, oldClosestWp.Z, oldClosestWp.Y) > distance(dest[1], dest[2],dest[3], v.X, v.Z, v.Y)	) then
			closest = i;
			end
		end
		traveldestination = closest
	end
	
	for pointnum,point in pairs(mapname) do
		for Num,link in pairs(point.Links) do
			if mapname[pointnum].Links[Num].dist == nil then
				mapname[pointnum].Links[Num].dist = distance(point.X, point.Z, mapname[Num].X, mapname[Num].Z)
			end
		end
	end

	local function findPath(_from, _val)

		-- initialize
		local dist = {} -- Current total distances to each point
		local previous = {} -- Current previous points that yield the shortest distance to those points
		local completed = {} -- points already checked and finished with
		local Q = {}-- queue of current points being worked on. Only the index numbers
		dist[_from] = 0
		Q[_from] = true

		local function getSmallestDist(_Q)
			-- Look for shortest path in Q
			local shortestdist = math.huge -- So we don't have to check for nil all the time
			local shortest
			for k,__ in pairs(_Q) do
				if dist[k] < shortestdist then
					shortestdist = dist[k]
					shortest = k
				end
			end

			return shortest
		end


		local destination_found = false
		while next(Q) ~= nil do -- not empty
			-- find point with shortest dist
			local currNum = getSmallestDist(Q)
			if currNum == nil then
				error("I think it finished without finding a path to the destination.")
			end
	if mapname[currNum]~= nil then -- This line is not needed. Added because of faulty database
			currPoint = table.copy(mapname[currNum])
			-- see if it's the destination
			if currNum == _val then
				destination_found = currNum
			end

			if destination_found then
				-- destination reached
				print("Destination found")
				break
			end

			-- bring in connected Links that aren't already completed
			for k,v in pairs(currPoint.Links) do
				if Q[v.Num] then -- Already in the Q. Update dist.
					local tmp = dist[currNum] + v.dist
					if tmp < dist[v.Num] then
						dist[v.Num] = tmp
						previous[v.Num] = currNum
					end
				elseif not completed[v.Num] then -- add new point
					Q[v.Num] = true
					dist[v.Num] = dist[currNum] + v.dist
					previous[v.Num] = currNum
				end
			end
	end -- This line is not needed. Added because of faulty database
			-- pop from the Q.
			completed[currNum] = true
			Q[currNum] = nil
		end

		if next(Q) == nil then
			error("Didn't find path to destination.")
		end

		if destination_found then -- return path
			-- 'currNum' is the destination
			table.insert(path,{X=mapname[destination_found].X,Z=mapname[destination_found].Z,Y=mapname[destination_found].Y})
			while previous[destination_found] do
				destination_found = previous[destination_found]
				--table.insert(path,destination_found)
				table.insert(path,{X=mapname[destination_found].X,Z=mapname[destination_found].Z,Y=mapname[destination_found].Y})
			end
		end

	end	
	
	findPath(traveldestination,travellocation)
	
	if _move == true then
		local count = #path
		for k,v in pairs(path) do
			player:moveTo(CWaypoint(v.X,v.Z),true,false,30)
			print(count..": points left to go before destination.")
			count = (count - 1)
		end
		print("Arrived at destination.")
	else
		table.print(path)
	end
end

--function CPlayer:moveTo(waypoint, ignoreCycleTargets, dontStopAtEnd, range)