Maze BFS in Python

Question

The program below was made for a game named CheckIO, and it works. I'm just wondering if there is any way to make the code more readable.

edit: hi luke15g

def checkio(maze_map):
 #the walls of the maze are already surrounded by 1's
 start_x,start_y=1,1
 stop_x,stop_y=10,10
 class Point:
 directions={'N':(-1,0),'W':(0,-1),'E':(0,1),'S':(1,0)}
 def __init__(self,other=None,direction=None):
 if other!=None:
 self.road=other.road+direction
 self.x=other.x+Point.directions[direction][0]
 self.y=other.y+Point.directions[direction][1]
 else:
 self.x,self.y=None,None
 self.road=''
 def hit(self):
 return maze_map[self.x][self.y]==1
 def new_point(self):
 for char in Point.directions:
 x=Point(self,char)
 if not x.hit():
 yield x
 def found_it(self):
 return self.x==stop_x and self.y==stop_y
 p=[Point()]
 p[0].x,p[0].y=start_x,start_y
 begin=0
 maze_map[start_x][start_y]=1
 while begin<=len(p)-1:
 if p[begin].found_it():
 return p[begin].road
 x=p[begin].new_point()
 while 1:
 try:
 new=next(x)
 except StopIteration:
 break
 p.append(new)
 maze_map[new.x][new.y]=1
 begin+=1

• jonrsharpe: Is this in Python 2.x or 3.x?
• Costea Vlad Alexandru: It's version 3.3

Answer 1

In terms of readability:

• There is no reason to nest the class inside the function (your current need to do so is caused by bad design, see below); doing so just distracts the reader from the actual business of the function.
• Both function and class (and the class's methods) should have docstrings explaining what they do.
• Python has a bool type, so while 1: is generally written while True:.
• You mostly follow the style guide, but a bit more whitespace (e.g. around methods, assignments) would be helpful.

---

On Point itself:

• directions is a constant, so should be UPPERCASE_WITH_UNDERSCORES to indicate as much: DIRECTIONS.
• It seems odd to take an other Point instance to __init__. This is particularly awkward when you have p = [Point()]; p[0].x, p[0].y = start_x, start_y - contrast with [Point(start_x, start_y)]. Move the functionality for creating a Point from an existing instance into a @classmethod, so you would call x = Point.from_point(self, char).
• road, the path of directions taken to get to the current point, could be a list instead of a str.
• Rather than found_it, refactor to is_at(self, x, y), so you don't have to have stop_x and stop_y in scope (see above) and if p[begin].found_it(): becomes if p[begin].is_at(stop_x, stop_y):, which is a little more explicit.
• Similarly, hit and new_point should take the maze_map as a parameter, rather than relying on scope.
• hit is only called within the class, so should probably be private-by-convention (i.e. named _hit instead).
• Point.directions is also accessible via self.directions, which will handle inheritance better.
• new_point yields more than one Point, so should be plural (new_points).

With these modifications:

class Point:
 DIRECTIONS = {'N': (-1, 0), 'W': (0, -1), 'E': (0, 1), 'S': (1, 0)}
 def __init__(self, x, y, road=None):
 self.x, self.y = x, y
 self.road = road or []
 @classmethod
 def from_point(cls, other, direction):
 """Create a new point from an existing point and direction."""
 d_x, d_y = cls.DIRECTIONS[direction]
 return cls(
 other.x + d_x, 
 other.y + d_y, 
 other.road + [direction],
 )
 def _hit(self, map):
 """Would this point hit a wall in the map?"""
 return map[self.x][self.y] == 1
 def new_points(self, map):
 """Generate new points from the current point."""
 for char in self.directions:
 new_point = Point.from_point(self, char)
 if not new_point._hit(map):
 yield new_point
 def is_at(self, x, y):
 """Whether the point is at the specified location."""
 return self.x == x and self.y == y

---

And on the checkio function:

• You can neaten while begin <= len(p) - 1: to while begin < len(p):.
• The names are pretty bad - p should be points, begin should be current (it's only begin at the beginning!).
• The while 1: loop would be much neater if you just iterated over new_points: for point in points[current].new_points():.

As modified:

def checkio(maze_map):
 """Solve the maze.
 The walls of the maze are already surrounded by 1s.
 """
 start_x, start_y = 1, 1
 stop_x, stop_y = 10, 10
 points = [Point(start_x, start_y)]
 current = 0
 maze_map[start_x][start_y] = 1
 while current < len(points):
 if points[current].is_at(stop_x, stop_y):
 return ''.join(points[current].road)
 for new_point in points[current].new_points(maze_map):
 points.append(new_point)
 maze_map[new_point.x][new_point.y] = 1
 current += 1

---

If you implemented __eq__ and __hash__ on the Point class, you could keep a set of the points you've already visited, rather than adding a "wall" into the map when you visit a particular location.

• Costea Vlad Alexandru: What does @classmethod do?
• jonrsharpe: @user2015213 it makes a method act on the class, instead of an instance, see e.g. stackoverflow.com/q/12179271/3001761, stackoverflow.com/q/136097/3001761

Answer 2

Point

It would help a lot if Point did not have to know about how to read the maze. Instead, it should concentrate on being a coordinate and crumbtrail. The hit() and found_it() functionality should move into a Maze class.

The fact that you wrote start_x,start_y and stop_x,stop_y indicates that Point is not doing its job — it should be more like start = Point(1, 1). p=[Point()]; p[0].x,p[0].y=start_x,start_y is even weirder — it should be queue = [start]. The 0 in self.x=other.x+Point.directions[direction][0] is also rather mysterious. The remedy for all of these problems is to make Point into a namedtuple.

According to your directions, the +x axis points south, and the +y axis points east. It would be more conventional to rename x and y as "row" and "column".

Maze

Now that we have a Point, it would be helpful have a way to fetch and set the value at a Point. For that, we define a Maze class, with an overridden [] operator.

With all the clutter out of the way, what remains is a solve() method that processes the queue. I suggest renaming p to queue and using idiomatic iteration techniques.

Suggested solution

from collections import namedtuple
class Point(namedtuple('Point', ['r', 'c'])):
 def __init__(self, r, c):
 self.src = None
 def __add__(self, other):
 return Point(self.r + other.r, self.c + other.c)
 def __sub__(self, other):
 return self + -other
 def __neg__(self):
 return Point(-self.r, -self.c)
 @property
 def neighbors(self):
 for delta in Point.DIRECTIONS:
 p = self + delta
 p.src = self
 yield p
 @property
 def path(self):
 if self.src is not None:
 yield from self.src.path
 yield Point.DIRECTIONS[self - self.src]
Point.DIRECTIONS = {
 Point(-1, 0): 'N',
 Point(0, -1): 'W', Point(0, +1): 'E',
 Point(+1, 0): 'S',
}
class Maze:
 def __init__(self, maze_map):
 """maze_map is a two-dimensional array, where each 1 indicates an
 obstacle. The walls of the maze must be surrounded by 1's."""
 self.maze_map = [row[:] for row in maze_map]
 def __getitem__(self, point):
 return self.maze_map[point.r][point.c]
 def __setitem__(self, point, value):
 self.maze_map[point.r][point.c] = value
 def solve(self, start=Point(1, 1), goal=Point(10, 10)):
 def enqueue(queue, point):
 if not self[point]:
 self[point] = 1
 queue.append(point)
 queue = []
 if start == goal:
 return start.path
 enqueue(queue, start)
 for point in queue:
 for neighbor in point.neighbors:
 if neighbor == goal:
 return neighbor.path
 enqueue(queue, neighbor)
maze = Maze(...)
print(''.join(maze.solve()))

• Gareth Rees: +1 for moving methods out of the Point class. But I still don't like the way this code uses Point.src. It shouldn't be the responsibility of a point to represent a path.