基于A*算法实现mask layout 布局 代码案例 并对结果进行绘图

以下是基于A*算法实现mask layout布局的代码案例，并且对结果进行绘图：

import heapq
import matplotlib.pyplot as plt

class Node:
    def __init__(self, x, y, g, h, parent=None):
        self.x = x
        self.y = y
        self.g = g
        self.h = h
        self.parent = parent

    def __lt__(self, other):
        return (self.g + self.h) < (other.g + other.h)

class AStar:
    def __init__(self, start, end, obstacles):
        self.start = start
        self.end = end
        self.obstacles = obstacles
        self.width = len(obstacles[0])
        self.height = len(obstacles)
        self.closed_set = set()
        self.open_set = [Node(start[0], start[1], 0, self.heuristic(start, end))]
        self.parents = {}

    def heuristic(self, node, end):
        return abs(node[0] - end[0]) + abs(node[1] - end[1])

    def get_neighbors(self, node):
        neighbors = []
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x = node.x + dx
            y = node.y + dy
            if x < 0 or x >= self.width or y < 0 or y >= self.height:
                continue
            if self.obstacles[y][x]:
                continue
            neighbors.append((x, y))
        return neighbors

    def reconstruct_path(self, node):
        path = [(node.x, node.y)]
        while node.parent:
            node = node.parent
            path.append((node.x, node.y))
        return path[::-1]

    def search(self):
        while self.open_set:
            current = heapq.heappop(self.open_set)
            if (current.x, current.y) == self.end:
                return self.reconstruct_path(current)
            self.closed_set.add((current.x, current.y))
            for neighbor in self.get_neighbors(current):
                if neighbor in self.closed_set:
                    continue
                g = current.g + 1
                h = self.heuristic(neighbor, self.end)
                node = Node(neighbor[0], neighbor[1], g, h, current)
                if node not in self.open_set:
                    heapq.heappush(self.open_set, node)
                    self.parents[neighbor] = (current.x, current.y)
        return []

    def get_path(self):
        path = self.search()
        if not path:
            return []
        return [(x, y) for x, y in path]

    def get_parents(self):
        return self.parents

    def plot(self, path):
        fig, ax = plt.subplots()
        for y in range(self.height):
            for x in range(self.width):
                if self.obstacles[y][x]:
                    ax.add_patch(plt.Rectangle((x, y), 1, 1, facecolor='gray'))
        for x, y in path:
            ax.add_patch(plt.Rectangle((x, y), 1, 1, facecolor='green'))
        ax.add_patch(plt.Rectangle(self.start, 1, 1, facecolor='blue'))
        ax.add_patch(plt.Rectangle(self.end, 1, 1, facecolor='red'))
        ax.set_xlim(0, self.width)
        ax.set_ylim(0, self.height)
        ax.set_aspect('equal')
        plt.show()

使用方法：

start = (0, 0)
end = (4, 4)
obstacles = [
    [False, True, False, False, False],
    [False, True, False, True, False],
    [False, False, False, True, False],
    [True, True, True, True, False],
    [False, False, False, False, False]
]

astar = AStar(start, end, obstacles)
path = astar.get_path()
astar.plot(path)

其中，`start`和`end`是起点和终点的坐标，`obstacles`是一个二维布尔数组，表示障碍物的位置。

`get_path`方法返回从起点到终点的路径，如果无法到达终点则返回空列表。

`plot`方法绘制布局和最短路径，蓝色表示起点，红色表示终点，绿色表示最短路径。