Python Path Finding Tutorial - Breadth First Search Algorithm

[@lastency]

You explained very nicely but it would be better if you explain the codes on checking the validmoves and findEnd

[@shallwebeginvg5750]

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

[@AndrewSeanego]

@@shallwebeginvg5750 I agree

[@wrathfeeling]

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.

[@SG2024-z7k]

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)

[@marmoripelaao9830]

This was actually bothering me in the video. Thanks!

[@Jacob___Kozak]

Thank you!!!!

[@zatmax5764]

you change it in the main function ?

[@abeljaimeriveraolaza4426]

Se te reza papi?

[@avvn9331]

thank you sir for explaining this in simple manner

[@edster512]

Fantastic video! Glad to see your programming skills > than your drawing skills haha

[@TechWithTim]

xD

[@kumarsaksham5651]

Thanku So much his would have made it a lot easier... You are One of my great Teacher Thanku

[@compucademy]

Pretty cool, but your variable names could be a lot clearer.

[@deadlock107]

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?

[@HostDotPromo]

Pretty cool algorithm, never heard of it so not sure about the pronounciation but sounds right 👍

[@djlazer1]

ironic you spelt pronunciation wrong

[@elnur0047]

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....

[@elnur0047]

​@@mcmisterhd1920 or you can simply change already visited places with "#"

[@leooel4650]

@@elnur0047 I agree with you!

[@sauldeleonn]

Thanks for the explanation, it's very helpful

[@abulmeah-n1e]

Where has the source code been removed to?

[@rorisangpetja4624]

Hey thank you bro this was the best explanation of BFS

[@m4rt_]

qeuque is also a seperate datastructure

[@rtcodes4618]

Nice video, thanks!!! Why is this necessary in the valid function please: if not(0

[@pedroduque9705]

To check if path is inside of the maze boundaries or not and if path doesn't lead to an obstacle

[@JoshKit]

Dammit - I was only doing this a couple of weeks ago; this would have made it a lot easier... :p

[@jakobcayson8644]

pro tip : you can watch series at flixzone. Me and my gf have been using them for watching all kinds of movies these days.

[@anthonythomas489]

@Jakob Cayson Definitely, I've been watching on Flixzone} for since november myself :)

[@stepanomelka7880]

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?

[@sirknumbskull3418]

Enlight me, guru! I had this stuff as a prerequirement in the first Semester - the examination was peanuts.... This requires twisted brain loops.

[@simplepycodes]

One of the best explanations, Nice. Do you also have personal mentoring?

[@dhrumilchavda2585]

thanks for this explaination it helps me to understand the concept

[@alfredoderodt6519]

Thaks for the video, great explanation!!!

[@sainco3036]

thanks

[@kennethazor]

ahh, making sense. thank you!

[@mariacunha8508]

"The page you're looking for doesn't exist or has been moved."

[@devhalder7799]

Hey Tim, I am at a very confused point right now. I have learnt basic python from a number of KZbin 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 ?

[@packirisamykaran6986]

hi same i am also stuck at this point where ik the basics but idk how to impliment minimax algoritams into my tictactoe games

[@packirisamykaran6986]

have you found found a way to learning all these

[@devhalder7799]

Not yet

[@mariamkhanam4037]

Never trust a programmer without dark mode

[@jakubbalog1590]

can u pls make also DFS explanation and code? i would be very happy. THX

[@JonAkdogan]

Algorithm is easy, but I couldn't understand the code.

[@ashishb7636]

Can you also tell how to build a maze using bfs.

[@yfchina143]

wtf, how did someone figured out the binary algo in the first example!

[@anonlegion9096]

werent you generating redundant binary numbers in your binary example? Isn't 0 == 00 == 000? or 1 == 01 == 001?

[@dmonitize9011]

You asked but no one answered, it is breadth, not breadth's.

[@adityaprasad4463]

What if there is no path

[@stgiven1882]

Hello! I am trying to create an indoor navigation, this algorithm can be used to do that or I should use A start

[@codespotlight9146]

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?

[@TechWithTim]

Only once

[@arujbansal]

@@TechWithTim what I meant was, instead of using an infinite while loop, if I use a for loop how many iterations do I need

[@Phoenixandcie]

@@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

[@mfatihkoc]

the code does not run!, how to run it?

[@mickon7404]

I copied the source code, but it's not working on my Python :(( (I have 3.8)

[@human.earthling]

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

[@human.earthling]

Additionally, make sure you already did "pip install queuelib" in terminal (if using mac)

[@mickon7404]

@@human.earthling Thanks ❤️

[@pavel9652]

"Breadth-first search algorithm explained extremely in-depth." Where I can find video briefly explaining the depth-first search? //troll_mode=off ;)

[@mithilanavishka4531]

This code not remove , visited node right ?

[@codecreed.521]

Hey, when you make move then if there is two vaild paths right and down then what path will be decide ?

[@shallwebeginvg5750]

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.

[@kisekihirakawa300]

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).

[@TechWithTim]

That could work!

[@b2stts2b37]

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.

[@Rajatkumar-tg3es]

How to find the shortest path in this algorithm

[@muhammadsaadmasood9329]

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 :)

[@maroso_]

thanks