flash

-- Pathfinder API
-- Crazyman32
-- October 6, 2014

--[[

	----------------------------------------------------------------------------------

	API:

		- pathfinder:FindPath()
		- pathfinder:SetEmptyCutoff()
		- path:GetPointCoordinates()
		- path:CheckOcclusionAsync()

		EXAMPLES:

		- pathfinder = require(game.ServerScriptService.Pathfinder)

		- path = pathfinder:FindPath(startPosition, endPosition)

				- points = path:GetPointCoordinates()
				- index  = path:CheckOcclusionAsync(startIndex)

		- pathfinder:SetEmptyCutoff(ratio)

	----------------------------------------------------------------------------------

	HOW TO USE -- Example Code:

		local pathfinder = require(game.ServerScriptService.Pathfinder)
		local points, status = pathfinder:FindPath(startPosition, endPosition)

		-- Where 'startPosition' and 'endPosition' are Vector3 values that
		-- represent the start and end positions of the path.

	----------------------------------------------------------------------------------

	BENEFITS OVER PATHFINDINGSERVICE:

	-	Simplified path. Instead of having tons of points for every step
		of the way, this API will simplify the path by only keeping the
		important points: the start/end points for each straight or
		diagonal line.

	-	No distance cap. You can find a path between as far of a distance
		as you want. The API will connect multiple max-length paths from
		the PathfindingService for you and return a single list of points.

--]]



local Pathfinder = {}
local API = {}
local MT = {}

-------------------------------------------------------------------------------
-- Core:

local MAX_PATHS = 10

local pathfindingService = game:GetService("PathfindingService")


local function SimplifyPointsStraight(points)
	local simplified = {}
	local i = 1
	while (i < #points) do
		local pt = points[i]
		table.insert(simplified, pt)
		if (i < #points) then
			local ptNext = points[i + 1]
			local dx, dy, dz = (ptNext.x - pt.x), (ptNext.y - pt.y), (ptNext.z - pt.z)
			for j = i+1, #points do
				i = j
				local ptLast = points[i - 1]
				local pt2 = points[i]
				local dx2, dy2, dz2 = (pt2.x - ptLast.x), (pt2.y - ptLast.y), (pt2.z - ptLast.z)
				if (dx ~= dx2 or dy ~= dy2 or dz ~= dz2) then
					i = (i - 1)
					break
				end
			end
		end
	end
	table.insert(simplified, points[#points])
	return simplified
end


local function SimplifyPointsDiagonal(points)
	local simplified = {}
	local i = 3
	while (i < #points) do
		local p1 = points[i - 2]
		local p2 = points[i - 1]
		local p3 = points[i]
		local a = (p1 - p2).magnitude
		local b = (p2 - p3).magnitude
		local c = (p1 - p3).magnitude
		table.insert(simplified, p1)
		if (a == b) then
			i = (i + 2)
		else
			i = (i + 1)
		end
	end
	table.insert(simplified, points[#points])
	return simplified
end


function CreatePathObject(paths, points, finalStatus)
	local path = {}
	local api = {}
	api.Status = finalStatus
	function api:GetPointCoordinates()
		return points
	end
	function api:CheckOcclusionAsync(start)
		local n = 0
		local startIndex = 1
		for i,p in pairs(paths) do
			local numPoints = #p:GetPointCoordinates()
			n = (n + numPoints)
			if (n >= start) then
				startIndex = i + 1
				local test = p:CheckOcclusionAsync(n - numPoints + start)
				if (test ~= -1) then
					return (n - numPoints + test)
				end
				break
			end
		end
		for i = startIndex, #paths do
			local p = paths[i]
			local numPoints = #p:GetPointCoordinates()
			n = (n + numPoints)
			if (numPoints > 0) then
				local test = p:CheckOcclusionAsync(1)
				if (test ~= -1) then
					return (n - numPoints + test)
				end
			end
		end
		return -1
	end
	return setmetatable(path, {
		__metatable = true;
		__index = api;
		__newindex = function()
			error("Cannot edit Path")
		end;
	})
end


-------------------------------------------------------------------------------
-- API:

function API:FindPath(pointA, pointB)
	local points = {}
	local paths = {}
	local path
	local tooLong = false
	repeat
		path = pathfindingService:ComputeRawPathAsync(pointA, pointB, 500)
		table.insert(paths, path)
		if (path.Status ~= Enum.PathStatus.FailStartNotEmpty and path.Status ~= Enum.PathStatus.FailFinishNotEmpty) then
			for _,pt in pairs(path:GetPointCoordinates()) do
				table.insert(points, pt)
			end
			if (path.Status == Enum.PathStatus.ClosestOutOfRange) then
				pointA = points[#points]
				if (#paths >= MAX_PATHS) then
					tooLong = true
					break
				end
			end
		end
	until (path.Status ~= Enum.PathStatus.ClosestOutOfRange)
	if (#points > 2) then
		points = SimplifyPointsStraight(SimplifyPointsDiagonal(points))
	end
	return CreatePathObject(paths, points, (tooLong and Enum.PathStatus.ClosestOutOfRange or path.Status))
end

function API:SetEmptyCutoff(emptyCutoff)
	pathfindingService.EmptyCutoff = emptyCutoff
end

-------------------------------------------------------------------------------
-- MT:

MT.__metatable = true
MT.__index = API
MT.__newindex = function()
	error("Cannot edit Pathfinder API")
end
setmetatable(Pathfinder, MT)

-------------------------------------------------------------------------------

return Pathfinder