# Pathfinding Trouble

So I’m working on a game similar to B-Cubed. You may be familiar with this game if you were a Coolmathgames junkie like me. The objective of the game is to reach B starting at A using ‘WASD’. Blocks would fall behind you as you move a specific direction.

Anywho, I’m having trouble deciding what the next step would be. I have the code for detecting what the former part was. MainPart was touching Part1 in the path including (Part1, Part2, Part3), therefore when hitting D to move RIGHT, Part1 would fall and the MainPart would be on top of Part2.

So the question is, how do I code this to work with WASD and to move parts on a designated path where there are multiple directional possibilities?

Here’s what I got so far, it works for declaring what part is touching the MainPart.

``````ReplicatedStorage:WaitForChild('MovePart').OnServerInvoke = function(x)
local Dir = x
local Connection = MainPart.Touched:Connect(function() end)
for i, v in pairs(MainPart:GetTouchingParts()) do
if v:IsA('BasePart') and v.Parent.Name == 'Path' then
table.insert(TouchingParts, v)
wait()
if Connection then
Connection:Disconnect()
Connection = nil
end

spawn(function()
MainPart.CFrame = CFrame.new((MainPart.CFrame-MainPart.Position)*CFrame.Angles(0,math.pi/2,0) + MainPart.Position)
MainPart:MoveTo(FindNextPath(Dir))

for i = 1, 20 do
local x = math.random(-100,100)/100
local y = math.random(-100,100)/100
local z = math.random(-100,100)/100
v.CFrame = CFrame.new(x,y,z)
wait()
v.Anchored = false
--table.remove(TouchingParts, v)
end
end)
end
end
end
``````
1 Like

If I understand the question correctly, you have a part which when touched you want it to move to the next grid position that leads to the goal, B?

The first step in any pathfinding problem is usually to think in terms of a computer science graph. In your case, a simple grid will do. This is defined by each “node” (what you call “parts”) being connected to four adjacent nodes. Since the weights or costs for movement in any direction is constant and always positive, a simple breadth first search through the grid will yield the optimal path.

The issue that you will run into is that if the grid contains open spaces, there will be many paths with the exact same cost. The simplest case is moving diagonally, moving left then up is the same as moving up then left. Moving two spaces diagonally there are five paths that would yield the same results (LLUU, LULU, LUUL, ULUL, UULL) this number expands the further you move and can yield some pretty nasty looking paths. When you run into this issue, I would actually recommend pathfinding using 8 directions of movement and then after a path is found convert it back into 4-direction movement. Moving on the diagonals should cost less than moving twice (square root of 2 is optimal) and only be available if the diagonal neighbor and a shared 4-direction neighbor is open. This guarantees that the 8-direction movement can be converted into 4-direction movement later. Since there will be different costs for movements, this modification of a breadth first search is called Dijkstra’s algorithm.

Here is a description of BFS on a maze grid. https://www.youtube.com/watch?v=ec0IJsiIuWk

And here is a quick BFS implementation with backtracking to find the path:

``````local function get_path(ancestry, cur)
local path = {}
while cur do
path[#path + 1] = cur
cur = ancestry[cur]
end
return path
end

local function BFS_step(nodes, visited, ancestry, goal)
local fringe = {}
for node in pairs(nodes) do
if goal == node then
return
end
for child in pairs(node.neighbors) do
if not visited[node] then
visited[node] = true
fringe[node] = true
end
end
end
return fringe
end

local function BFS(start, goal)
local fringe = {[start] = true}
local visited = {}
local ancestry = {}

while true do
fringe = BFS_step(fringe, visited, ancestry, goal)
if not fringe then
return find_path(ancestry, goal)
elseif #fringe == 0 then
return 'NO PATH'
end
end
end
``````
4 Likes

You were very close in what I was trying to do. Either way, your code is extremely helpful and will kickstart my work today. Thank you very much