"Amazing" from 101 BASIC Computer Games in Python

Question

I'm trying to write a program that duplicates the "Amazing" game from 101 BASIC Computer Games, in Python. I want it to create the same text mazes using the same characters, and so far I am limiting myself to a program that I can run from a command line, without creating a new GUI. My research has led me to the Wikipedia article "Maze Generation Algorithm" and the page "Think Labyrinth: Maze Algorithms," from the astrolog.org website.

My first thought was to write a program that would build the maze from nothing, but the majority opinion about maze creation seems to be to start with a grid, start at a cell, then write an algorithm that tests the cell's neighbors to see if they have been visited, and break down the wall between the current cell and a random new neighbor that hasn't been visited already.

So far, I have written a program that will generate the text grid according to user input of width and height:

    """Asks user for a width and height, then generates a text grid based on
    user input."""

    #Only two imports
    import random
    import sys

    width1 = int(input("What width do you want? "))
    height1 = int(input("What height do you want? "))

    #Text elements for the grid
    top_Line = ".--"
    top_End = "."
    mid_Line = ":--"
    mid_End = ":"
    yes_Wall = "  I"

    def grid_Top(width1):
        """Draws the top of a grid of user width."""
        top_Lst = []
        for i in range(width1):
            top_Lst.append(top_Line)
        top_Lst.append(top_End)
        return top_Lst

    def grid_Walls(width1):
        """Draws the walls of the grid."""
        walls_Lst = []
        walls_Lst.append("I")
        for i in range(width1):
            walls_Lst.append(yes_Wall)
        return walls_Lst

    def grid_Floors(width1):
        """Draws the floors of the grid."""
        floors_Lst = []
        for i in range(width1):
            floors_Lst.append(mid_Line)
        floors_Lst.append(mid_End)
        return floors_Lst

    def grid_Create(width1, height1):
        """Creates the grid of user width & height."""
        for i in grid_Top(width1):
            print(i, end = "")
        print("")
        for j in range(height1):
            for i in grid_Walls(width1):
                print(i, end="")
            print("")
            for i in grid_Floors(width1):
                print(i, end="")
            print("")

    grid_Create(width1, height1)

So, as it stands, each of my cells is defined by the ceiling above it, the walls to either side, and the floor below it. As it stands, this means that testing each cell for whether it has been visited or is intact involves looking at three lists - the previous list, the current list, and the next list, if you get my meaning.

My question is: How do I impose a structure onto my text grid so that each cell is its own entity, which can be tested for whether it has been visited in a depth-first search?

Any and all comments about my code will be welcome, whether or not they are relevant to the actual question I am asking!

Thanks!

Answer 1

I would use a set to explicitly track which cells have been visited:

visited = set()

if candidate_coord not in visited:
    visited.add(candidate_coord)
    break_wall(candidate_coord, curr_coord)