Звездная реализация в лабиринте не работает. Ошибка нетипичного объекта - PullRequest
Новая
       26

Звездная реализация в лабиринте не работает. Ошибка нетипичного объекта

0 голосов
/ 04 января 2019

Я пытаюсь реализовать поиск Астар на основе этого: https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2

Однако я получаю

нетипизированный объект не повторяется ошибка

При вызове моего метода astar в методе nextmove().

Мне не разрешено импортировать любые другие методы. При тестировании я также обнаружил, что операторы if в методе astar, похоже, не вводятся. Я подозреваю, что 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

1 Ответ

0 голосов
/ 04 января 2019

Я полагаю, у вас есть опечатка здесь: 

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
...