Question

Cannot figure our what's wrong with this code but it won't stop running when I run it. This is python code for a pac-man game to find the corners of the maze

def cornersHeuristic(state, problem):
"""
A heuristic for the CornersProblem that you defined.

state: The current search state
(a data structure you chose in your search problem)

problem: The CornersProblem instance for this layout.

This function should always return a number that is a lower bound on the
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 ***"
currPos = state[0]
if problem.isGoalState(state):
return 0
# find the shortest path
uncheckedCor = list(state[1][:])
path = 0;
# print(uncheckedCor[0])
while len(uncheckedCor) > 0:
closetPos = closetCorner(currPos,uncheckedCor)
path += util.manhattanDistance(currPos,closetPos)
currPos = closetPos
uncheckedCor.remove(closetPos)
uncheckedCor = tuple(uncheckedCor)
return path
def closetCorner(start, cor):
if len(cor) == 0:
return None
closetCorner = cor[0]
shortestPath = util.manhattanDistance(start,cor[0])
for pos in cor[1:4]:
cost = util.manhattanDistance(start,pos)
if cost < shortestPath:
shortestPath = cost
closetCorner = pos
return closetCorner

Answer 1

The following snippet is the python code for a pacman corner finding problem. It is a standard Artificial Intelligence and python problem discussed across a lot of universities around the world.

Here corners can be found using either breadthFirstSearch or Heuristics.

Heuristics refers to functions for search states that return numbers that estimate the cost to the nearest goal. Highly effective heuristics will return values closer to the actual goal costs.

Here the result can be achieved by visiting a lot of nodes but with higher node traversal comes greater complexity.

So here, in the above code node traversal is high so the compilation time is really high. Moreover, the Heuristics have to consistent as evident below.

An alternative code for the same is as follows :

def cornersHeuristic(state, problem):
"""
A heuristic for the CornersProblem that you defined.
state: The current search state
(a data structure you chose in your search problem)
problem: The CornersProblem instance for this layout.
This function should always return a number that is a lower bound
on the 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)
unvisited = [] # Hold unvisited corners
visited = state[1] # Visited corners
node = state[0] # Current node
heuristic = 0 # Heuristic value

# Find all the corners that we haven't visited yet, and append them together

for corner in corners:
if not corner in visited:
unvisited.append(corner)
  
# Find the sum of the shortest distances between the unvisited corners. Use
# this as the heuristic because it is consistent (will always choose the same corners for a given situation). #It helps to find the number of moves when all the wall has been removed. The
# heuristic will return 0 at a goal state since the minimum distance to a
# corner when in a corner is 0, and will never return a negative since manhattan distance can never be negative.
while unvisited:
distance, corner = min([(util.manhattanDistance(node, corner), corner) \
for corner in unvisited])
heuristic += distance
node = corner
unvisited.remove(corner)
  
return heuristic