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

Question

Im trying to implement an astar search based on this one: https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2

However, I get a

nonetype object is not iterable error

When calling my astar method in the nextmove() method.

I'm not allowed to import any other methods. I also found when testing that the if statements in the astar method don't seem to be entered. I suspect that the goalnode is never actually found I just don't know why.

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

I believe you have a typo here:

ChildPos[1] < gameEnvironment.getColNumber()

This loop might also give you trouble. The continue statements apply to the inner most loop. So you are iterating over all of closedSet and continuing that loop if it matches (not the outer one). Same for the openSet loop.

  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)

You might want to look into using Python's set() builtin. It will allow you to not loop over every item checking for equality. (e.g. store the visited and to-visit positions as tuples in the respective sets).

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