Instantly share code, notes, and snippets.

@akpw /grid.py
Last active Jul 26, 2017

Embed
What would you like to do?
Finds shortest path in rectangular grid with obstacles
#!/usr/bin/env python
# coding=utf8
## explained in details
## in this blog: http://www.akpdev.com/articles/2016/05/26/Leonidas.html
class Point:
''' Represents a point
'''
def __init__(self, x = 0, y = 0):
self.x = x
self.y = y
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def __hash__(self):
return hash((self.x, self.y))
def __str__(self):
return '({0}, {1})'.format(self.x, self.y)
class PathFinder:
''' Finds paths in rectangular field with obstacles
'''
def __init__(self, field):
self._field = field
def shortest_path(self, start_point, end_point):
''' Given start / end points, finds a shortest path between the two (if it exists)
'''
self._check_range(start_point)
self._check_range(end_point)
if self.is_obstacle(start_point) or self.is_obstacle(end_point):
return []
# the queue of paths
queue = []
visited = set()
queue.append([start_point])
while queue:
# the first path from the queue
path = queue.pop(0)
# the last point from the path
current_point = path[-1]
# path found?
if current_point == end_point:
return path
for adjacent_point in self._adjacent_points(current_point):
if adjacent_point not in visited:
visited.add(adjacent_point)
# construct a new path and add it to the queue
new_path = list(path)
new_path.append(adjacent_point)
queue.append(new_path)
# no path found
return []
@property
def max_y(self):
return len(self._field)
@property
def max_x(self):
return len(self._field[0])
def is_obstacle(self, point):
return self._field[point.y][point.x] == 0
def _adjacent_points(self, point):
''' given a point, finds all adjacent points that are not obstacles
'''
adjacent_points = []
# can take a step into either directions
for x in range(-1,2): ## -1 <- x -> +1
# 0 <= adj_x <= self.max_x - 1
adj_x = min(max(point.x + x, 0), self.max_x - 1)
for y in range (-1,2): ## -1 <- y -> +1
# 0 <= adj_y <= self.max_y - 1
adj_y = min(max(point.y + y, 0), self.max_y - 1)
if adj_x == point.x and adj_y == point.y:
continue
adjacent_point = Point(adj_x, adj_y)
if self.is_obstacle(adjacent_point):
continue
# all checks passed
adjacent_points.append(adjacent_point)
return adjacent_points
def _check_range(self, point):
if point.x < 0 or point.x >= self.max_x or point.y < 0 or point.y >= self.max_y:
raise ValueError("out of defined field range")
################## Test ##################
import random
from datetime import datetime
from functools import reduce
def print_field(field, start_point, end_point, path):
s = set(path)
def node_repr(point):
if path and point == start_point:
return 'S'
elif path and point == end_point:
return 'E'
elif point in s:
return '*'
elif field[point.y][point.x] == 0:
return 'x'
else:
return ' '
visual_field = [[node_repr(Point(x,y)) for x in range(range_X)] for y in range(range_Y)]
reversed_visual_field = [row for row in reversed(visual_field)]
print()
print('\n'.join(str(row) for row in reversed_visual_field))
def print_summary(start_point, end_point, path):
if path:
print('\nShortest path from {0} to {1}): \n '.format(start_point, end_point), \
'->'.join([s.__str__() for s in path]))
else:
print('No path from {0} to {1} (distance: -1)'.format(start_point, end_point))
if __name__ == '__main__':
### set the field range
range_X, range_Y = 12, 14
### printing a large field could be impractical, set your preferred limits here
printable_field = True if range_X <= 16 and range_Y <= 16 else False
# generate a field of given size, with random obstacles
test_field = [[random.randrange(2) for _ in range(range_X)] for _ in range(range_Y)]
pathFinder = PathFinder(test_field)
# find a shortest path in the field, iterate till success
# record the time for all attempts
path, passedTimes = [], []
while not path:
# generate random start / end points
start_point, end_point = Point(0,0), Point(0,0)
while start_point == end_point:
start_point = Point(random.randrange(range_X),random.randrange(range_Y))
end_point = Point(random.randrange(range_X),random.randrange(range_Y))
# if one of the points is an obstacle, reset
if pathFinder.is_obstacle(start_point) or pathFinder.is_obstacle(end_point):
start_point, end_point = Point(0,0), Point(0,0)
# start recording time
start_time = datetime.now()
path = pathFinder.shortest_path(start_point, end_point)
delta = datetime.now() - start_time
# print the field if appropriate
if path and printable_field:
print_field(test_field, start_point, end_point, path)
elif not passedTimes and printable_field:
# for unsuccessful attempts, print the initial field just once
print_field(test_field, start_point, end_point, path)
passedTimes.append(delta)
print_summary(start_point, end_point, path)
# print time reports
found_time = passedTimes.pop()
print ('\nFound path with distance {0} in: {1}.{2}sec'.format(\
len(path) - 1, found_time.seconds, found_time.microseconds))
if passedTimes:
avg_nf_time = reduce( (lambda x, y: x + y), passedTimes ) / len(passedTimes)
print ('Avg time for "not found" attempts: {0}.{1}sec\n'.format(\
avg_nf_time.seconds, avg_nf_time.microseconds))
@whizzer0

This comment has been minimized.

whizzer0 commented Jul 26, 2017

I'm getting a strange problem where sometimes it will randomly return [] even when a valid path exists. I can't seem to find a pattern to this. The coordinates of the points go from the top-left of the grid, right?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment