Hi!
What do you want to achieve? I want to utilize Breadth-first Search for a pathfinding system
What is the issue? I genuinely do not understand how to do this and what any code I see for it even means.
What solutions have you tried so far? I tried looking at a showcase of it (open sourced) and I didn’t know what the variables were and what the function even did.
Please help me.
Thanks!
For simplicity we will consider this map as the data you need for pathfinding just so we are on the same page.
Pathfinding at it’s core is rather simple. We start at the starting point, and we ask what neighbors it has that we can move to (so which tiles are next to it that aren’t walls or traps or something). Then we look at all those neighbors we found one by one and ask the same question again, what neighbors does this have that we haven’t already looked at? You just keep checking neighbors and neighbors of neighbors until eventually, one of these neighbors is the goal.
Generally we have 2 lists to help us keep track of these neighbors. An openList which is where we put neighbors we have found but not processed. And a closedList which is where we put neighbors we have processed (found it’s neighbors already).
So the first tile, the start is going to be the only thing in the openList to start. You want to keep looping while the open list has tiles. First in this loop you want to pull the first item in the openList out of the openList and add it to the closed list. Then you want to check if this tile is the exit. If it’s not the exit, you want to add all of it’s neighbors to the openList IF it doesn’t exist in the open or closed list already (since any tile is it’s neighbors neighbor, you need to be able to filter out tiles you are checking or have checked).
Breadth first let’s us simplify the algorithm a little since we can’t end up finding shorter paths to a tile we have already found. In some algorithms like A*, you will need to worry about that though and have a way to update tiles to the shorter path when you find it. We don’t need to worry about it here though.
Anyways, every tile you add to the openList needs to have 2 pieces of information about it. Where the tile is (so you can know where to move, and so you can check that it doesn’t already exist in either list). You also need a reference to the parent tile, which is the tile it came from. When you find the exit, you basically just walk backwards along all the parent tiles until you hit the start again which let’s you construct the path.
For a visual aid, I recommend checking out this site (it’s where that first image came from)
https://clementmihailescu.github.io/Pathfinding-Visualizer/
The algorithm you are probably interested in would be Dijkstra’s and I recommend setting the speed to slow so you can see how it’s processing all of the neighbors over and over again.
Grids of course are used for pathfinding like we use in this example, but they aren’t perfect for every situation, you can create a graph of nodes, or you can create something called a navmesh. They all share the same general algorithm though of recursively searching through valid neighbors until you find a path. These approaches are more complex, but also more powerful in how they can describe where players can move. They however are much harder to get the data for. Roblox generates something like this behind the scenes for it’s own pathfinding, but sadly we can’t access it.
And keep in mind pathfinding can be a bit complex, but it’s very cool when you get it working. I wish you luck and feel free to ask me if you need any help or clarification.
I’ve got a question; How exactly does going back on the explored tiles give you the shortest path? Thanks!
Basically for every tile you are storing the tile you came from to get there. This means by checking the tile you came from over and over until you hit the tile without a parent, you have hit the start. Since only the start tile wasn’t found from another tile and every path has to have a way back to the start. Basically it’s like a linked list that represents the path.
Just note breadth first simplifies this a bit. Since everytime you fund a neighbor it either already exists, or is the shortest path. For a depth first or just another approach, sometimes you can end up finding a shorter path later so you’d need to make sure that only the parent with the shortest path gets to be the considered tiles parent.
So I tried coding it while looking at another BFS searching algorithm, and the exploring tiles part works, but the backtracking part doesn’t.
(Note, this is for a WW1 game.)
My code (for testing):
local function ShowPathToGoal(explored, goal, s)
local path = {}
local currentNode = goal
while currentNode and currentNode.Name ~= s.Name do
local num = tonumber(string.split(currentNode.Name,"e")[2])
print(num)
print(currentNode)
table.insert(path, 1, currentNode)
currentNode = explored[num]
wait(0.1)
end
print(currentNode)
print(explored)
print(path)
for _,node in pairs(path) do
--if node ~= goal then
node.BrickColor = BrickColor.new("Shamrock")
--end
end
end
function BFS(s,f)
local queue = {s}
local explored = {}
local goalReached = false
while #queue ~= 0 do
local slot = queue[1]
if slot == f then
goalReached = true
break
end
if slot ~= s then
slot.BrickColor = BrickColor.new("White")
end
table.remove(queue, 1)
local neighbors = workspace:GetPartsInPart(slot)
if #neighbors > 0 then
for i,v in pairs(neighbors) do
if v:FindFirstChild("Obstacle") then continue end
if not table.find(explored,v) and not table.find(queue, v) then
table.insert(explored,slot)
table.insert(queue,v)
end
end
else
break
end
end
--print(explored)
if goalReached then
ShowPathToGoal(explored, f, s)
end
end
wait(4)
BFS(workspace.France["Alsace-Lorraine"].Tile33,workspace["Polish Republic"].Koenigsburg.Tile58)
and a picture of the thing.
Thanks!
well i know im late but i love the algorithm topics .
Anyways here is my idea why don’t u use queue system with bfs ?
