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[0])-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
            self.visited.add(node[0:2])

            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[0])):
                        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[0]
        y = node[1]
        end_x = end[0]
        end_y = end[1]
        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