Dead-end filling maze solver in Python

Question

I was reading Wikipedia about maze-algorithms, and I decided to write my own maze-solver. It uses dead-end-filling as it seemed simple to implement (it seemed, I said).

The code I wrote is pretty massive, 179 lines including documentation and tests, but I like that it solves my easy examples.

I included some ASCII-animation code inside my code, as it is incredibly satisfying to see a maze being programmatically solved.

import doctest
import time

BLOCKED = 1
EMPTY = 0

SMALL_MAZE =  [
    [1, 1, 1, 1, 1],
    [0, 0, 1, 1, 1],
    [1, 0, 0, 0, 0],
    [1, 1, 0, 1, 1],
    [1, 1, 1, 1, 1] ]

BIG_TEXT_MAZE = """
**************************
*                        *
** ********************* *
   *                   * *
*    **** ****************
*       *                 
**************************
"""

SMALL_TEXT_MAZE = """
******************
**   **** *** ****
****       *     *
**   ** **** *****
**** **   **    **
      * **** *****
*******           
******************
"""


def maze_repr(maze):
    """
    Prints a nice textual represenatation of a maze.
    '*' indicates a wall, ' ' a corridor.

    >>> print(maze_repr( [ [1, 1, 1, 1], [0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 1, 1] ]))
    ****
      **
    *   
    ****
    """
    string_maze = ""
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            string_maze += "*" if maze[y][x] else ' '
        string_maze += "\n"
    return string_maze[:-1]

def read_maze(text_maze):
    """
    The opposite of `maze_repr`, given a textual maze, builds
    a list of lists from it.

    >>> read_maze("****\\n  **\\n*   \\n****")
    [[1, 1, 1, 1], [0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 1, 1]]
    """
    return list(map((lambda row:  [1 if square == '*' else 0 for square in row]),
                    (i for i in text_maze.split("\n") if i)))

def nears(curr_x, curr_y, maze):
    """
    Returns the squares from which you may go doing one
    step in any of the four cardinal directions
    (NORD, EST, WEST, SOUTH).

    The result consists of:
    * 2 squares if (x, y) is on the corner,
    * 3 squares if (x, y) is on the side,
    * 4 squares otherwise.

    >>> list(nears(1, 0, [ [2, 1, 3], [1, 4, 6] ]))
    [3, 4, 2]
    """
    for (x, y) in ( (curr_x + 1, curr_y), (curr_x, curr_y + 1),
                    (curr_x - 1, curr_y), (curr_x, curr_y - 1)):
        try:
            if x >= 0 and y >= 0:
                yield maze[y][x]
        except IndexError:
            pass

def is_dead_end(x, y, maze):
    """
    Is the square at (x, y) of the maze a dead end?
    A wall can not be a dead end.

    Interenstingly enough, using 2 or 1 instead of 3
    creates some nice chambers in the labirith instead of solving it.

    A square circled by 4 walls is also a dead end, in the case of
    solitary closed inacessible rooms in the labirinth.

    >>> is_dead_end(2, 1, read_maze(SMALL_TEXT_MAZE))
    True
    """
    if maze[y][x] == BLOCKED:
        return False
    return list(nears(x, y, maze)).count(BLOCKED) in (3, 4)

def fill_one_dead_end(maze):
    """
    Fills the first encountered dead end of the maze.

    >>> print(maze_repr(fill_one_dead_end(SMALL_MAZE)))
    *****
      ***
    *    
    *****
    *****
    """
    new = maze[:]
    found_dead_end = False
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            if (not found_dead_end) and is_dead_end(x, y, maze):
                found_dead_end = True
                new[y][x] = BLOCKED
            else:
                new[y][x] = maze[y][x]
    return new

def has_at_least_one_dead_end(maze):
    """
    Does the maze have at least one dead end?

    >>> has_at_least_one_dead_end(read_maze(BIG_TEXT_MAZE))
    True
    """
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            if is_dead_end(x, y, maze):
                return True
    return False

def solve_maze(maze, logging = False):
    """
    Solves mazes where the corridors are one wide,
    filling all the dead ends.

    >>> maze = read_maze(SMALL_TEXT_MAZE)
    >>> print(maze_repr(solve_maze(maze)))
    ******************
    ******************
    ****    **********
    **** ** **********
    **** ** **********
         ** **********
    *******           
    ******************
    >>> maze = read_maze(BIG_TEXT_MAZE)
    >>> print(maze_repr(solve_maze(maze)))
    **************************
    **************************
    **************************
       *      ****************
    *    **** ****************
    *    ****                 
    **************************
    """
    if logging:
        print(maze_repr(maze), end="\n\n")
    while has_at_least_one_dead_end(maze):
        maze = fill_one_dead_end(maze)
        if logging:
            print("\n"*50)
            print(maze_repr(maze), end="\n\n")
            time.sleep(0.2)
    return maze

def main():
    solve_maze(read_maze(SMALL_TEXT_MAZE), logging = True)
    solve_maze(read_maze(BIG_TEXT_MAZE), logging = True)
    doctest.testmod()

if __name__ == "__main__":
    main()

If you're using a style guide other than PEP-8 could you provide a link to it? Also, why have you rolled your own logging? — jonrsharpe
– jonrsharpe, Commented Sep 21, 2015 at 16:08

alexwlchan · Accepted Answer · 2015-09-21 17:11:04Z

Here are some general comments:

All of your functions take a maze argument. This shared state is a sign that you could create a class and define methods on that, rather than continuously passing state around.
A lot of your code is quite busy and difficult to read. I’ve provided some examples of more readable versions in the feedback below; try not to pack so much onto one line.
You take an interesting approach to printing the result to stdout. Printing 50 newlines between iterations will ensure that the previous iterations disappears off the screen (although not on my monitor; I have a portrait display), but a well-behaved program shouldn’t scribble all over my terminal window.

I haven’t used it in a while, but there are modules like blessings which let you modify what’s already been printed to stdout. You might also want to watch Thomas Ballinger’s PyCon talk Terminal whispering, which features a bunch of clever things like this.
There are times when your code deviates from PEP 8, the Python style guide. You might want to brush up on it a little.

Some detailed feedback on individual functions:

Your maze_repr() function is a bit fiddly. Rather than doing lots of string concatenations, you could just use some str.join()s:
```
row_strings = []
for row in maze:
    row_strings.append(''.join('*' if elem else ' ' for elem in row))
return '\n'.join(row_strings)
```
That also saves you dropping the trailing newline at the end. (I recommend dropping trailing whitespace with str.strip() instead of taking a slice, incidentally.)

Also, repr(obj) usually means “a string I could eval() to get an equivalent instance”; that’s close but not quite what you’re doing here.
Your read_maze() function is doing far too much on a single line. It’s very difficult to read and unpack; space it out over more lines for readability. Here’s a clean, spaced-out version o your code:
```
rows = []
for line in text_maze.splitlines():
    if not line:
        continue
    rows.append([1 if char == '*' else 0 for char in line])
return rows
```
I also prefer str.splitlines() instead of .split('\n'). I think it’s more readable, and I slightly more portable (for platforms where '\n' isn’t the line ending.)
The nears() function is mostly fine, except I’d change the docstring so the order of directions is the same as the order returned.
- Docstring: North East West South
- Function: East North West South
It’s good to be consistent.
In your fill_one_dead_end function, you can return as soon as you find a single dead end, and do away with the found_dead_end variable. The rest of maze has already been copied into new, so there’s no more work to do here: just exit early and return new.

Stack Exchange Network

Dead-end filling maze solver in Python

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Dead-end filling maze solver in Python

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions