FAQ: A* Algorithm: Python - A Starry-Eyed Heuristic that Never Sleeps

This community-built FAQ covers the “A Starry-Eyed Heuristic that Never Sleeps” exercise from the lesson “A* Algorithm: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Computer Science

FAQs on the exercise A Starry-Eyed Heuristic that Never Sleeps

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Here’s some help with:

2.

In the function body, create a variable x_distance and set it equal to the absolute value of the target’s x value subtracted from start 's x value.

Create a variable y_distance in the same way.

def heuristic(start, target):
  x_distance = abs(start.position[0] - target.position[0])
  y_distance = abs(start.position[1] - target.position[1])
  return x_distance + y_distance
5 Likes

Manhattan heuristic . This heuristic is only considered admissible — meaning that it never overestimates the distance in reaching the target

This appears to be sides ab + bc of a right triangle with hypotenuse ac. does that not always overestimate the length of ac?

1 Like

It has been quite some time since you posted, so it’s possible the module was updated, but the full quote is below:

This heuristic is only considered admissible — meaning that it never overestimates the distance in reaching the target — in a grid system in which the search can only move up, down, left, or right.

As stated, the Manhattan heuristic is only admissible in a grid system. The length of ac isn’t a viable move in a grid system.

    for neighbor, edge_weight in graph[current_vertex]:
      new_distance = current_distance + edge_weight + heuristic(neighbor, target)
      new_path = paths_and_distances[current_vertex][1] + [neighbor.name]
      

Hi guys,
In the code above, It seems to me that the new distance is accumulating all the heuristics function values from the previous vertices to the new neighbour’s distance.
Don’t we need to track the sum of ‘actual’ weights until the node separately like dijkstras algorithm and only add heuristics function value at each vertex as explained in the introductory video?

Or it doesn’t really matter when it comes to the result?

I got stuck here for a while. My problem was that I had
target.position - start.position
instead of
start.position - target.position
but it shouldn’t matter if we take the absolute value, so I got stuck here for a long while.