From 8967edfb6c659864ffffacc519034927aeea2727 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Fri, 3 Sep 2021 21:35:38 -0500 Subject: implemented cornersAgent and its heuristic Co-authored-by: Andreas1282 --- searchAgents.py | 59 ++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 44 insertions(+), 15 deletions(-) (limited to 'searchAgents.py') 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" -- cgit v1.2.3-70-g09d2