迷宫环境中的星形实现不起作用.无类型对象错误

Question

我试图基于这个实现一个 astar 搜索：https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2

但是，我得到一个

nonetype 对象不是可迭代错误

在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