# AStar Implementation and Efficiency

This is my implementation of an AStar-like algorithm for maze solving.

A quick summary of the problem I am trying to solve with my algorithm might be:

A simple binary maze is given to you to solve, you may only go in the standard cardinal directions: north, east, west and south. There is a twist, however: You may also break only one wall. Create a function solution(maze) which determines the minimal number of steps to reach the end defined at point (width-1, height-1) from the start point (0, 0).

class AStar:
def __init__(self, maze):
self.queue = []
self.visited = set()
self.maze = maze
self.end = len(self.maze)-1, len(self.maze)-1

def forward(self):
self.queue.append((0, 0, False, 0, 0, None))

while self.queue:
self.queue = sorted(self.queue, key=lambda x: x[-3]+x[-4])  #Might be suboptimal to sort every time...
node = self.queue.pop(0)

if node[0:2] == self.end:
return node

new_nodes = self.rulebook(node)
self.queue.extend(new_nodes)

def rulebook(self, node):
x, y, broken, cost, heuristic, _ = node
new_nodes = []

#------RULES & ACTIONS-----#
for direction in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
x_dir, y_dir = direction
x_pdir = x + x_dir
y_pdir = y + y_dir
distance = self.distance((x_pdir, y_pdir), self.end)
if (x_pdir, y_pdir) not in self.visited:
if (x_pdir,y_pdir) not in self.visited:
if (x_pdir < len(self.maze) and y_pdir < len(self.maze)):
if (x_pdir >= 0 and y_pdir >= 0):
if self.maze[x_pdir][y_pdir] == 1:
if not broken:
new_nodes.append((x_pdir, y_pdir, True, cost+1, \
distance, node))
elif self.maze[x_pdir][y_pdir] == 0:
new_nodes.append((x_pdir, y_pdir, False, cost+1, \
distance, node))
return new_nodes
def distance(self, node, end):
#Chose the Taxicab Metric as it is more of a fit for the problem,
#as you cannot go diagonally in the problem statement.
x = node
y = node
end_x = end
end_y = end
return abs(x - end_x) + abs(y - end_y)
def backward(self, node):
steps = 0
while node != None:
steps += 1
node = node[-1]
return steps

def solution(maze):
astar = AStar(maze)
end_node = astar.forward()
steps = astar.backward(end_node)
return steps