A* with path destruction

astar_destruct_pseudo.py

def solve(self):
    # Add starting cell to open heap queue
    heapq.heappush(self.opened, (self.start.f, self.start))
    while len(self.opened):
        # Pop cell from heap queue
        f, cell = heapq.heappop(self.opened)

        # Add cell to closed list so we don't process it twice
        self.closed.add(cell)

        # If ending cell, return found path
        if cell is self.end:
            return self.get_path()

        # Get adjacent cells for cell
        adj_cells = self.get_adjacent_cells(cell)
        for adj_cell in adj_cells:

            # If the cell is a wall and we haven't destroyed one yet
            if adj_cell.is_wall and (not self.wall_destroyed):
                # Check that we haven't destroyed this cell before
                if (adj_cell.x, adj_cell.y) not in self.past_destroyed_walls:
                    # Trip the destroyed flag, so no more wall destruction :(
                    self.wall_destroyed = True
                    # Destroy the wall and make it reachable
                    self.destroy_wall(adj_cell)
                    # Add the destroyed coords to our past destroyed walls, so
                    # we don't attempt to destroy it again in another pass through
                    self.past_destroyed_walls.append((adj_cell.x, adj_cell.y))

            if adj_cell.reachable and adj_cell not in self.closed:
                if (adj_cell.f, adj_cell) in self.opened:
                    if adj_cell.g > cell.g + 10:
                        self.update_cell(adj_cell, cell)
                else:
                    self.update_cell(adj_cell, cell)
                    heapq.heappush(self.opened, (adj_cell.f, adj_cell))

def solve_all_paths(self):
    smallest_path = 100000000 # Some egregiously large number here to initialize

    # Try to destroy each wall once
    while self.path_attempts < self.num_walls:
        # Solve maze and increment attempts
        result_path = self.solve()
        self.path_attempts += 1

        # Reset path specific variables
        self.wall_destroyed = False

        # If path is returned, reevaluate the smallest path based on return
        if result_path is not None:
            if len(result_path) < smallest_path:
                smallest_path = len(result_path)

    return result_path