A网格算法并不仅限于处理方形网格,它也可以用于处理矩形或非方形的网格。下面是一个示例代码,展示了如何使用A算法处理非方形网格。
import heapq
class Node:
def __init__(self, x, y, cost=0):
self.x = x
self.y = y
self.cost = cost
self.heuristic = 0
self.parent = None
def __lt__(self, other):
return self.cost + self.heuristic < other.cost + other.heuristic
def heuristic(node, goal):
return abs(node.x - goal.x) + abs(node.y - goal.y)
def astar(grid, start, goal):
open_list = []
closed_list = set()
start.heuristic = heuristic(start, goal)
heapq.heappush(open_list, start)
while open_list:
current = heapq.heappop(open_list)
if current.x == goal.x and current.y == goal.y:
path = []
while current:
path.append((current.x, current.y))
current = current.parent
return path[::-1]
for neighbor in neighbors(grid, current):
if neighbor in closed_list:
continue
cost = current.cost + 1
if neighbor not in open_list or cost < neighbor.cost:
neighbor.cost = cost
neighbor.heuristic = heuristic(neighbor, goal)
neighbor.parent = current
if neighbor not in open_list:
heapq.heappush(open_list, neighbor)
closed_list.add(current)
return None
def neighbors(grid, node):
neighbors = []
x, y = node.x, node.y
if x > 0 and grid[x-1][y] != 1:
neighbors.append(Node(x-1, y))
if x < len(grid)-1 and grid[x+1][y] != 1:
neighbors.append(Node(x+1, y))
if y > 0 and grid[x][y-1] != 1:
neighbors.append(Node(x, y-1))
if y < len(grid[0])-1 and grid[x][y+1] != 1:
neighbors.append(Node(x, y+1))
return neighbors
# 示例网格
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 = Node(0, 0)
goal = Node(4, 4)
path = astar(grid, start, goal)
if path:
print("路径:", path)
else:
print("无法找到路径")
以上代码演示了如何使用A算法处理一个非方形网格。在示例中,我们定义了一个Node
类来表示网格上的节点,astar
函数用于执行A算法搜索路径。heuristic
函数计算节点与目标节点之间的启发式估计值。neighbors
函数用于获取一个节点的邻居节点。最后,我们使用一个示例网格和起点、终点来演示路径搜索的过程。
下一篇:AST的DFS退出条件