迷宫环境中的星形实施不起作用。 Nonetype 对象错误

Question

我正在尝试基于此实现 astar 搜索：https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2

然而，我得到一个

nonetype object is not iterable error

在nextmove()方法中调用我的astar方法时

不允许我导入任何其他方法。我在测试的时候也发现，astar方法中的if语句好像没有输入。我怀疑从未真正找到 goalnode 我只是不知道为什么。

import Search
import math
import random
counter = 0
moveset = []


class Node:
    def __init__(self,parent=None,position=None):
      self.parent = parent
      self.position = position
      self.g = 0
      self.f = 0
      self.h = 0



  #Manhattan heuristic function used to return the h value for the f = h + g heuristic. We use Manhattan as we can only traverse the maze by traveling up,down,left or 
    #right rather than being able to travel diagonally aswell.

    def heuristic(a):
      (x1,y1) = a
      (x2,y2) = gameEnvironment.getGoal()
      return(abs(x2 - x1) + abs(y2-y1))

    #The A star Search function, uses two lists to store open and closed nodes in the maze and considers the openNode with the lowest f value on each loop of the openlist.
    #All posible moves from any given node in the path are stored as children of that node and are then considered so that the next node in the path can be added

    def aStar(start,goal,gameEnvironment):
      #Creating the start and goal nodes and assign their heuristic values
      StartNode = Node(None,start)
      StartNode.g = StartNode.h = StartNode.f = 0
      GoalNode = Node(None,goal)
      GoalNode.g = GoalNode.h = GoalNode.f = 0

      #Initialisng the closed and open lists and placing the startNode on the open list

      closedSet = []
      openSet = []
      openSet.append(StartNode)

      #loop until the openset is empty(i.e the end)

      while openSet:
    #Identify the Current Node 
        CurrentNode = openSet[0]
        CurrentIndex = 0
        for index,item in enumerate(openSet):
          if item.f < CurrentNode.f:
            CurrentNode = item
            CurrentIndex = index


        openSet.pop(CurrentIndex)
        closedSet.append(CurrentNode)


        if CurrentNode.position == GoalNode.position:
          path = []
          current = CurrentNode
          while current is not None:
            path.append(current.position)
            current = current.parent
          reversedPath = path.reverse()
          return reversedPath


        childrenList = []
        for NewPos in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
      #Finding the Child Position
          ChildPos = (CurrentNode.position[0] + NewPos[0],CurrentNode.position[1] + NewPos[1])

          #Checking for walls
          if gameEnvironment.scanSpace(ChildPos[0],ChildPos[1]) == "Wall":
            continue

      #Checking for the edges of the maze
          if ChildPos[0] < 0 or ChildPos[1] < 0 or ChildPos[0] > gameEnvironment.getRowNumber() or ChildPos[1] < gameEnvironment.getColNumber():
            continue

          Child = Node(CurrentNode, ChildPos)
          childrenList.append(Child)
        #Loop through the Children   
        for x in childrenList:
      #Checks if child is closed
          for closed in closedSet:
             if x.position == closed.position:
               continue
      #creates heuristic values for the child   
          x.g = CurrentNode.g + 1
          x.h = self.heuristic(Child)
          x.f = x.g + x.h
          #checks if child is in the open set already
          for openNode in openSet:
            if x.position == openNode.position and x.g > openNode.g:
              continue
      #Add child
          openSet.append(x)


class Robot:
    def __init__(self, name="Robot"):
        self.name = name


    def nextMove(self, gameEnvironment, gameType):

        #return random.choice(["NORTH", "EAST", "SOUTH", "WEST", "STOP"])
        global counter
        global moveset
        if counter == 0:
          moveset.extend(Node.aStar(gameEnvironment.getStart(), gameEnvironment.getGoal(),gameEnvironment))
        move = moveset.pop(0)
        counter = counter + 1
        return move

Answer 1

我相信你这里有错字：

ChildPos[1] < gameEnvironment.getColNumber()

这个循环也可能会给您带来麻烦。 continue 语句适用于最内层的循环。因此，您正在遍历所有 closedSet 并在匹配时继续该循环（不是外部循环）。 openSet 循环也是如此。

  for x in childrenList:
  #Checks if child is closed
      for closed in closedSet:
         if x.position == closed.position:
           continue
      #creates heuristic values for the child   
      x.g = CurrentNode.g + 1
      x.h = self.heuristic(Child)
      x.f = x.g + x.h
      #checks if child is in the open set already
      for openNode in openSet:
        if x.position == openNode.position and x.g > openNode.g:
          continue
      #Add child
      openSet.append(x)

您可能想研究使用 Python 的 set() 内置函数。它将允许您不遍历检查是否相等的每个项目。（例如，将访问和访问位置存储为相应集合中的元组）。

>>> s = set()
>>> s.add((0,0))
>>> s.add((0,1))
>>> (0,0) in s
True
>>> (1,1) in s
False

迷宫环境中的星形实施不起作用。 Nonetype 对象错误

A Star Implementation in a maze environement not working. Nonetype Object error

python

maze

a-star