Hi,

I have a programing problem of finding monotonic heuristics (in python).

I have this function which takes two points a and b in the n-dimensional space and returns the d-dimensional point r such that r_i = | a_i - b_i | for i = 1...d

def distance_in_each_coordinate(x, y):

res = [ abs(a-b) for (a,b) in zip(x, y) ]

return res

Then I have the following functions, which receive coordinates of two grid points and return the estimated distance between them.

def grid_3D_heuristic(current, destination): # in the classis 3D grid

dst_per_coor = distance_in_each_coordinate(current, destination)

return sum(dst_per_coor)

def grid_all_diagonal_3D_heuristic(current, destination): # in the 3D grid containing both face and space diagonals

dst_per_coor = distance_in_each_coordinate(current, destination)

return max(dst_per_coor)

And similarly I would like to know how to calculate the distance in a 3D grid, which contains only face diagonals (no space diagonals):

def grid_face_diagonal_3D_heuristic(current, destination):

return 'WHAT DO I RETURN HERE?'

I have tried using manhattan distance and calculating the heuristic as follows:

def manhattan_dist(x, y):

return sum(abs(a-b) for (a,b) in zip(x, y))

def grid_face_diagonal_3D_heuristic(current, destination):

return manhattan_dist(current, destination)

But this doesn't give a monotonic heuristic. Could you please help me find the heuristic in a 3D grid with face diagonals only?

Thank you! <3