# Maze BFS in Python

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.x=other.x+Point.directions[direction][0]
self.y=other.y+Point.directions[direction][1]
else:
self.x,self.y=None,None
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():
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

• Is this in Python 2.x or 3.x? – jonrsharpe May 31 '15 at 10:41
• It's version 3.3 – Costea Vlad Alexandru May 31 '15 at 10:58

• 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)}

self.x, self.y = x, y

@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,
)

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):
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.

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

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

• +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. – Gareth Rees Jun 1 '15 at 13:27