Solving Mazes in Python: Depth-First Search, Breadth-First Search, & A*

We will develop code to generate simple mazes in Python and find paths in them to navigate from a starting node to a goal node. Along the way, we will learn the fundamental search algorithms depth-first search, breadth-first search, and A*. To support these algorithms, we will also learn the stack, queue, and priority queue data structures.

The examples are from chapter 2 of Classic Computer Science Problems in Python.

All of the code is available in the chapter 2 folder of the Classic Computer Science Problems in Python GitHub repository.

The Maze Solving GUI is also available on GitHub.

I made a small mistake in the explanation of A*, I meant to say the explored dictionary is storing the g(n) so far, not the f(n). Sorry!

Follow me on Twitter

Find out more about the Classic Computer Science Problems series, including the books in Java and Swift

[martindeveloper]

It always surprises me that high quality videos are underrated and especially their creators.
The big problem I see in the video space is that people are only looking for short explanations and don't want to know the underlying things such as how is queue, stack and priority queue implemented. Even though those data structures are easy, this is not the point, the point I try to convey is that a approach from ground up takes longer to watch but in my opinion this facilitates the process of leaning the concept more easily and I guess also enabling the instructor to build on top of his explanation pyramid.

And also I love your real world examples especially the one with the priority queue and the email inbox, quite intuitive and this video is a lot fun. I searched for a video about getting a refresher in common graph search algorithms after watching a little bit more about Machine Learning.

Thanks a lot.

[matthewcarmody]

This is incredible, I cannot believe you dont have 100times more subscribers <3 thank you david

[AAAA-rbhm]

I recommended your book to our University library, and they bought it for us, thanks, David.

[akashkewar]

Amazing job @David Kopec. Waiting for more videos like this.

[enthusiastjumper]

Youtube algorithm did recommend something awesome finally.

[haniyehzahraee]

thank you so much I really need this course and its really usefull for me

[LiSek]

perfect way to show how dfs works! MIT proffesor also talked about mazes with dfs:)

[ironman]

i haven't read you book yet, but due to the headache you saved me, i'll be downloading it shortly, am working on a warehouse simulator

[hiloworle]

How can you modify the dfs in this example to have some utility.. for example... randomly generate the maze using the dfs itself.. and then solving using the BFs or astar..

[innocent.amchechesi]

Can you please solve a maze for the longest path using ant system algorithm

[kishanjotaniya]

how can i implement GUI which youve provided in github using a code of A* algo youve provided?

[abdallahaymanmohamedabuzai]

can you please provide us the A* gui implementation