Problem with custom AI pathfinding

Help and Feedback Scripting Support
#1

ASD
ASD726Ă—403 69.7 KB 

local Ship = game.Workspace.TheShip
local StartingBall = Ship.StartingBall
local EndingBall = Ship.EndingBall
for i,v in pairs(game.Workspace:GetChildren()) do
	if v:FindFirstChild("Cities") then
		for i,city in pairs(v.Cities:GetChildren()) do
			if city.Value.BillboardCity.NomeCit.Text == "VENICE" then
				StartingBall.Value = v
			end
			if city.Value.BillboardCity.NomeCit.Text == "CONSTANTINOPLE" then
				EndingBall.Value = v
			end
		end
	end
end

local ClosestBallToEndGoal
local PreviousBall = StartingBall
local CurrentBall = StartingBall
local Arrived = false
repeat
	wait(3)
	local ClosestMagnitude = 100000
	for i,v in pairs(CurrentBall.Value.NeighboringWaypoints:GetChildren()) do
		local NeighboringBall = v.Value
		print("Current ball "..CurrentBall.Value.Name)
		if NeighboringBall == EndingBall.Value then
			print("ARRIVED AT "..EndingBall.Value.Name)
			Arrived = true
			PreviousBall.Value = CurrentBall.Value
			CurrentBall.Value = EndingBall.Value
			Ship.CFrame = CFrame.lookAt(Ship.Position,CurrentBall.Value.Position)
			Ship.Position = CurrentBall.Value.Position
		else
			print("Neighbor " .. NeighboringBall.Name , "Previous " .. PreviousBall.Value.Name)
			if NeighboringBall ~= PreviousBall.Value then
				print(math.ceil((NeighboringBall.Position - EndingBall.Value.Position).magnitude) , math.ceil(ClosestMagnitude))
				if (NeighboringBall.Position - EndingBall.Value.Position).magnitude < ClosestMagnitude then
					print(NeighboringBall.Name.." is closer")
					ClosestMagnitude = (NeighboringBall.Position - EndingBall.Value.Position).magnitude
					ClosestBallToEndGoal = NeighboringBall
				end
			end
		end
	end
	if Arrived == false then
		PreviousBall.Value = CurrentBall.Value
		CurrentBall.Value = ClosestBallToEndGoal
		Ship.CFrame = CFrame.lookAt(Ship.Position,CurrentBall.Value.Position)
		Ship.Position = CurrentBall.Value.Position
		print("ship is at "..CurrentBall.Value.Name)
	end
	print("=================================")
until Arrived == true

“NeighboringBalls” is a folder inside each ball, which has objectValues telling which neighboring balls the ship can travel to next.
The problem is the ship cant really figure out that it should go around the continent instead of just running into the wall.
Do you guys have any idea on how this problem can be solved?

#2

I’m still looking for an answer :sob:

#3

have you tried using a raycast to detect the wall?

#4

to expand on this idea, use a raycast from point to calculated point to check for obstacles. it’d be a little bit of math but it should in theory work just fine.

#5

What you have is what’s known in computer science circles as a graph. What you need is a form of Dijkstra’s Algorithm. It’s an algorithm that was published in the 1950s to solve exactly this type of problem. Basically, you have a bunch of nodes. Each node contains a connection to another node. The algorithm will find the best path through the nodes at the least cost. I’ve included a picture of your nodes (with lines and your map) to illustrate your graph.

20220621_161901
20220621_1619011920Ă—1440 109 KB

The large circles are your cities, the small open circles are your nodes from your map, the solid small circles are extra nodes that I added, and the square is the destination. If you place a weight on each link between the nodes, and make that weight, say. the distance, then the algorithm will find the shortest path between any two nodes.

Wikipedia has a pretty good writeup on it with pseudocode which you can look at here: Dijkstra's algorithm - Wikipedia

Rosetta Code also has a pretty good writeup and actual code in LUA which can be found here: Dijkstra’s Algorithm - Rosetta Code

Hope this helps.

1 Like