Spelling made exciting in a labyrinthine maze!

Last week, my son Isaac was crushed by his 3rd-grade spelling test. For an 8-year-old, it can be difficult to study something that might seem opaque in its usefulness. So, with a bit of Python magic, let us engage the children in solving a spelling maze!

The idea is to accept the input of a word, then generate a maze where the path to success is made easier if you know the next letter of the word.

Just Passing Through (TL;DR)

I figured I would need the ability to 1) generate a maze, 2) find all the junction points of that maze, and 3) draw letters at the junctions which lead the player down the correct route.

I built infrastructure and foundational code to perform functions like determining block positions, drawing the maze, and cleaning up relationships between blocks. Separately, I created a Maze class, which handled the maze-generation algorithm. I treated this Maze class as a parent to the WordMaze class which handles many of the functions related to letter placement. This helped de-clutter the Maze class and extend its functionality.

At the end of my project journey, I developed the code to apply words in the maze. This part became pretty complex, as I needed many parameters to be met so that the letters would group properly and the possible “incorrect” letter junctions along the solution route would be challenging enough. There were bugs to iron out, but eventually the code worked. Even better, soon a kid will be learning his spelling list and having fun at the same time!

Staying for a While (Technical Peeps)

The code for this project can be found at my GitHub.

Infrastructure and Foundational Code

After writing a toy maze generator, it was clear that I would need to build some foundations to help reduce the top-level complexity of the maze generation code. The three main foundational classes were:

• A Map Class
• A Draw Class
• A Path Class

Foundational Code: Map Class

The map class handles the grid of blocks to represent a player’s position at any point in the maze. It performs the following functions:

• Block relationships, including entry and exit directions
• Block positions, including x-y coordinate grid

Foundational Code: Draw Class

The draw class (‘Drawable2D’ in the code) is responsible for drawing to a grid of pixels, as defined by the object itself. This is an inheritable class allowing an object to set its pixel width and height and call functions like ‘fill,’ ‘draw_portion,’ or ‘draw_edge.’

The object inheriting from this class must implement a ‘draw’ method instructing how to draw itself.

Foundational Code: Path Class

This class is responsible primarily for generating random paths using the ‘step_path’ function. By moving this logic to its own class, we radically reduce the complexity of generating the maze.

Now that we have a high level view of the classes involved, let’s get into the actual maze generation!

Maze Generation

The code is available at my GitHub, but I will include the chunks of code I am referencing as we go along. For this section we will look at the ‘generate_maze’ function in the Maze class, as shown below:

def generate_maze(self):
    # Setup our start and end blocks
    self.map_start = self.map.get_start_block()
    self.map_end = None

    # We always go from North to South
    self.map_start.entry_direction = GridDirection.North

    # Setup our temporary algorithm variable
    new_start = self.map_start 

    # Start our Algorithm
    while not self.map_end:
        # Generate random paths from our starting block
        self.generate_paths(new_start)
        
        # Get the lowest block and set an exit direction (South)
        y, lowest_block = self.get_lowest_block()
        lowest_block.exit_directions.add(GridDirection.South)

        # If we have hit the bottom of the play area make this our end block
        if y == self.map.grid_height - 1:
            self.map_end = lowest_block
        # If we haven't hit the bottom then make this our next start block for random paths
        else:
            new_start = self.map.get_block_in_direction(lowest_block, GridDirection.South)
            new_start.entry_direction = GridDirection.North

    # Draw the final maze
    self.map.draw()

Firstly, we only make Mazes that start at the top and end at the bottom. With this basic tenet, we can say that we aren’t done building the maze until we have at least one block touching the southern edge of the grid. This is why our main while loop is checking for a ‘map_end’ block. We will be iterating the algorithm steps until we see such a block.

So first we grab the map’s start block, set that as our ‘new_start’ and generate paths from it. Once we have generated the paths for ‘new_start,’ we get the lowest block explored on the grid. If this block is touching the southern edge of the grid, we are done! If it isn’t touching the southern edge, then we set the southern edge as an exit. Next, we get the block south of this block and set it as ‘new_start’ and let the algorithm run again.

Generate Paths

The ‘generate_paths’ function (code below) is a random depth-first search algorithm that will generate random exits as it goes on its current search.

def generate_paths(self, start_block: Block):
    # Setup our Algorithm temporary variables
    possible_path_starts = [start_block]

    # While we have possible path starts continue building
    while possible_path_starts:
        # Randomly choose our next path start and remove it from the list
        current_start = random.choice(possible_path_starts)
        possible_path_starts.remove(current_start)

        # If this block is already explored move on
        if current_start.explored:
            continue
        
        # Otherwise create a new path and step it until it is finished
        path = Path(self.map, current_start)
        while not path.complete:
            possible_path_starts.extend(path.step_path())

Below is a GIF of how this algorithm looks when it is running.

It will eventually produce a maze like this:

All right, so we have a maze generated! Now how do we get our word in there to guide our kid to the spelling solution?

Putting Spelling Words in the Maze

With perfect 20/20 hindsight, I probably would have included exit count in path creation when I was working on the maze generator. I hadn’t considered how to control the number of exits on the solution path until I tried applying a word to it. The problem is our solution path must have exactly the same number of junctions as there are letters in our target word. This means if we have too many junctions on our solution path, we must do something to remove them.

I had a few ideas on how to do this with simple algorithms that I thought for sure would do exactly what I wanted them to do… None of them worked for various reasons, largely due to bugs in the foundational code.

I created multiple band-aids to mitigate these problems. If the band-aids stacked too high, I would eventually sift the code down to where it belonged. However, I will warn the reader, none of the code that I submit here is pretty. This was one of those “quickly written/get the thing working!” kind of projects. Should it be deemed for long term use, I think a rewrite would be warranted and easily done. Anyway, on to the method that I chose!

Apply Word

The ‘apply_word’ method orchestrates all the steps in adding letters to our maze and is included in a child class of the Maze class called… WordMaze.

def apply_word(self):
    exit_count = len(self.word)
    solution_junctions = self.get_solution_path_junctions()
    
    if len(solution_junctions) < exit_count - 1:
        raise IndexError("Not enough exit points to write word!")
    
    # Randomly select the junctions to be used for our word path
    selected_junctions = self.select_solution_path_junctions(solution_junctions)

    # Close off and unexplore all other junctions
    self.close_all_solution_path_junctions(solution_junctions, selected_junctions)

    # Reopen paths for unexplored areas on valid routes
    self.fill_out_unexplored_areas()
    
    # Apply letters to junctions
    self.apply_letters_to_junctions()

Put simply, after we have generated a maze using our parent class, we find all junctions in the map and select ones that are located along the solution path. From this smaller set, we randomly choose the junctions we want to use for the letters of our word (this shortens the list further).

With our solution letter junctions selected, we need to get rid of all other junctions along the solution path. So, we close off their entry and “un-explore” them, meaning we reset them to the original state they held before we applied any path algorithm to them.

At this point we have a pretty boring maze, and it likely is pretty easy to distinguish which path is the right one because we “un-explored” all but the ones chosen for our letters. To increase complexity, we open the dead-ends of our selected paths, exploring them until the dead space is accessible again from the selected junction.

If this is still confusing, stick with me, we have some visual elements below that will hopefully fill any gaps of understanding. First, let’s break down the important methods included in the code block above that follow the steps I just described.

get solution path junctions

This function gets all of the junctions in the map and randomly selects ones that exist on the solution path.

select solution path junctions

Of the set of junctions that exist on the solution path, select only as many as there are letters in our target word. Do this selection at random.

close all solution path junctions

This closes all of our non-selected solution path junctions and marks the blocks in the path closed off from the solution path as not explored.

Fill out unexplored areas

Now that we have a bunch of unexplored territory, let’s re-explore it from the dead ends of the selected paths. This should make the puzzle a bit more…puzzling!

Apply Letters to junctions

Finally, let’s get some letters at the junction exits. This method will iterate all junctions, giving them each a random letter. Then, it will iterate all the solution path blocks in order, applying the correct letter of the word to each. To make things a bit more tricky in the orthogonal direction of the solution path, we put the letter that comes after the correct letter.

Below is a GIF showing the re-exploration of unexplored map area:

With re-exploration completed, we can perform letter application. Below is the result of running the following command:

python3 ./main.py --word Discover

Conclusion

Spelling is difficult for many youngsters my son’s age. I hope that doing puzzles will push it just far enough over the edge of engagement to keep him moving forward. I want to thank you for sticking with me through this post. I hope the ideas and implementation I shared were thought-provoking. If you have any thoughts inspired by this post, please feel free to leave a comment below.

Also, if there is interest, I can push a web version of this application so that you can generate spelling mazes from a webpage instead of having to run it on your local machine.

Thanks for reading!

Spelling Maze Code

The code for this project can be found at my GitHub.

My Related Work

If you find algorithms interesting and would like to read more about another project of mine, check out another interesting algorithm problem from my PaperBoy VR Game.