Build a maze with Python
Some months ago I failed an interview question from Google that required me to write a program to navigate a maze in the least amount of steps, it is by no means a small task since a very popular book on AI ( AI a modern approach ) devotes a lot of pages to this subject, but what I got stumped with and found more interesting was the code needed to make a maze ( which wasn’t provided ) and since I like GUIs and games I thought it would be a cool little thing to learn about, so without much ado, here we go, we’ll be making a basic maze game in python !
Here's the code snippets in Repo form if you prefer...https://github.com/KenoLeon/Medium-Mazes
Step 1. The first thing we need is a canvas/data structure where we can draw structured data, a numpy backed grid fits the bill nicely, I am using PySimpleGui + numpy but you can use another GUI library if you wish, I will also be using and modifying some grid functions from a previous post on Grids ( but you can skip reading it if the code makes sense to you ) :
Should give you:
Notes: We are using square grids to make our life easier, so a grid with cellCount 10 is a 10x10 grid. There are drawGrid() and drawCell(coordinates) methods for drawing the grid and placing a single cell. In order to read a numpy array as the map for the grid, uncomment the placeCells() call, should give you a populated grid based on the random numpy cellMap array.
Step 2: It would be nice if we could move around the canvas with the up/down/left/right arrows of the keyboard, so lets tie those events to moving a player:
How it works: We now have a new variable: _VARS['playerPos': [x, y]] which is simply the player position, when you press the up/down/right/left arrows, this variable get's modified (add/subtract 40 to the x, y coordinate so it snaps to the grid), then we clear and redraw the grid and player and voila we have player control and movement.
Step 3 : Slight snag, the player is moving now but has no concept of boundaries so it keeps going beyond the grid limits and then disappears. This is a good time to introduce some movement restriction logic that we can later use to make the maze walls…
In order to enforce some boundaries around the grid, we need to modify the event loop, so on the upper limit it would look like this:if (_VARS['playerPos'] - 40 >= 0)... if the position is greater than zero we can draw the change in position, else we don't, for the opposite end we use 400 as a limit since our gridSize is 400.
The player should now stay inside the grid.
Step 4. So we now have a playpen, in order to make it into a maze we still need a couple of key mechanics; for starters we’d need to make walls inside the maze and have the player know there are there so it can’t move over them.
The logic is identical to the one used for the outer grid walls but here we read the numpy array and check if the cell in question is not 1 ( which represents a wall ), here for instance we check before moving to the left if there's a wall:if cellMAP[yPos][xPos-1] != 1Note: There's a few other changes in this script, we now have an orange tile that stands for the player along with less hardcoded values, so you can experiment by changing the size and cell count for instance.
Step 5. Almost there, the last thing we need to do to have a rudimentary puzzle game is to add an exit tile, ( same logic ) we simply create a new variable with the exit coordinates and draw it, then we check the players coordinates and if they match the exit has been found:
You should now be able to place an exit and recognize when it has been reached:
I said at the start that we were going to try and make a maze game and well there it is, but it is by no means a good or robust maze program, you should by now have a sense of what goes into making a maze though, so what follows is completely optional and might not apply to your project or needs…
Randomly generated mazes. It sure would be an improvement if instead of reading a predefined maze we could create a random one each time, that way we also get to experience it for the first time like any other player.
This seemingly small request turns out to be a fairly complicated one, my ( your ) first instinct might be to simply feed the cellMap a random numpy array…
# This snippet creates a random maze and clears the entry and exit points.cellMAP = np.random.randint(2, size=(_VARS['cellCount'], _VARS['cellCount']))cellMAP = 0
cellMAP = 0
The problem with this approach is that we have no way to guarantee there is a solution to our maze and in order to do so ( find a solution ) we would need to traverse the maze and find the exit BEFORE we present it to the user, that way we can guarantee that the maze is solvable ( unlike this one ):
There are many ways to create and solve mazes, the subject is a favorite of AI, mathematics and computer science, it is a rabbit hole, here are some entry points:Maze generation, Pathfinding and maze solving.
To get you started here’s something I put together that works about 90% of the time, I’ve also added a function and button to make a new maze in case the resulting maze is not solvable (a game feature ?)…
And here are a few of the mazes created :
Next steps & conclusion.
I am leaving aside pathfinding ( ie traversing the maze before it is presented ) because as mentioned the subject can get deep, especially if you add search algorithms ( you are looking for an exit after all ). Another reasonable upgrade you might want is to have graphics and complex walls instead of simple cells, the core logic would be the same but you’d probably need to load images and add extra logic for complex walls, and finally you can get creative with the game logic, you could for instance add a timer, shifting walls, enemies etc, etc.
Speaking of improvements, if you were making a game you might want to use classes instead of a global dictionary to store things like position and command the player to move, so you would have a player class and even a grid/maze class with class methods and properties ( playerPos, movePlayer, createMaze etc, etc), I chose not to use classes because while handy they add another abstraction layer that might get in the way of learning the basics, in any case there should be plenty of examples of small games that do use classes out there to complement your learning, I didn't look at other maze tutorials while making this, but you probably should if you want a second or third opinion.
I hope though that these code snippets and scripts give you a starting point and code samples of how to make a maze in python.
Thanks for reading !