Python迷宫寻路程序（A*算法）报AttributeError: 'NoneType'无'path'属性

问题描述 #

在Jupyter Notebook中使用Python结合simpleai库的A*算法实现迷宫最短路径查找，运行时触发AttributeError: 'NoneType' object has no attribute 'path'，怀疑与重写的result方法有关，但无法定位具体问题。

错误信息 #

AttributeError                            Traceback (most recent call last)
Input In [26], in <cell line: 57>()
     88 problem = MazeSolver(MAP)
     90 result = astar(problem, graph_search=True)
---> 92 path = [x[1] for x in result.path()]
     94 print()
     95 for y in range(len(MAP)):

AttributeError: 'NoneType' object has no attribute 'path'

相关代码 #

import math
from simpleai.search import SearchProblem, astar

class MazeSolver(SearchProblem):
    
    def __init__(self, board):
        self.board = board
        self.goal = (0,0)
        
        for y in range(len(self.board)):
            for x in range(len(self.board[y])):
                if self.board[y][x].lower() == "o":
                    self.initial = (x, y)
                elif self.board[y][x].lower() == "x":
                    self.goal = (x, y)
        super(MazeSolver, self).__init__(initial_state = self.initial)
                
    
    def actions(self, state):
        actions = []
        for action in COSTS.keys():
            newx, newy = self.result(state, actions)
            if self.board[newy][newx] != "#":
                actions.append(action)
        return actions
    
    

    def result(self, state, action):
        x, y = state
        
        if action.count("up"):
            y -= 1
        if action.count("down"):
            y += 1
        if action.count("left"):
            x -= 1
        if action.count("right"):
            x += 1
            
        new_state = (x, y)
        
        return new_state
    
    def is_goal(self, state):
        return state == self.goal
        
    def cost(self, state, action, state2):
        return COSTS[action]
    
    def heuristic(self, state):
        x, y = state
        gx, gy = self.goal
        
        return math.sqrt((x - gx) ** 2 + (y - gy) ** 2)

if __name__ == "__main__":
    MAP = """
    #############################
    #        #              #   #
    # ####   ########       #   #
    #  o #   #              #   #
    #    ###    #####  ######   #
    #      #   ###  #           #
    #      #     #  #  #  #   ###
    #     #####    #   #  # x   #
    #              #      #     #
    #############################
    """
    
    print(MAP)
    MAP = [list(x) for x in MAP.split("\n") if x]
    
    cost_regular = 1.0
    cost_diagonal = 1.7
    
    COSTS = {
        "up": cost_regular,
        "down": cost_regular,
        "left": cost_regular,
        "right": cost_regular,
        "up left": cost_diagonal,
        "up right": cost_diagonal,
        "down left": cost_diagonal,
        "down right": cost_diagonal
    }

    problem = MazeSolver(MAP)
    
    result = astar(problem, graph_search=True)
    
    path = [x[1] for x in result.path()]
    
    print()
    for y in range(len(MAP)):
        for x in range(len(MAP[y])):
            if (x, y) == problem.initial:
                print('o', end='')
            elif(x, y) == problem.goal:
                print('x', end='')
            elif (x, y) in path:
                print('.', end='')
            else:
                print(MAP[y][x], end='')
        print()

错误原因分析 #

1. actions方法参数传递错误：遍历动作时，错误地将actions列表传给result方法，而result需要单个动作字符串作为参数，导致新坐标计算完全错误，无法识别合法动作，最终A*算法找不到路径返回None。
2. 缺少坐标边界检查：计算新坐标后未判断是否超出地图范围，会触发索引越界错误，同样导致路径查找失败。
3. result方法动作判断冗余：使用action.count()判断动作类型，逻辑虽可行但不够精准，且代码冗余。

修复方案 #

修正后的完整代码 #

import math
from simpleai.search import SearchProblem, astar

class MazeSolver(SearchProblem):
    
    def __init__(self, board):
        self.board = board
        self.goal = (0,0)
        self.max_y = len(board)
        self.max_x = len(board[0]) if self.max_y > 0 else 0
        
        for y in range(self.max_y):
            for x in range(self.max_x):
                if self.board[y][x].lower() == "o":
                    self.initial = (x, y)
                elif self.board[y][x].lower() == "x":
                    self.goal = (x, y)
        super(MazeSolver, self).__init__(initial_state = self.initial)
                
    
    def actions(self, state):
        actions = []
        for action in COSTS.keys():
            # 传入单个动作计算新状态
            new_x, new_y = self.result(state, action)
            # 检查坐标合法性：在地图范围内且不是墙
            if 0 <= new_x < self.max_x and 0 <= new_y < self.max_y:
                if self.board[new_y][new_x] != "#":
                    actions.append(action)
        return actions
    
    def result(self, state, action):
        x, y = state
        
        # 直接匹配动作类型，简化逻辑
        if action == "up":
            y -= 1
        elif action == "down":
            y += 1
        elif action == "left":
            x -= 1
        elif action == "right":
            x += 1
        elif action == "up left":
            x -= 1
            y -= 1
        elif action == "up right":
            x += 1
            y -= 1
        elif action == "down left":
            x -= 1
            y += 1
        elif action == "down right":
            x += 1
            y += 1
            
        return (x, y)
    
    def is_goal(self, state):
        return state == self.goal
        
    def cost(self, state, action, state2):
        return COSTS[action]
    
    def heuristic(self, state):
        x, y = state
        gx, gy = self.goal
        
        # 可选：改用切比雪夫距离更适配对角线移动的场景，避免浮点运算
        # return max(abs(x - gx), abs(y - gy)) * cost_regular
        return math.sqrt((x - gx) ** 2 + (y - gy) ** 2)

if __name__ == "__main__":
    MAP = """
    #############################
    #        #              #   #
    # ####   ########       #   #
    #  o #   #              #   #
    #    ###    #####  ######   #
    #      #   ###  #           #
    #      #     #  #  #  #   ###
    #     #####    #   #  # x   #
    #              #      #     #
    #############################
    """
    
    print(MAP)
    MAP = [list(x) for x in MAP.split("\n") if x]
    
    cost_regular = 1.0
    cost_diagonal = 1.7
    
    COSTS = {
        "up": cost_regular,
        "down": cost_regular,
        "left": cost_regular,
        "right": cost_regular,
        "up left": cost_diagonal,
        "up right": cost_diagonal,
        "down left": cost_diagonal,
        "down right": cost_diagonal
    }

    problem = MazeSolver(MAP)
    
    result = astar(problem, graph_search=True)
    
    # 增加非空判断，避免触发AttributeError
    if result is not None:
        path = [x[1] for x in result.path()]
        
        print()
        for y in range(len(MAP)):
            for x in range(len(MAP[y])):
                if (x, y) == problem.initial:
                    print('o', end='')
                elif(x, y) == problem.goal:
                    print('x', end='')
                elif (x, y) in path:
                    print('.', end='')
                else:
                    print(MAP[y][x], end='')
            print()
    else:
        print("未找到可行路径")

关键修复点说明 #

1. 修正actions方法参数传递：遍历动作时传入单个动作字符串，确保新坐标计算正确。
2. 添加坐标边界检查：在actions中判断新坐标是否在地图索引范围内，避免越界错误。
3. 简化result方法逻辑：直接匹配动作类型，代码更清晰高效。
4. 增加result非空判断：主程序中先检查result是否为None，再调用path()方法。
5. 优化初始化逻辑：记录地图最大坐标值，方便后续边界检查。

内容的提问来源于stack exchange，提问作者Aicr