diff options
| -rw-r--r-- | searchAgents.py | 139 |
1 files changed, 85 insertions, 54 deletions
diff --git a/searchAgents.py b/searchAgents.py index e990dce..a203795 100644 --- a/searchAgents.py +++ b/searchAgents.py @@ -4,8 +4,9 @@ # Project 1 # Due: Sept. 14th, 2021 # -# TODO NAME -# Partner: TODO NAME +# TODO Add name +# Name: +# Partner: # @@ -504,15 +505,12 @@ def foodHeuristic(state, problem): Subsequent calls to this heuristic can access problem.heuristicInfo['wallCount'] """ - - # manhattanDist = lambda pos1, pos2: abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) - + + # returns an estimation of the traversal cost between two points def getDistance(pos1, pos2): - # Manhattan Distance - distance = abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) - # Returns the penalty for a full bisection of walls along the a given axis, or if none are found, 0 - # -952 nodes expanded (6700/7652) + # Returns the penalty for a full bisection of walls along the a given + # axis, or if none are found, returns 0. -952 nodes expanded (6700/7652) def wallPenalty(arrayLambda, axis): # Get the other axis index other = int(not axis) @@ -524,59 +522,82 @@ def foodHeuristic(state, problem): upperBound = max((pos2[other], pos1[other])) # Only run if the secondary axis's width is > 1 - if lowerBound != upperBound: - - # Loop though each line in primary axis between the two positions - for item in range(axisLowerBound, axisUpperBound): - - # The lambda is used to generically return an array of isWall's for each line - wallArray = arrayLambda(item) - - # Slice the array of walls using the bounds - wallsBetween = wallArray[lowerBound:upperBound] - - # Check if all the spaces between the bounds are walls - if all(wallsBetween): - - # Initialize the penalty to 2 (minimum to get around the line of walls) - penalty = 2 - lowerWall = lowerBound + 1 - upperWall = upperBound + 1 - - # For each distance the wall exends out on both sides, increase the penalty by 1 - while lowerWall >= 0 and upperWall < len(wallArray) and wallArray[lowerWall] and wallArray[upperWall]: - penalty += 1 - lowerWall += 1 - upperWall += 1 - return penalty + if lowerBound == upperBound: + return 0 + + # Loop though each line in primary axis between two positions + for item in range(axisLowerBound, axisUpperBound): + + # The lambda is used to generically return an array of + # isWall's for each line + wallArray = arrayLambda(item) + + # Slice the array of walls using the bounds + wallsBetween = wallArray[lowerBound:upperBound] + + # Check if all the spaces between the bounds are walls + if not all(wallsBetween): + continue + + # Initialize the penalty to 2 (minimum to get around + # the line of walls) + penalty = 2 + lowerWall = lowerBound + 1 + upperWall = upperBound + 1 + + # For each distance the wall exends out on both sides and + # increase the penalty by 1 + while ( + lowerWall >= 0 + and upperWall < len(wallArray) + and wallArray[lowerWall] + and wallArray[upperWall] + ): + penalty += 1 + lowerWall += 1 + upperWall += 1 + return penalty + return 0 - # Check for a full bisection of walls along the x axis, + # Manhattan Distance + distance = abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) + + # Check for a full bisection of walls along the x axis, # if found, return the penalty + Manhattan Distance penalty = wallPenalty(lambda x: wallGrid[x], 0) if penalty > 0: return distance + penalty - # Check for a full bisection of walls along the y axis, + # Check for a full bisection of walls along the y axis, # if found, return the penalty + Manhattan Distance penalty = wallPenalty(lambda y: [axis[y] for axis in wallGrid], 1) if penalty > 0: return distance + penalty - # If no wall bisections were found, but the "box" is width/length of 1, return the path + # If no wall bisections were found and the "box" is 1xK or Kx1, + # return the path if pos2[0] == pos1[0] or pos2[1] == pos1[1]: return distance - # Lastly, check if either node is immediately "boxed off" and, if so, add a penalty + # Lastly, check if either node is immediately "boxed off" and, if so, + # add a penalty + # normalizes the x and y offsets to either 1 or -1 xOffset = (pos1[0] - pos2[0]) / abs(pos1[0] - pos2[0]) yOffset = (pos1[1] - pos2[1]) / abs(pos1[1] - pos2[1]) # adds weight for walls around the positions being looked at - if wallGrid[pos2[0] + xOffset][pos2[1]] and wallGrid[pos2[0]][pos2[1] + yOffset]: + if ( + wallGrid[pos2[0] + xOffset][pos2[1]] + and wallGrid[pos2[0]][pos2[1] + yOffset] + ): distance += 2 - if wallGrid[pos1[0] + (xOffset * -1) ][pos1[1]] and wallGrid[pos1[0]][pos1[1] + (yOffset * -1)]: + if ( + wallGrid[pos1[0] + (xOffset * -1)][pos1[1]] + and wallGrid[pos1[0]][pos1[1] + (yOffset * -1)] + ): distance += 2 return distance @@ -591,30 +612,40 @@ def foodHeuristic(state, problem): if foodLeft == 0: return 0 - # get the distances between the current position and remaining food + # get the position and distance of the closest food to pacman minFood = min(foodList, key=lambda food: getDistance(food, position)) minFoodDist = getDistance(minFood, position) - - # get distance to minFood and then distance between foods that are farthest from eachother - # -925 nodes expanded (7652/8577) - if problem.heuristicInfo.has_key('foodList') and problem.heuristicInfo['foodList'] == foodList: - mostDispersed = problem.heuristicInfo['mostDispersed'] + # get distance to minFood and then distance between foods that are farthest + # from each other. -925 nodes expanded (7652/8577) + + # Check if the foodList has changed + if ( + problem.heuristicInfo.has_key("foodList") + and problem.heuristicInfo["foodList"] == foodList + ): + # If foodList has not changed, there is no need to calculate a new + # mosDispersed, just return the last one calculated + mostDispersed = problem.heuristicInfo["mostDispersed"] else: + # If foodList has changed, initialize mostDispersed and recalculate it. mostDispersed = (minFood, minFood, 0) + # Loop though each food, find the furthest food from it foodList. O(n^2)? for food in foodList: - temp = max(map(lambda other: (food, other, getDistance(other, food)), foodList), key=lambda node: node[2]) + temp = max( + map(lambda other: (food, other, getDistance(other, food)), foodList), + key=lambda node: node[2], + ) + + # Store the max distances pair of foods in a tuple. if temp[2] > mostDispersed[2]: mostDispersed = temp - - problem.heuristicInfo['foodList'] = foodList - problem.heuristicInfo['mostDispersed'] = mostDispersed - - # if minFoodPos != mostDispersed[0] and minFoodPos != mostDispersed[1]: - # distance from the closest food to the closest of the two points from the mostDispersed - # minToMostDispersed = mostDispersed[2] + min(getDistance(mostDispersed[0], minFoodPos), getDistance(mostDispersed[1], minFoodPos)) + # Store the state of the foodList and calculated mostDispersed, for + # possible reuse if the foodList doesn't change. + problem.heuristicInfo["foodList"] = foodList + problem.heuristicInfo["mostDispersed"] = mostDispersed # sets the bounds of our heuristic to keep it consistent bounds = (mostDispersed[2], foodLeft - 1) |