diff options
Diffstat (limited to 'searchAgents.py')
-rw-r--r-- | searchAgents.py | 81 |
1 files changed, 50 insertions, 31 deletions
diff --git a/searchAgents.py b/searchAgents.py index 126f171..e990dce 100644 --- a/searchAgents.py +++ b/searchAgents.py @@ -511,44 +511,63 @@ def foodHeuristic(state, problem): # Manhattan Distance distance = abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) - # adds weight for walls around the positions being looked at - # -54 nodes expanded (8577/8631) - - def wallPenalty(wallArray, lowerBound, upperBound): - wallsBetween = wallArray[lowerBound:upperBound] - if all(wallsBetween): - penalty = 2 - lowerWall = lowerBound + 1 - upperWall = upperBound + 1 - while lowerWall >= 0 and upperWall < len(wallArray) and wallArray[lowerWall] and wallArray[upperWall]: - penalty += 1 - lowerWall += 1 - upperWall += 1 - return penalty + # 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) + def wallPenalty(arrayLambda, axis): + # Get the other axis index + other = int(not axis) + + # Set the bounds for the "box" between the two positions + axisLowerBound = min((pos2[axis], pos1[axis])) + axisUpperBound = max((pos2[axis], pos1[axis])) + lowerBound = min((pos2[other], pos1[other])) + 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 return 0 - xLowerBound = min((pos2[0], pos1[0])) - xUpperBound = max((pos2[0], pos1[0])) - - yLowerBound = min((pos2[1], pos1[1])) - yUpperBound = max((pos2[1], pos1[1])) - - if yLowerBound != yUpperBound: - for x in range(xLowerBound, xUpperBound): - penalty = wallPenalty(wallGrid[x], yLowerBound, yUpperBound) - if penalty > 0: - return distance + penalty - - if xLowerBound != xUpperBound: - for y in range(yLowerBound, yUpperBound): - penalty = wallPenalty([axis[y] for axis in wallGrid], xLowerBound, xUpperBound) - if penalty > 0: - return distance + penalty + # 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, + # 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 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 # 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]) |