There are several kinds of heuristics out there that you can use to estimate distance, but we’ll start with the *Manhattan heuristic*. 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.

To get the heuristic estimate, we need to:

- Measure the distance between the two vertices’
`x`

positional values and between their`y`

positional values. - Return the sum of the
`x`

distance and`y`

distance together.

### Instructions

**1.**

Define a function `heuristic()`

with two parameters: `start`

and `target`

.

**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.

**3.**

Return the sum of `x_distance`

and `y_distance`

from the function.

**4.**

Time to add the heuristic into `a_star()`

so that distance is factored in!

Go to the line of `a_star()`

where `new_distance`

is defined. Set `new_distance`

equal to the sum of:

`current_distance`

`edge_weight`

- an invocation of
`heuristic()`

with`neighbor`

and`target`

as arguments (this estimates the distance between`neighbor`

and`target`

)

**5.**

Congrats! You’ve implemented A* using the Manhattan heuristic.

Try calling the function on the graph provided find the best path from Penn Station to Grand Central Station in Manhattan!