This programme creates a maze in your terminal that is composed of standard letter characters. You can navigate the maze by typing compass directions into the terminal. You should try to go from the start to the goal.
It is based on an exercise from Classic Computer Science Problems in Python by David Kopec. You can read his code here. Following Kopec’s original, several algorithms - specifically Breadth First Search, Depth First search, and A* - traverse the maze, trying to find the optimal route.
However, I have supplemented the code with elements that make the programme function more as a game. The programme concludes by comparing the number of moves it to you to complete the maze with the algorithms. See if you can beat the algorithms!
As part of my ongoing efforts to learn Python, I’ve been working through a book called Classic Computer Science Problems in Python. it is part of a series of books by David Kopec that present classic computer science problems (no surprise there) in different programming languages. In addition to Python he has also published variants for Java and Swift.
I found the chapter on algorithms particularly interesting. The premise of the original programme was to create a grid with a start, goal and various obstacles along the way. It include several algorithms, namely Breath First Search, Depth First Search, and A* to traverse the grid from start to finish.
The purpose of the programme was to demonstrate how different search algorithms work and how they can be more or less efficient.
It demonstrated how several traditional search algorithms could be used to navigate a maze from start to finish. Specifically Breath First Search, Depth First Search, and A*.
Certainly an interesting topic to learn about, but what really intrigued me was the visual output Kopec included. The programme would generate grids on terminal, made from basic key characters, demonstrate the course each algorithm to through the maze.
These visualisations reminded me of classic dungeon crawlers, like Rogue, where the player would similarly traverse a map made from simple characters. Of course these games included many other elements such as enemies, items, and more elaborate maze structures. But I immediately thought Kopec’s code could be enhanced with some way to interact with the map.
For the most part I’ve retained Kopec’s original code but change a few details and added some elements to make it play more like a game.
I’d recommend following along with the code in my Github repository. I would post snippets here but I the code gets rather gnarly (more on that later) and I think it would make reading this post quite difficult.
In the original, if a solution was possible the programme would draw the grid with the solutions each algorithm found by the different algorithms. I added a new class MazeMovement, which includes functions to prompt the user to input directions to navigate the maze, as well to keep track of where the player is in the maze. I also added a method goal_reached to verify that the maze has a solution before letting the player attempt it - no point letting someone attempt to navigate a maze if there is no solution.
Finally, I added some logic to compare the number of moves the player takes to complete the maze with the algorithms.
I’m mostly happy with my code here. I feel it extend Kopec’s original idea to demonstrate how different algorithms work in a fun way. But of course there are some things I’d like to improve.
For one thing, implementing the elements to make the programme behave more game-like was quite challenging. it took some effort to think about how to keep track of the state of the game and include some quality of life checks, such as checking there is a solution to the maze beforehand.
I’ve no experience making games so it could just be my lack of familiarity that made this difficult. However, this did make me wonder if Python isn’t the best language for creating games. Perhaps using a framework like Unity or Unreal might be better.
As I was adjusting Kopec’s code, I did have some further thoughts on how I could make this an even better game. But I didn’t make these changes as I felt they would undermine the educational goals.
For instance, I had thought about including easy, hard, and extreme modes. Easy would be the code as it currently stands, hard would be similar, except the maze is revealed as the player traverses it, and extreme would allow navigation but show no map.
I didn’t implement these modes as I feel that seeing the map in its entirety is important to ‘beating the algorithm’. Otherwise it just becomes a game of how lucky you are in getting a simple map.
Having said that, to put in the other way around, if the beating the algorithm aspect were removed then you could make potentially a more challenging version of the game.
Similarly adding the traditional tenants of dungeon crawlers, like enemies, items and health and combat stats would improve the programme as a game.
Overall I feel this was a rather fun small project. I think it preserves Kopic’s original intent, demonstrating how the various algorithms work, but introduces an interactive component.
Of course, I’ve not discussed how the algorithms work in detail, check out Kopic’s book for that, or search online.
Also, as raised in the last section, there is quite a bit that could be done to improve the game dynamics here.
I’ll leave it to the reader to follow up on these.
Explore the algo maze! by William Samuel McDonald is licensed under CC BY 4.0