Python递归迷宫解算器从来不会一路返回

Question

我有一个带有一个图像（PNG，200x200）的递归迷宫解算器，我曾尝试使用try/except打印异常，但没有打印

递归函数

def solveRecursiveMaze(arr,x,y):
    successful = False
    if (x,y) == getExitPoint():
        successful = True
    elif isValid(arr,x,y):
        arr[x][y] = "V" #set to V to show it's a visited path
        successful = solveRecursiveMaze(arr, x-1, y)    
        if not successful:
            successful = solveRecursiveMaze(arr, x, y+1)
        if not successful:
            successful = solveRecursiveMaze(arr, x+1, y)
        if not successful:
            successful = solveRecursiveMaze(arr, x, y-1)
    if successful:
        arr[x][y] = "P" #Mark as P to show it's a valid pa
    return successful

isValid检查2D数组在传入的位置是否有一个“W”（表示白色像素），并且它是否在数组的边界内

def isValid(arr,x,y):
    if x < len(arr) and y < len(arr) and x >= 0 and y >= 0:
         if arr[x][y] == "W":
             return True
    return False

getExitPoint返回为迷宫出口找到的点的x，y（像素）

def getExitPoint():
     x = crop.size[0] - 1
     for y in range(0, crop.size[1]):
         if(crop.getpixel((x,y)) == (255,255,255)):
             return x,y
         if(crop.getpixel((y,x)) == (255,255,255)):
             return y,x

这就是我如何将图像转换为二维阵列的方法

maze = []
width,height = crop.size
for x in range(0, width):
    mazeX = []
    for y in range(0, height):
        if(crop.getpixel((x,y)) == (0,0,0)):
            mazeX.append("B")
        elif(crop.getpixel((x,y)) == (255,255,255)):
            mazeX.append("W")
    maze.append(mazeX)

• 它应该做的是将图像转换成2D数组，递归遍历（使用回溯）以寻找成功的路径，然后在路径上画一条红线

脚本在这幅图像上不起作用，每次它都在像素X=76，y=153处停止，我不确定该做什么/我做错了什么

边界为1px，路径为1px。没有任何错误、堆栈跟踪、异常或抛出的任何内容。递归停止，程序退出。有什么想法吗

Answer 1

您的代码存在一些不同的问题，但我认为现在发生的是，您的运行超出了递归限制。你的迷宫相当大和复杂。我需要使用4000（对我来说，1000是默认值，而3000不够大）

不确定您正在使用的图像库；我用了PIL.Image

您的输入图像实际上是203x203，要找到入口和出口是一个挑战。我假设入口在顶部或左侧，出口在右侧或沿底部

import sys
import argparse
import PIL.Image
import os

colors = {
    'white' : (255, 255, 255),
    'black' : (0, 0, 0),
    'red'   : (128, 0, 0),
    'green' : (0, 255, 0) }


def isValid(image, x, y):
    if x < image.size[0] and y < image.size[1] and x >= 0 and y >= 0:
        if image.getpixel((x, y)) == colors['white']:
            return True
    return False


def getEntryPoint(image):
    # Search along top.
    for x in range(1, image.size[0] - 1):
        if image.getpixel((x, 1)) == colors['white']:
            return x, 1

    # Search along left side.
    for y in range(1, image.size[1] - 1):
        if image.getpixel((1, y)) == colors['white']:
            return 1, y

    # Maze is invalid if there is no entry point.
    raise Exception('No entry point found!')


def getExitPoint(image):
    # Search along bottom.
    for x in range(1, image.size[0] - 1):
        if image.getpixel((x, image.size[1] - 2)) == colors['white']:
            return x, image.size[1] - 2

    # Search along right side.
    for y in range(1, image.size[1] - 1):
        if image.getpixel((image.size[0] - 2, y)) == colors['white']:
            return image.size[0] - 2, y

    # Maze is invalid if there is no exit point.
    raise Exception('No exit point found!')


def solveRecursiveMaze(image, x, y):
    successful = False
    if (x, y) == getExitPoint(image):
        successful = True
    elif isValid(image, x, y):
        # set to show it's a visited path
        image.putpixel((x, y), colors['red'])

        successful = solveRecursiveMaze(image, x-1, y)    
        if not successful:
            successful = solveRecursiveMaze(image, x, y+1)
        if not successful:
            successful = solveRecursiveMaze(image, x+1, y)
        if not successful:
            successful = solveRecursiveMaze(image, x, y-1)

    if successful:
        # Mark to show it's a valid path.
        image.putpixel((x, y), colors['green'])

    return successful


def main(options):
    solved = False

    if options.depth:
        sys.setrecursionlimit(options.depth)

    try:
        image = PIL.Image.open(options.filename)
    except:
        print('ERROR: Could not open %s' % (options.filename))
    else:
        image = image.convert('RGB')

        x, y = getEntryPoint(image)
        print('Entering maze at x = %d, y = %d' % (x, y))
        solved = solveRecursiveMaze(image, x, y)
        if not solved:
            print('No solution exists.')
        else:
            print('Solved maze.')
            basename = os.path.splitext(options.filename)[0]
            image.save(basename + '_solution' + '.png', 'PNG')

    return 0 if solved else 1


if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    parser.add_argument(
        ' d',
        '-depth',
        dest='depth',
        type=int,
        help='Set Python recursion limit with sys.setrecursionlimit()')
    parser.add_argument(
        'filename',
        help='Image containing the maze.')
    options = parser.parse_args()
    sys.exit(main(options))