博客

python实现A*寻路算法

  • Post category:Python

下面是关于“Python实现A*寻路算法”的完整攻略。

1. A*寻路算法简介

A寻路算法是种启发式搜索算法，用于在图形中寻找最短路径。它使用估价函数来评估每个节点的优先级，并选择先级最高的节点进行扩展。A寻路算法可以在有向和无向图中使用，并且可以处理带权重的边。

2. Python实现A*寻路算法

2.1 算法流程

A*寻路算法的流程如下：

  1. 初始化起点和终点。
  2. 将起点加入开放列表。
  3. 从开放列表中选择优先级最高的节点进行扩展。
  4. 对于每个相邻节点，计算估价函数值，并将其加入开放列表。
  5. 如果终点在开放列表中，则返回路径。
  6. 如果开放列表为空，则返回无解。

2.2 Python实现

在Python中，我们可以使用以下代码实现A*寻路算法：

import heapq

class AStar:
    def __init__(self, grid, start, end):
        self.grid = grid
        self.start = start
        self.end = end
        self.open_list = []
        self.closed_list = set()

    def heuristic(self, a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    def get_neighbors(self, node):
        neighbors = []
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
 x = node[0] + dx
            y = node[1] + dy
            if 0 <= x < len(self.grid) and 0 <= y < len(self.grid[0]) and self.grid[x][y] == 0:
                neighbors.append((x, y))
        return neighbors

    def get_path(self, current):
        path = []
        while current is not None:
            path.append(current)
            current = current.parent
        return path[::-1]

    def search(self):
        heapq.heappush(self.open_list, (0, self.start))
        while self.open_list:
            current = heapq.heappop(self.open_list)[1]
            if current == self.end:
                return self.get_path(current)
            self.closed_list.add(current)
            for neighbor in self.get_neighbors(current):
                if neighbor in self.closed_list:
                    continue
                g = current.g + 1
                h = self.heuristic(neighbor, self.end)
                f = g + h
                if neighbor in [i[1] for i in self.open_list]:
                    index = [i[1] for i in self.open_list].index(neighbor)
                    if self.open_list[index][0] > f:
                        self.open_list[index] = (f, neighbor, current)
                else:
                    heapq.heappush(self.open_list, (f, neighbor, current))
        return None

在这个代码中，我们定义了一个 AStar 类，用于实现A*寻路算法。我们首先在 __init__() 函数中初始化起点、终点、开放列表和关闭列表。然后，定义了一个 heuristic() 函数，用于计算估价函数值。在 get_neighbors() 函数中，我们计算当前节点的相邻节点。在 get_path() 函数中，我们从终点开始，沿着每个节点的父节点，一直回溯到起点，得到路径。在 search() 函数中，我们使用堆来实现开放列表，并使用 heappush() 和 heappop() 函数来维护堆的优先级。我们首先将起点加入开放列表，然后从开放列表中选择优先级最高的节点进行扩展。对于每个相邻节点，我们计算估价函数值，并将其加入开放列表。如果终点在开放列表中，则返回路径。如果开放列表为空，则返回无解。

2.3 示例说明

下面是一个使用A*寻路算法的示例：

grid = [[0, 0, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 0, 0]]
start = (0, 0)
end = (4, 4)
astar = AStar(grid, start, end)
path = astar.search()
print(path)

在这个示例中，我们首先定义了一个二维网格 grid，其中 0 表示可通过的节点，1 表示障碍物。然后，我们定义了起点 start 和终点 end。最后，我们创建一个 AStar 对象，并使用 search() 函数来寻找最短路径。我们打印路径。

面是另一个使用A*寻路算法的示例：

import numpy as np
import matplotlib.pyplot as plt

grid = np.zeros((100, 100))
grid[20:80, 20:80] = 1
start = (10, 10)
end = (90, 90)
astar = AStar(grid, start, end)
path = astar.search()

plt.imshow(grid, cmap="gray")
plt.plot(start[1], start[0], "ro")
plt.plot(end[1], end[0], "bo")
for i in range(len(path) - 1):
    plt.plot([path[i][1], path[i+1][1]], [path[i][0], path[i+1][0]], "r")
plt.show()

在这个示例中，我们首先创建一个 100100 的二维网格 grid，其中 0 表示可通过的节点，1 表示障碍物。然后，我们定义了起点 start 和终点 end。最后，我们创建一个 AStar 对象，并使用 search() 函数来寻找最短路径。我们使用 imshow() 函数来显示二维网格，使用 plot() 函数来显示起点、终点和路径。

Tags: ,