Maze pathfinding implementation (BFS) not giving correct path

I am trying to get the shortest path for a maze with a ball (the ball is rolling until it hits a wall).

maze = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0],
        [0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0],
        [0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1],
        [1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
        [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0],
        [0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0],
        [0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

start = (0, 0)
end = (22, 22)

def shortestDistance(maze: List[List[int]], start: List[int], destination: List[int]):
    start, destination = tuple(start), tuple(destination)
    row, col = len(maze), len(maze[0])
    moves = [(-1, 0), (0, 1), (0, -1), (1, 0)]
    dstr = ['u', 'r', 'l', 'd']

    class Point:
        def __init__(self, distance, coordinates, directions):
            self.distance = distance
            self.coordinates = coordinates
            self.directions = directions

        def __eq__(self, p):
            if self.distance == p.distance:
                return self.__lt__(self, p)

            return self.distance - p.distance

        def __lt__(self, p):
            return len(self.directions) - len(p.directions)


    heap = [(Point(0, start, ""))]
    visited = set()
    while heap:
        point = heapq.heappop(heap)
        dist = point.distance
        node = point.coordinates
        directions = point.directions

        if node in visited: continue
        if node == destination:
            return directions

        visited.add(node)

        for idx, move in enumerate(moves):
            dx, dy = move
            newX = node[0]
            newY = node[1]
            distance = dist
            newDirections = directions
            while 0 <= newX + dx < row and 0 <= newY + dy < col and maze[newX + dx][newY + dy] == 0:
                newX += dx
                newY += dy
                distance += 1
                if (newX, newY) == destination:
                    break

            if (newX, newY) not in visited:
                heapq.heappush(heap, Point(distance, (newX, newY), newDirections + dstr[idx]))

    return "Impossible"


path = shortestDistance(maze, start, end)
print(path)

The idea is to compare the distance and if it is equal, pick the path with less changes of direction.

I am currently getting rdrludlrdrudludldldr as an output, but it doesn’t make sense. “Right” should not be followed by “Left” or “Up” by “Down” and vice versa. This just gets the ball to the same location.

Answer

The problem is that the __lt__ function is not doing what it should.

It should return a boolean which is true when self is to be considered less than p. As you currently return an integer result, which often is non-zero you get into the situation where a pair (p, q) of points would have both p < q and q < p as true… which leads to erratic behaviour.

Here is how you could define it:

def __lt__(self, p):
    return ((self.distance, len(self.directions), self.directions) < 
          < (p.distance, len(p.directions), p.directions)) 

With this change the returned path is

rdrdldldrdr

Simplification

Instead of creating the class Point, you could use named tuples, which makes everything easier (and faster). You would just need to change the order of the “properties” so that these points compare in the desired way, i.e. directions should come before coordinates and the length of the directions string should get its own property:

from collections import namedtuple

# change order of properties so comparison works as intended
Point = namedtuple("Point", "distance, length, directions, coordinates")

And then make the appropriate change where you call Point:

heap = [Point(0, 0, "", start)]
# ...
heapq.heappush(heap, Point(distance, len(newDirections) + 1, newDirections + dstr[idx], (newX, newY)))