Python Path Finding Tutorial - Breadth First Search Algorithm
Vložit
- čas přidán 4. 07. 2024
- This path finding tutorial will show you how to implement the breadth first search algorithm for path finding in python. The breadth first search algorithm is a famous Queue based algorithm that is used to generate a set of all possible paths for a given maze.
Source Code: techwithtim.net/tutorials/bre...
**************************************************************
WEBSITE: techwithtim.net
proXPN VPN: secure.proxpn.com/?a_aid=5c34...
Use the Code "SAVE6144" For 50% Off!
One-Time Donations: goo.gl/pbCE9J
Support the Channel: / techwithtim
Podcast: anchor.fm/tech-with-tim
Twitter: / techwithtimm
Join my discord server: / discord
**************************************************************
Please leave a LIKE and SUBSCRIBE for more content!
Tags:
- Tech With Tim
- Path Finding Python
- Beadth first search algorithm
- Python Tutorials
thank you sir for explaining this in simple manner
Thanku So much his would have made it a lot easier... You are One of my great Teacher Thanku
Thanks for the explanation, it's very helpful
Thaks for the video, great explanation!!!
thanks for this explaination it helps me to understand the concept
Hey thank you bro this was the best explanation of BFS
You explained very nicely but it would be better if you explain the codes on checking the validmoves and findEnd
I agree, the foundation of this algorithm is explained but without any explanation of validMoves() or findEnd(), it is difficult to understand how this algorithm is applied to this 'maze' situation
@@shallwebeginvg5750 I agree
Hey, just began learning Python and doing algorithm's like these is a great way to practise.
Instead of stepping through each direction and updating the x and y values, you can simply count the occurrences of "L" and "R" and finding the difference would give you the x offset which you can then add to the start position. The same can be done for the y coordinate.
Thanks for the tutorial!
practice* dont be a sucky british person please.
Fantastic video! Glad to see your programming skills > than your drawing skills haha
xD
I try this out with the Breadth First Search Code algorithm, using a pattern in a maze I have.
I wonder if I understand this algorithm well enough.
Tree structure:
Starting node A, equal sign means those pathing are connected. G is the goal to reach.
Starting node A
A=B
B=CD
C=BE
D=BF
E=CGH
F=DI
G=
H=EJ
I=FJ
J=HI
Add B in queue, Visited B, Current queue B
Add CD in queue, Visited BC, Current queue CD
Add BE in queue, Visited BCE, Current queue GH
Visited BCEG. Reached G.
At the 3x3 grid you said the solution is LLDDD, or DDLLL. Why 3*D and 3*L? To me looks like it can reach the X only by 4 steps. LLDD or DDLL. Or you also counting the turn?
Pretty cool algorithm, never heard of it so not sure about the pronounciation but sounds right 👍
ironic you spelt pronunciation wrong
ahh, making sense. thank you!
Hi Tim. Amazing tutorial, please do more of these type of tutorials about algorithms. I have change this section of code to avoid reversing. It solves the maze in fraction time of original code (2.9s vs 0.0003s). What do you think? THX!!!
if valid(maze, put):
if len(put) < 3:
nums.put(put)
else:
if put[-1] == "L" and put[-2] != "R" or put[-1] == "R" and put[-2] != "L" or put[-1] == "U" and put[-2] != "D" or put[-1] == "D" and put[-2] != "U":
nums.put(put)
This was actually bothering me in the video. Thanks!
Thank you!!!!
you change it in the main function ?
Se te reza papi?
thanks
Hi, first of all thanks for the idea, explanation is great, which is why I subbed, I think your code is doing so much extra work that it might take decades for larger mazes, you should prevent it from going same route over and over again, for example from starting point it can go like U-D-U-D-U-D... or L-D-R-U-L-D-R-U-L....
@@mcmisterhd1920 or you can simply change already visited places with "#"
@@elnur0047 I agree with you!
One of the best explanations, Nice. Do you also have personal mentoring?
Pretty cool, but your variable names could be a lot clearer.
Where has the source code been removed to?
qeuque is also a seperate datastructure
Dammit - I was only doing this a couple of weeks ago; this would have made it a lot easier... :p
pro tip : you can watch series at flixzone. Me and my gf have been using them for watching all kinds of movies these days.
@Jakob Cayson Definitely, I've been watching on Flixzone} for since november myself :)
Hello! I am trying to create an indoor navigation, this algorithm can be used to do that or I should use A start
Nice video, thanks!!! Why is this necessary in the valid function please:
if not(0
To check if path is inside of the maze boundaries or not and if path doesn't lead to an obstacle
Hi,
I feel like the algorithm could be much more effective if we claimed steping "backwards" non-valid too. Why should we keep track of stepping backwards? If I step backwards in a maze I already know it is less effective than some other path.
By backwards I mean opposite of the move before: If I go Down, why would I allow going up the very next move? This creates a lot of redundant paths every move. In the end of the example algorithm, you are keeping track of hundreds of paths, but 99% of them are redundant.
These are examples of redundant paths:
DUDUDUDUDUD
DRLRLRLRLRL
DLRLRLRLRLRL
This was the correct solution: DLDDRDDDDRRD
This solution is already not correct: DUDLDDRDDDDRRD, because we repeat ourselves in the beginning.
Am I wrong?
Can you also tell how to build a maze using bfs.
can u pls make also DFS explanation and code? i would be very happy. THX
werent you generating redundant binary numbers in your binary example? Isn't 0 == 00 == 000? or 1 == 01 == 001?
Hey,
when you make move then if there is two vaild paths right and down then what path will be decide ?
Both paths are added to the queue. The queue stores all valid moves until the destination is reached, in which case it will pick the current stored (shortest) path.
What if there is no path
the code does not run!, how to run it?
This code not remove , visited node right ?
Hey Tim, I am at a very confused point right now. I have learnt basic python from a number of CZcams videos. My goal is to learn artificial neural networks . Can you please tell me, what should I do now , to be able to understand and make such ai to solve the maze or tic tac toe games like you are doing in this video ?
hi same i am also stuck at this point where ik the basics but idk how to impliment minimax algoritams into my tictactoe games
have you found found a way to learning all these
Not yet
Enlight me, guru! I had this stuff as a prerequirement in the first Semester - the examination was peanuts.... This requires twisted brain loops.
Hey, Thanks for the awesome video. How do I terminate in case there is no solution?
I was considering keeping a max limit on the len(put).
That could work!
Don't know if you still need help on this. If you just went left "L" then there's no point in going right "R". So only put a new path if it's valid and it doesn't go back to the previous position.
"The page you're looking for doesn't exist or has been moved."
wtf, how did someone figured out the binary algo in the first example!
Algorithm is easy, but I couldn't understand the code.
Hey Tim, I have a competitive programming contest coming up in a day, I'd be grateful if you can reply as early as possible.
How many times will I need to run this code before saying that there is no path?
Only once
@@TechWithTim what I meant was, instead of using an infinite while loop, if I use a for loop how many iterations do I need
@@arujbansal there's no way of telling there's no exit. Just add a limit. A great adaptative limit is to set it to the size of the map (if the map is 8 by 8, once you get a result that has a length of 64, break the loop because you've at least made all the logical combinations) or in case you have a decision tree, just limit the iterations to the maximum value of the decision tree. Let's say you want to find a binary result for the queue Tim showed in the video, then you'll have to consider 2**15 possibilities, so this would be the limit to break the loop
"Breadth-first search algorithm explained extremely in-depth." Where I can find video briefly explaining the depth-first search? //troll_mode=off ;)
I copied the source code, but it's not working on my Python :(( (I have 3.8)
edited: I think it only works on Python 2.7.16
try using the following code:
import Queue as queue
import sys
def createMaze():
maze = []
maze.append(["#","#", "#", "#", "#", "O","#"])
maze.append(["#"," ", " ", " ", "#", " ","#"])
maze.append(["#"," ", "#", " ", "#", " ","#"])
maze.append(["#"," ", "#", " ", " ", " ","#"])
maze.append(["#"," ", "#", "#", "#", " ","#"])
maze.append(["#"," ", " ", " ", "#", " ","#"])
maze.append(["#","#", "#", "#", "#", "X","#"])
return maze
def createMaze2():
maze = []
maze.append(["#","#", "#", "#", "#", "O", "#", "#", "#"])
maze.append(["#"," ", " ", " ", " ", " ", " ", " ", "#"])
maze.append(["#"," ", "#", "#", " ", "#", "#", " ", "#"])
maze.append(["#"," ", "#", " ", " ", " ", "#", " ", "#"])
maze.append(["#"," ", "#", " ", "#", " ", "#", " ", "#"])
maze.append(["#"," ", "#", " ", "#", " ", "#", " ", "#"])
maze.append(["#"," ", "#", " ", "#", " ", "#", "#", "#"])
maze.append(["#"," ", " ", " ", " ", " ", " ", " ", "#"])
maze.append(["#","#", "#", "#", "#", "#", "#", "X", "#"])
return maze
def printMaze(maze, path=""):
for x, pos in enumerate(maze[0]):
if pos == "O":
start = x
i = start
j = 0
pos = set()
for move in path:
if move == "L":
i -= 1
elif move == "R":
i += 1
elif move == "U":
j -= 1
elif move == "D":
j += 1
pos.add((j, i))
for j, row in enumerate(maze):
for i, col in enumerate(row):
if (j, i) in pos:
sys.stdout.write ("+ ")
else:
sys.stdout.write (col + " ")
sys.stdout.write('
')
def valid(maze, moves):
for x, pos in enumerate(maze[0]):
if pos == "O":
start = x
i = start
j = 0
for move in moves:
if move == "L":
i -= 1
elif move == "R":
i += 1
elif move == "U":
j -= 1
elif move == "D":
j += 1
if not(0
Additionally, make sure you already did "pip install queuelib" in terminal (if using mac)
@@human.earthling Thanks ❤️
How to find the shortest path in this algorithm
Never trust a programmer without dark mode
can you please help me with my work. I have been given a maze diagram, I am asked to find the shortest path and also make a function that can test if there is a path it should give value 1 if not then 0. please contact me asap your help would be a great. I have to do this assignment in 2 days max :)
You asked but no one answered, it is breadth, not breadth's.
lol nice dirty mike and the boys flag
Thanks lol
thanks