Python Path Finding Tutorial - Breadth First Search Algorithm

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.

**************************************************************

Use the Code "SAVE6144" For 50% Off!

**************************************************************

Please leave a LIKE and SUBSCRIBE for more content!

Tags:
- Tech With Tim
- Path Finding Python
- Beadth first search algorithm
- Python Tutorials

[SG-zk]

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)

[lastency]

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

[avvn]

thank you sir for explaining this in simple manner

[edster]

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

[kumarsaksham]

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

[deadlock]

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 👍

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

[elnur]

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

[sauldeleonn]

Thanks for the explanation, it's very helpful

[abulmeah-ne]

Where has the source code been removed to?

[rorisangpetja]

Hey thank you bro this was the best explanation of BFS

[compucademy]

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

[JoshKit]

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

[stepanomelka]

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?

[simplepycodes]

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

[osamaalsahli]

Hello Tim, we used this code in a project for a university module, and it was very helpful, but now the "source code" page shows an error, and I need it for referencing. Can you fix it please? Really appreciate it.

[dhrumilchavda]

thanks for this explaination it helps me to understand the concept

[mrt_]

qeuque is also a seperate datastructure

[alfredoderodt]

Thaks for the video, great explanation!!!