Able To Find Path Using Dfs But Not Able Specify The Right Directions To Pacman _ Python

I am working on an assignment found on an AI course page at berkley website for fun. I need to write a depth-first search for the pacman game so that it can find its path.The probl

Solution 1:

Some hints:

• Each node you check should encapsulate the data of how you got there.
• DFS is like a stack; you start by pushing the start state. You pop the stack, and push back the nodes that can follow from the node you popped.
• Since you are ultimately trying to find a path, the node data must hold your location and the path you took to get there.

Solution 2:

How you store your path is a VERY important topic, when you consider that some of your searches might result in paths 200+ steps long. Iterating over a list that many times.... O(2^N) or O(3^N)? lists for any kind of search as a path storing mechanism are the wrong answer, especially when you get into BFS and any time you have multiple objectives (meaning, multiple paths through the same node can exist). List complexity and the data storage is ridiculous.

I recommend linklisting as a path storage mechanism. When you push your nodes into the fringe, simply key them into a dictionary with a unique key and push the key. Then when you pull a node from the fringe, you can get the entire state, as is, from the dictionary.

If part of your state is the node that that state was in one step previously, then you have a path to the start; the end node links to the one behind it, which links to the one behind it, etc. Using a unique key system like this allows multiple paths through the same point, at EXTREMELY low data cost; you still must be rational about which paths you pull off the fringe. However, any time you pull anything off the fringe, you pull it's entire path, with only 1 number.

Solution 3:

I did get it work by making sure each move is only 1 distance. One of the issue with your code was at the end it try to jump 5 or 6 places. Make sure every move it make is one and reverse till move distance become 1 to your next destination. Hint manhattanDistance().

Solution 4:

start= [problem.getStartState()]
  for item instart:
      Open=[item]
  Closed=[]
  Path=[]

  if problem.isGoalState(Open[0]) isTrue:
      returnelse:
       count=0
       while Open:
                if count==0:
                  visit=Open.pop()
                else:
                  temp=Open.pop()
                  visit=temp[0]

                Closed.append(visit)                            
                if problem.isGoalState(visit) isTrue:
                    return Path
                else:
                    Successors= problem.getSuccessors(visit)
                    for index in Successors:
                            if index[0] notin Closed :
                              Open.append((index[0],index[1]))
                print Open
                count=count+1

i changed the code as u said. right now i am not having anything in path.

this open after finding the solution -( 1,1 is the solution)

[((5, 4), 'South'), ((4, 5), 'West')][((5, 4), 'South'), ((3, 5), 'West')][((5, 4), 'South'), ((2, 5), 'West')][((5, 4), 'South'), ((1, 5), 'West')][((5, 4), 'South'), ((1, 4), 'South')][((5, 4), 'South'), ((1, 3), 'South')][((5, 4), 'South'), ((2, 3), 'East')][((5, 4), 'South'), ((2, 2), 'South')][((5, 4), 'South'), ((2, 1), 'South'), ((3, 2), 'East')][((5, 4), 'South'), ((2, 1), 'South'), ((4, 2), 'East')][((5, 4), 'South'), ((2, 1), 'South'), ((4, 3), 'North')][((5, 4), 'South'), ((2, 1), 'South'), ((5, 3), 'East')][((5, 4), 'South'), ((2, 1), 'South'), ((5, 4), 'North')][((5, 4), 'South'), ((2, 1), 'South')][((5, 4), 'South'), ((1, 1), 'West')]

now if you will notice when it gets three list members it takes a path which was a dead end now the Open is able to backtrace and find the correct path but i need a way to somewhow specify the return direction in the Path variable like

for eg Path = ['south',west' west'.................] etc