# Maze pathfinding implementation (BFS) not giving correct path [closed]

#### Tags: algorithm, breadth-first-search, maze, path-finding, python

I am trying to get the shortest path for a maze with a ball: the ball is rolling until it hits a wall. I use Dijkstra’s algorithm using `heapq` for priority queue. However, I get a non-optimal path as result.

Here is my code with sample input:

```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

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 fewer changes of direction.

I am currently getting `rdrludlrdrudludldldr` (i.e. right-down-right-left-…) as an output, but the sequence “rl” found at index 2 doesn’t make sense: “Right” should not be followed by “Left” nor should “Up” be followed by “Down” and vice versa. Such a sequence is evidently not optimal as the first of those two moves could just be omitted to get the ball at the same location and travelling shorter distance.

The expected output for this maze is `drururdrdrurdrd`.

Why am I not getting the shortest path?

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)))
```

Source: stackoverflow