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
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!
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)
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?
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.
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....
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?
Hey Tim, I am at a very confused point right now. I have learnt basic python from a number of UA-cam 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 ?
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.
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?
@@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
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.
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 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.
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?
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?
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.
thank you sir for explaining this in simple manner
Fantastic video! Glad to see your programming skills > than your drawing skills haha
xD
Pretty cool algorithm, never heard of it so not sure about the pronounciation but sounds right 👍
ironic you spelt pronunciation wrong
Where has the source code been removed to?
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
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!
Pretty cool, but your variable names could be a lot clearer.
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 :)
qeuque is also a seperate datastructure
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?
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
Hey thank you bro this was the best explanation of BFS
werent you generating redundant binary numbers in your binary example? Isn't 0 == 00 == 000? or 1 == 01 == 001?
thanks for this explaination it helps me to understand the concept
One of the best explanations, Nice. Do you also have personal mentoring?
Hey Tim, I am at a very confused point right now. I have learnt basic python from a number of UA-cam 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
Thaks for the video, great explanation!!!
thanks
ahh, making sense. thank you!
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
Enlight me, guru! I had this stuff as a prerequirement in the first Semester - the examination was peanuts.... This requires twisted brain loops.
Hello! I am trying to create an indoor navigation, this algorithm can be used to do that or I should use A start
wtf, how did someone figured out the binary algo in the first example!
What if there is no path
This code not remove , visited node right ?
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.
"The page you're looking for doesn't exist or has been moved."
the code does not run!, how to run it?
Never trust a programmer without dark mode
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
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 ❤️
"Breadth-first search algorithm explained extremely in-depth." Where I can find video briefly explaining the depth-first search? //troll_mode=off ;)
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.
You asked but no one answered, it is breadth, not breadth's.
Algorithm is easy, but I couldn't understand the code.
How to find the shortest path in this algorithm
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 :)
lol nice dirty mike and the boys flag
Thanks lol
thanks