时间戳

首页 > 解决方案 > 迷宫环境中的 Star 实施不起作用。无类型对象错误

python - 迷宫环境中的 Star 实施不起作用。无类型对象错误

问题描述

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

但是，我得到一个

nonetype 对象不是可迭代的错误

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

我不允许导入任何其他方法。我在测试的时候还发现ifastar方法中的语句好像没有输入。我怀疑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

标签： pythona-starmaze

解决方案

我相信你这里有一个错字：

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

推荐阅读