implemented cornersAgent and its heuristic

Co-authored-by: Andreas1282 <Andreas1282@users.noreply.github.com>

1 files changed, 44 insertions, 15 deletions

diff --git a/searchAgents.py b/searchAgents.py
index 1d757b1..9a6f0ab 100644
--- a/searchAgents.py
+++ b/searchAgents.py
@@ -273,7 +273,7 @@ class CornersProblem(search.SearchProblem):
     You must select a suitable state space and successor function
     """
 
-    def __init__(self, startingGameState):
+    def __init__(self, startingGameState, visualize = True):
         """
         Stores the walls, pacman's starting position and corners.
         """
@@ -287,22 +287,34 @@ class CornersProblem(search.SearchProblem):
         self._expanded = 0 # DO NOT CHANGE; Number of search nodes expanded
         # Please add any code here which you would like to use
         # in initializing the problem
-        "*** YOUR CODE HERE ***"
+        goals = dict(zip(self.corners, [False]*len(self.corners)))
+        self.startState = (self.startingPosition, goals)
+        
+        # For display purposes
+        self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE        
 
     def getStartState(self):
         """
         Returns the start state (in your state space, not the full Pacman state
         space)
         """
-        "*** YOUR CODE HERE ***"
-        util.raiseNotDefined()
+        return self.startState
 
     def isGoalState(self, state):
         """
         Returns whether this search state is a goal state of the problem.
         """
-        "*** YOUR CODE HERE ***"
-        util.raiseNotDefined()
+        isGoal = all(state[1].values())
+
+        # For display purposes only
+        if isGoal:
+            self._visitedlist.append(state[0])
+            import __main__
+            if '_display' in dir(__main__):
+                if 'drawExpandedCells' in dir(__main__._display): #@UndefinedVariable
+                    __main__._display.drawExpandedCells(self._visitedlist) #@UndefinedVariable
+
+        return isGoal
 
     def getSuccessors(self, state):
         """
@@ -319,14 +331,25 @@ class CornersProblem(search.SearchProblem):
         for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
             # Add a successor state to the successor list if the action is legal
             # Here's a code snippet for figuring out whether a new position hits a wall:
-            #   x,y = currentPosition
-            #   dx, dy = Actions.directionToVector(action)
-            #   nextx, nexty = int(x + dx), int(y + dy)
-            #   hitsWall = self.walls[nextx][nexty]
+            (x,y), goals = state
+            dx, dy = Actions.directionToVector(action)
+            nextx, nexty = int(x + dx), int(y + dy)
+            if not self.walls[nextx][nexty]:
+                successor = (nextx, nexty)
+                newGoals = goals.copy()
+                for corner in self.corners:
+                    if successor == corner:
+                        newGoals[successor] = True
+
+                successors.append(((successor, newGoals), action, 1))
 
-            "*** YOUR CODE HERE ***"
+        # For display purposes only
+        if state[0] not in self._visited:
+            self._visited[state[0]] = True
+            self._visitedlist.append(state[0])
 
         self._expanded += 1 # DO NOT CHANGE
+
         return successors
 
     def getCostOfActions(self, actions):
@@ -356,11 +379,17 @@ def cornersHeuristic(state, problem):
     shortest path from the state to a goal of the problem; i.e.  it should be
     admissible (as well as consistent).
     """
+    
     corners = problem.corners # These are the corner coordinates
-    walls = problem.walls # These are the walls of the maze, as a Grid (game.py)
-
-    "*** YOUR CODE HERE ***"
-    return 0 # Default to trivial solution
+    # walls = problem.walls # These are the walls of the maze, as a Grid (game.py)
+    position, visited = state
+    getDistance = lambda corner: abs(position[0] - corner[0]) + abs(position[1] - corner[1])
+    unvisited = filter(lambda corner: not visited[corner], corners)
+    
+    if len(unvisited) == 0:
+        return 0
+        
+    return getDistance(max(unvisited, key=getDistance))
 
 class AStarCornersAgent(SearchAgent):
     "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic"