There are many algorithms that can be applied to maze generating, but the one I implemented is called recursive backtracking. Recursive Backtracking is when you travel to new adjacent grid spaces until you get stuck, then you back track until you get to a spot which is adjacent to an unexplored grid space. I followed a video tutorial by The Coding Train, who wrote their program in Javascript with p5.js, but I implemented the algorithm with python and presented it with graphics .py library.
This is a very visually appealing project and I hope to incorporate the A star algorithm in the future to solve the mazes that I generate! I am not sure how great a euclidean distance heuristic would work because often the solution to a maze is not short distance. It might be interesting to explore different heuristics. If you don't know what the A star algorithm is definitely check out the python version I wrote or just look it up!
Here are the videos I followed:
https://www.youtube.com/watch?v=HyK_Q5rrcr4
https://www.youtube.com/watch?v=D8UgRyRnvXU
https://www.youtube.com/watch?v=8Ju_uxJ9v44
https://www.youtube.com/watch?v=_p5IH0L63wo
Here is the code!!!
This is really fun to just watch and push the limits of the size of the maze. If you don't want to be hypnotized by the animation you can unindent update() by one so that it runs after the algorithm has finished. I wanted to save the maze afterwards into a picture but I only managed to save it in eps format. After I figure it out will definitely make another post on it!
Thank you for reading, check out The Coding Train for amazing content!
:)
Comments