First solution in Uncategorized category for Open Labyrinth by _Chico_
Navigate a maze and return a route from the start to the finish.
Use A* to find a path in an efficient manner.
# The cardinal directions
DIRECTIONS = [
(0, -1, 'N'),
(0, 1, 'S'),
(-1, 0, 'W'),
(1, 0, 'E'),
Node = collections.namedtuple('Node', ['hist', 'ix', 'dist', 'pt', 'prev', 'direction'])
def heuristic(point, goal):
Return an admissible heuristic for the distance from point to goal.
For the case of a grid with orthogonal movement, use the Manhattan distance.
return abs(point - goal) + abs(point - goal)
Return a string of the characters [NSEW] describing a path through labyrinth.
labyrinth: A list of lists. '0' indicates a passable cell.
height, width = len(labyrinth), len(labyrinth)
start = (1, 1)
goal = (height - 2, width - 2)
# Each node consists of (estimated path distance, ix, dist, (x, y), previous node, direction)
# The ix field is a serial number to ensure that subsequent fields are
# not compared.
open = [Node(heuristic(start, goal), 0, 0, start, None, None)]
# A set of all visited coordinates.
explored = set()
ix = 1
node = heapq.heappop(open)
_, _, dist, point, prev, prev_d = node
if point in explored:
if point == goal:
# Now consider moves in each direction.
for dx, dy, d in DIRECTIONS:
new_point = point + dx, point + dy
if new_point not in explored and \
h = dist + 1 + heuristic(new_point, goal)
tie_break = 4 if prev_d != d else 0 # Prefer moving straight
new_node = Node(h, ix + tie_break, dist + 1, new_point, node, d)
ix = ix + 1
# Return a path to node
result = ''
while node.prev is not None:
result = node.direction + result
node = node.prev
July 10, 2021