Python迷宫生成器：使用递归

Question

我希望用递归算法解决迷宫问题。程序打开一个像这样的文本文件：

10 20
1 1 
10 20
-----------------------------------------
|     |     | |     | | |       |     | |
|-+ +-+-+ +-+ + +-+ + + +-+-+ +-+-+ + + |
|         |       |     | | | |   | |   |
| + +-+ + + +-+-+-+ + + + + + +-+ + + + |
| | |   |     |     | |     |       | | |
| +-+-+-+-+ +-+ +-+-+-+-+ +-+ + +-+-+ +-|
| | | |       |   | |         | |   |   |
| + + +-+ +-+-+ + + + +-+ +-+ + + + +-+ |
|     |     |   | |     | |   |   | | | |
|-+-+ +-+-+-+-+-+-+-+ +-+ +-+-+ +-+-+ +-|
| |   |   |     |     |     |   | | | | |
| +-+-+ +-+-+ +-+ + +-+-+ +-+ +-+ + + + |
|       |     | | |   |   | | | |       |
|-+ +-+ + + +-+ +-+-+ + +-+ + + +-+ +-+ |
|   | | | |     | | | | | | | |   | | | |
|-+ + +-+ + + + + + +-+ + + + + +-+-+ + |
|       | | | |     |     |             |
| + + +-+ + +-+-+-+ + +-+ + + +-+-+ +-+ |
| | |     | |           | | | |     |   |
-----------------------------------------

文件的第一行是迷宫的大小（10 20），第二行是起点（1 1），第三行是出口（10, 20）。我想用“*”标记正确的路径。这是我的代码：

编辑：我在findpath()函数中更改了一些代码，现在我没有任何错误，但迷宫为空，路径（'*'）没有在迷宫上“绘制”。

class maze():    
    def __init__(self, file):

        self.maze_list = []

        data= file.readlines()

        size = data.pop(0).split()  # size of maze

        start = data.pop(0).split() # starting row and column; keeps being 0 because the previous not there anymore
        self.start_i = start[0]  # starting row
        self.start_j = start[1]  # starting column

        exit = data.pop(0).split()   # exit row and column 
        self.end_i = exit[0]
        self.end_j = exit[1]

        for i in data:  
            self.maze_list.append(list(i[:-1])) # removes \n character off of each list of list
        print(self.maze_list) # debug


    def print_maze(self):

        for i in range(len(self.maze_list)):
            for j in range(len(self.maze_list[0])):  
                print(self.maze_list[i][j], end='')                         
            print()

def main():

    filename = input('Please enter a file name to be processed: ') # prompt user for a file


    try:
        file = open(filename, 'r')
    except:                     # if a non-existing file is atempted to open, returns error 
        print("File Does Not Exist")
        return  

    mazeObject = maze(file)
    mazeObject.print_maze() # prints maze

    row = int(mazeObject.start_i)
    col = int(mazeObject.start_j)   

    findpath(row, col, mazeObject)  # finds solution route of maze if any

def findpath(row, col, mazeObject):

    if row == mazeObject.end_i and col == mazeObject.end_j: # returns True if it has found the Exit of the maze
        mazeObject.maze_list[row][col] = ' ' # to delete wrong path
        return True

    elif mazeObject.maze_list[row][col] == "|": # returns False if it finds wall 
        return False

    elif mazeObject.maze_list[row][col] '-': # returns False if it finds a wall 
    return False

    elif mazeObject.maze_list[row][col] '+': # returns False if it finds a wall 
        return False    

    elif mazeObject.maze_list[row][col] '*': # returns False if the path has been visited
        return False

    mazeObject.maze_list[row][col] = '*'   # marks the path followed with an *   

    if ((findpath(row + 1, col, mazeObject)) 
        or (findpath(row, col - 1, mazeObject)) 
        or (findpath(row - 1, col, mazeObject)) 
        or (findpath(row, col + 1, mazeObject))):    # recursion method
        mazeObject.maze_list[row][col] = ' '  # to delete wrong path
        return True
    return False    

那么现在我的问题是，错误在哪里？我的意思是程序只是打印出迷宫，没有解决方案。我想用“*”填充正确的路径。

- lux1020

---

你的问题是什么？请参考这个问题来了解你的错误含义，这可能会给你修复它的线索。 :) - puqeko

这个错误意味着你试图通过数字索引访问迷宫类的对象，例如 maze[1]，而你想要的是 maze.maze_list[1]。对象本身是不可下标化的，因为它没有 __getitem__ 方法，不像列表、字符串和元组等类型。 - Håken Lid

@puqeko 好的，我想我明白了，我更新了我的问题。我修复了代码，现在不会出现错误，但路径仍然不会显示在迷宫中。 - lux1020

它不会修复你的逻辑，但在调用 findpath 后打印迷宫是一个好的开始。此外，你缺少一些 ==。 - puqeko

Answer 1

看了你的代码后，我发现有几个错误。你没有正确处理入口和出口的行列对。对于这个迷宫来说，(10,20)是正确的，如果你假设每隔一行和每隔一列都是一个网格线。也就是说，如果|和-字符表示的是偶尔会有断裂的无限细线，就像传统的迷宫图画一样。

你需要乘以/除以2，并解决不可避免的篱笆柱错误，以便将文件参数正确地转换为数组行/列值。

接下来，你的findpath函数有些混乱：

首先，它应该是类的一个方法。它访问内部数据，包含关于类细节的“内部知识”。让它成为一个方法吧！

其次，你的退出条件用空格替换了当前字符，“删除错误的路径”。但如果你已经找到出口，那么路径就是正确的定义。不要这样做！

第三，你有一堆if语句用于不同的字符类型。虽然没问题，但请用单个if语句替换它们。

if self.maze_list[row][col] in '|-+*':
    return False

第四，你需要在检查完成之后将当前单元格标记为'*'，但当你到达出口位置时，应该在宣布胜利之前标记单元格。我认为将退出测试下移会更好。

这样应该能很好地清理问题。

第五，最后，你的递归测试是反过来的。当代码到达退出位置时，你的代码返回True。当代码遇到墙壁或尝试穿过自己的路径时，你的代码返回False。因此，如果代码走上了一条死路，它将到达终点，返回false，在回溯几次后一直返回false，直到回到起点。

因此，如果你看到任何一个True返回值，你就知道代码沿着那个方向找到了出口。你要立即返回true，什么也不要做。当然，不要擦除路径——它通向出口！

另一方面，如果你的所有可能的方向都没有返回true，那么你已经到了死路——出口不在这个方向上。你应该擦除你的路径，返回False，并希望能够在更高层次上找到出口。

- aghast