Scripting HelpersARCHIVE
A little piece of Roblox history. Preserved for everyone, one question at a time.Read about the archive →
All questions/Question #5600
✓ ANSWER ACCEPTED

Path finding Alorithm, what have I missed?

Asked 237 views1 answers

Yes, you can copy and try this code for yourself.

REQUIREMENTS:

Use a Normal (Server) script.

Line12, 'Objects', a Model of all Parts / Walls in Workspace (BasePlate should not be a child of this) Line13, Just an NPC, with a 'Humanoid'

It's based on the A* algorithm.

Efficiency is NOT a requirement at the moment.

SELECTION BOX COLOUR CODES:

BLUE ' Open List '

RED 'Closed List'

Yellow 'Pathway picked'

Anyone with any knowledge on this algorithm, please let me know of anything I've missed.

PS. The *Heuristic *is on line 129

if not Workspace:FindFirstChild("BasePlate") then
	BasePlate = Instance.new("Part",Workspace)
	BasePlate.Name = "BasePlate"
	BasePlate.FormFactor = "Custom"
	BasePlate.Size = Vector3.new()
	BasePlate.CanCollide = true
	BasePlate.Anchored = true
	BasePlate.CFrame = CFrame.new(0,-100,0)
else
	BasePlate = Workspace.BasePlate
end
Objects = Workspace.Objects
char = script.Parent
char:MakeJoints()

if not Workspace:FindFirstChild("Nodes") then
	Instance.new("Model",Workspace).Name = "Nodes"
end
Nodes = Workspace.Nodes

defaultNode = Instance.new("Part")
defaultNode.Name = "Node"
defaultNode.Transparency = 0
defaultNode.Anchored = true
defaultNode.CanCollide = false
defaultNode.FormFactor = "Custom"
defaultNode.Size = Vector3.new(.4,.4,.4)
--Instance.new("SelectionBox",defaultNode).Adornee = defaultNode



function isOpen(n,list)
	for _,v in pairs(list) do if v == n then return true end end
	return false
end
function isClosed(n,list)
	for _,v in pairs(list) do
		if v == n then return true end end 
	return false
end


castedFolder = Instance.new("Model",Workspace)
castedFolder.Name = "RayCastFolder"

rayP = Instance.new("Part")
rayP.Anchored = true
rayP.CanCollide = false
rayP.FormFactor = "Custom"


function isVisible(from,too, ignore)
	ray = Ray.new(from.Position,(too.Position-from.Position).unit*999)
	if not ignore then
		hit,pos = Workspace:FindPartOnRayWithIgnoreList(ray, {char,castedFolder})
	else
		hit,pos = Workspace:FindPartOnRayWithIgnoreList(ray, {ignore,char,castedFolder})
	end
	local rp = rayP:Clone()
	rp.Parent = castedFolder
	rp.Size = Vector3.new(0,0,(pos-ray.Origin).magnitude)
	rp.CFrame = CFrame.new(ray.Origin:Lerp(pos,0.5),pos)

	if hit == too then return true else return false end
end


function UpdateNodes()
	Nodes:ClearAllChildren()
	for _,v in pairs(Objects:GetChildren()) do
		if v:IsA("BasePart") and v~= Workspace.Target then
			local div = 1
			newNode = defaultNode:Clone()
			newNode.Name = newNode.Name
			newNode.Parent = Nodes
			newNode.CFrame = v.CFrame * CFrame.new(v.Size.x/div,0,v.Size.z/div)
	
			newNode = defaultNode:Clone()
			newNode.Name = newNode.Name
			newNode.Parent = Nodes
			newNode.CFrame = v.CFrame * CFrame.new(-v.Size.x/div,0,v.Size.z/div)
	
			newNode = defaultNode:Clone()
			newNode.Name = newNode.Name
			newNode.Parent = Nodes
			newNode.CFrame = v.CFrame * CFrame.new(-v.Size.x/div,0,-v.Size.z/div)
	
			newNode = defaultNode:Clone()
			newNode.Name = newNode.Name
			newNode.Parent = Nodes
			newNode.CFrame = v.CFrame * CFrame.new(v.Size.x/div,0,-v.Size.z/div)
		end
	end
	x = 0
	nameTag = "Node"
	for i,v in pairs(Nodes:GetChildren())do
		if x < 10 then
			v.Name = nameTag.."00"..x
		elseif x >= 10 and x < 100 then
			v.Name = nameTag.."0"..x
		elseif x >= 100 and x < 1000 then
			v.Name = nameTag..x
		end
		x = x + 1
	end
end












function GetShortestPath(paths) print("GetShortest Path", #paths)
	bestPath = nil
	bestScore = math.huge
	for i,path in pairs(paths) do wait(2)
		castedFolder:ClearAllChildren()
		score = 0
			for x,p in pairs(path) do
				if x == 1 then isVisible(char.Torso,p) end if x == #path and isVisible(p,Target) then end
				if not lastP then lastP = p end
				if isVisible(lastP,p) then
					score = score + (p.Position-lastP.Position).magnitude + (p.Position-Target.Position).magnitude
				--	print(score,bestScore)
				end
				lastP = p
			end
			if score > 0 and score < bestScore then
				bestScore = score
				bestPath = path
			end
	end
	print("Check now")
	wait(5)
	if bestPath and #bestPath > 0 then
		for _,n in pairs(bestPath) do wait(0.5)
			local sb = Instance.new("SelectionBox",n)
			sb.Adornee = n
			sb.Transparency = 0
			sb.Color = BrickColor.Yellow()
			game.Debris:AddItem(sb,5)
		end
	else
		bestPath = nil
	end


	if bestPath then --print("Returning best path", #bestPath.." steps")
		return bestPath
	else	print("Returning nil path")
		return {}
	end
end










UpdateTime = 1


function Search(from,too) wait()-- processes = processes + 1 if processes > 50 then return end
	local openList = {}
--	local closedList = {}
	if from.Parent == Nodes then
		table.insert(closedList,from)
		if not from:FindFirstChild("SelectionBox") then
			sb = Instance.new("SelectionBox",from)
			sb.Adornee = from
			sb.Color = BrickColor.Red()
			game.Debris:AddItem(sb,UpdateTime)
		end
	end
	if isVisible(from,Target,Nodes) then table.insert(newPath,from) return true end
	if isVisible(too,Target,Nodes) then table.insert(newPath,too) return true end

	if isVisible(from,too) then
		table.insert(newPath,from)
		table.insert(newPath,too)
	end

	for i,n in pairs(Nodes:GetChildren()) do
		if not isClosed(n,closedList) and isVisible(from,n) then
			table.insert(openList,n)
			if not n:FindFirstChild("SelectionBox") then
				sb = Instance.new("SelectionBox",n)
				sb.Adornee = n
				sb.Color = BrickColor.Blue()
				game.Debris:AddItem(sb,UpdateTime)
			end
		end
	end
	
	for i,v in pairs(openList) do
		for z,n in pairs(Nodes:GetChildren()) do
			if n ~= v and isVisible(v,n) and not isClosed(n,closedList) then
				if Search(v,n) then processes = processes + 1
					print("Got "..processes.." path(s)")
					table.insert(paths,newPath)
					newPath = {char.Torso}
					castedFolder:ClearAllChildren()
				end
			end
		end
	end

end





while true do print("Go")
	castedFolder:ClearAllChildren()
	Target = Workspace.Target
	if isVisible(char.Torso,Target) then
		FOUNDTARGET = true
		char.Humanoid:MoveTo(Target.Position,BasePlate)
	else
		FOUNDTARGET = false
		UpdateNodes()
		newPath = {char.Torso}
		closedList = {}
		openList = {}
		paths = {}
		processes = 0
		Search(char.Torso,Target)
		print("Paths found["..#paths.."]")
	--	coroutine.resume(coroutine.create(function()
			if #paths> 0 then
				for _,v in pairs(GetShortestPath(paths)) do wait(UpdateTime/5) print("Travelin' to ", v)
					sb = Instance.new("SelectionBox",v)
					sb.Adornee = v
					sb.Color = BrickColor.White()
					game.Debris:AddItem(sb,UpdateTime/5)
					repeat wait()
						castedFolder:ClearAllChildren()
						overshoot = -(char.Torso.Position-v.Position).unit*4
						char.Humanoid:MoveTo(v.Position + overshoot,BasePlate)
					until (v.Position-char.Torso.Position).magnitude <= 4 or FOUNDTARGET or isVisible(char.Torso,Workspace.Target)
					if isVisible(char.Torso,Workspace.Target) then break end
				end
			end
	--	end))
	end
	wait(UpdateTime)
end
AnonymousEdited

3 comments

0

dude 258 lines of code...

Anonymous#
0

As I said, you can copy and test it.

Anonymous#
0

I understand the algorithm but just post the algorithm.

Anonymous#

1 answer

✓ Accepted answer

A* is not a complicated function. A lot of what you have can be significantly reduced. I'm not going to make this quite the same as what you have, but hopefully this is a useful model for your to write your stuff.

I assume adjacent is defined in a way like isVisible is (except where the parameters are Vector3's)

nodes I take as a list of Vector3's, and from and to being two Vector3's inside of that list.

I didn't test this, but it should work. This function seems to replace your Search and GetShortestPath functions.

When A* is implemented correctly, it efficiently finds the shortest path, not just a path which may be short, but the shortest path.

function astar(nodes,from,to)
	local visited = {};
	local goto = {}; -- Should be a heap for efficiency
	local parent = {};
	local pathDistance = {};
	local last = from;
	while last and last ~= to do
		visited[last] = true;
		for _,node in pairs(nodes) do
			if adjacent(node,last) and not visited[node] then
				pathDistance[node] = pathDistance[last] 
					+ (node-last).magnitude;
				parent[node] = last;
				visited[node] = true;
				table.insert(goto,node);
			end
		end
		table.sort(goto, function(a,b)
			local DA = (a - to).magnitude;
			local DB = (b - to).magnitude;
			return DA + pathDistance[a] < DB + pathDistance[b];
		end);
		-- Again, for efficiency purposes, should be a heap
		last = goto[1];
	end
	local path = {};
	while last do
		table.insert(path,last,1);
		last = parent[last];
	end
	return path;
end

EDIT: Here's an explanation of the algorithm.

This form of path finding is done on a list of "nodes", points in space. Some of them are "connected" or "adjacent", meaning you can go directly from one to another. In the context of a game, that means you can walk in a straight line without any obstacles in the way.

The idea of A* is to improve upon Dijstrika's algorithm. Dijstrika's algorithm starts from a single node, and finds the very closest node, V, to the starting node, S.

You know that since this was the shortest edge available, any other path to that particular closest node would be longer than this one; you know the shortest path from S to V is just {S,V}.

Now we consider all of the nodes adjacent to either S or V to find the next closest (by path length) node to S. If this node, B is adjacent to V (but not S) then the distance of its path is ||B - V|| + ||V - S||. If it is adjacent to S, it's path length is just ||B - S||. (||x|| here means the magnitude of vector x)

We see for the same arguments as before that we have the shortest path to B (either {S,B} or {S,V,B}) and furthermore that no node has a shorter path than B.

We can repeat this until we find a shortest path to every node.

If you think about this, though, for most applications, this is grossly inefficient. Why do we care about the shortest path to B if we only need to know the shortest path to C?

We could begin by modifying the way we grow out. If we instead consider the node closest to our target, we'll see that it only bothers checking things going in the correct direction. This will mean it will (usually) find the path much more quickly. However, we can easily imagine mazes where it goes completely out of its way, turns around, and then finds the solution. The paths produced from this "best first" search is not optimal.

It is provable that if we modify Dijstrika's by just adding the distance to the target, we keep the paths optimal, but also make it much more direct to the target. If we multiply that distance by a larger amount, we get a faster algorithm that gives slightly less optimal paths.

So that's A* for you.

AnonymousEdited Permalink

1 comment

0

Thanks for taking the time to explain this, I knew my version wasn't efficient, but I was unsure how to do it. To be honest I'm still having trouble with it. But cheers.

Anonymous#

This discussion is preserved as it was. New answers, comments, and votes are closed.