solving a Maze Using Python

Question

My goal is to make a function which will allow a robot to solve a maze. for the class excercise purpose its a depth first search here is the template....

Todo = (root,[])
visited = []
while Todo not empty:
   node,path = Todo[0]
   Todo = Todo[1:]
   if node in visited:
       pass
   else:
       children = node.children
       children.remove(visited)
       if node is good:
           done(return path)
       Todo = [(child, path[child])]
           for child in children

the robot can only go forward or turn right im wondering what to name each template in the code...for example what would "children" be or "node"?

i'm using Calico (which lets me program in python) and the library Myro to do this.

This is a rather late post but to those interested this ended up being the final DFS . And also the code to plan the moves

class Node:
    def __init__(self, x, y, direction):
        self.x = x
        self.y = y
        self.direction = direction

    __left = { 'N' : 'W',
               'E' : 'N',
               'S' : 'E',
               'W' : 'S' }

    __right = { 'N' : 'E',
                'E' : 'S',
                'S' : 'W',
                'W' : 'N' }

    __dx = { 'N' : 0,
             'E' : 1,
             'S' : 0,
             'W' : -1 }

    __dy = { 'N' : 1,
             'E' : 0,
             'S' : -1,
             'W' : 0 }

def __str__(self):
    return "<%d,%d,%s>" % (self.x, self.y, self.direction)


def _left(self):
    return Node(self.x, self.y,
                self.__left[self.direction])

def _right(self):
    return Node(self.x, self.y,
                self.__right[self.direction])

def _forward(self):
    return  Node(self.x + self.__dx[self.direction], 
                 self.y + self.__dy[self.direction], 
                 self.direction)

def children(self):      
    return [ ('left',    self._left()), 
             ('right',   self._right()),
             ('forward', self._forward()),
           ]

def dfs(node, soughtValue, visitedNodes):
     if node.x == soughtValue.x and node.y == soughtValue.y and node.direction ==      soughtValue.direction:
      return []

 newVisited = visitedNodes[:]
 newVisited.append(node)
 for action, adjNode in node.children():
      if adjNode not in newVisited:
          plan = dfs(adjNode, soughtValue, newVisited)
          if plan is not None:
              p = [action]
              p.extend(plan)
              return p
 return None

Thanks for all the answers though!!

Answer 1

Assuming a structure such as

class Node(object):
    def __init__(self):
        self.children = set()

Your depth-first would look like:

Todo = [(root, [])]
visited = set()
while Todo:
    node, path = Todo.pop()
    path.append(node)
    if node is good:
        return path
    visited.add(node)
    children = node.children.copy()
    Todo.extend([(child, path[:]) for child in children if child not in visited])

Todo contains a list of tuples. Each tuple being a node and a path to get there.

A test would be

good = Node()
a = Node()
b = Node()
b.children.add(good)
c = Node()
root = Node()
root.children.add(a)
root.children.add(b)
root.children.add(c)

Answer 2

"Children" and "node" refer to items in what is a tree data structure. Node is just that -- a node or item in the tree. Children refers to the items immediately under the node that you're looking at in the tree.

Your "Todo" tuple looks like the first item is the node in question, and the second item is an array of children. This can be a nested data structure to express a tree. Each of the items under the children array could themselves be node tuples.

I'm not sure what you're referring to here with "template". Right now you have an empty tree, and your traversal should do nothing because there's nothing to be done. Ideally the contents of your tree might be different paths available through the maze.