A*算法的python实现
# -*- coding: utf-8 -*-
class Node():
def __init__(self, parent, x, y, G, H):
self.parent = parent
self.x = x
self.y = y
self.G = G
self.H = H
@property
def F(self):
return self.G + self.H
class Astar():
"""
x0,y0:起点的坐标; x1,y1:目标点的坐标; weight,height:地图大小; gamemap:游戏地图;
is_path:若不计算路径只判断能否到达则为False; ground:地板
"""
def __init__(self, x0, y0, x1, y1, weight, height, gamemap, is_path, ground):
self.__start_x = x0
self.__start_y = y0
self.__end_x = x1
self.__end_y = y1
self.__weight = weight
self.__height = height
self.__map = gamemap
self.__open = []
self.__close = []
self.__is_path = is_path
self.__ground = ground
self.path = []
def __index(self, node_list, node):
for i, n in enumerate(node_list):
if(n.x == node.x and n.y == node.y):
return i
return -1
def __G(self, parent_x, parent_y, child_x, child_y):
if(child_x == parent_x or child_y == parent_y):
return 10
return 14
def __extend_node(self, node):
direction_x = (-1, 0, 1, -1, 1, -1, 0, 1)#八方向
direction_y = (-1, -1, -1, 0, 0, 1, 1, 1)
for x, y in zip(direction_x, direction_y):
new_x = node.x + x
new_y = node.y + y
new_G = node.G + self.__G(node.x, node.y, new_x, new_y)
new_H = (abs(self.__end_x - new_x) + abs(self.__end_y - new_y)) * 10
if not (((0 <= new_x <= self.__weight and 0 <= new_y <= self.__height)) and
(self.__map[new_x][new_y] == self.__ground)):#如果新的点不合要求就放弃
continue
new_node = Node(node, new_x, new_y, new_G, new_H)
if self.__index(self.__close, new_node) != -1:
continue
pos = self.__index(self.__open, new_node)
if pos != -1:
if self.__open[pos].G > new_node.G:
self.__open[pos].parent = node
self.__open[pos].G = new_G
self.__open[pos].H = new_H
continue
self.__open.append(new_node)
def find_path(self):
start = Node(None, self.__start_x, self.__start_y, 0, 0)
self.__open.append(start)
while True:
self.__extend_node(start)
if not self.__open:
return
start = self.__open[0]
for node in self.__open:
if node.F < start.F:
start = node
if start.x == self.__end_x and start.y == self.__end_y:#是否到达终点
if self.__is_path:
self.__get_path(start)
return True
self.__close.append(start)
del self.__open[0]
def __get_path(self, node):#回溯找到起点 起点的parent = None
while node:
self.path.append(node)
node = node.parent
优质内容筛选与推荐>>