我这里有一个基本可用的A星算法。它能够找到通往目的地的路径，但是如果有更好的路径可用时，它无法更新路径。
例如：
s = 起点e = 终点x = 墙. = 路径它现在是这样做的：
xs......x e .x . .x . .x. .而我希望它这样做：
xs . x e . x . . x . . x. .我需要的是当有更低的G成本的节点可用时，瓦片（节点）能够更改它们的父节点。实现这一点确实是个挑战。
任何帮助都将不胜感激，
谢谢
map = [['w','w','w','w','w'],['w','w','x','w','w'],['w','w','x','w','w'],['w','w','x','w','w'],['w','w','w','w','w'],]""" make copy of dict in the function! """tile_data = {}class Tile: def __init__(self, pos, char): self.pos = pos self.char = char self.parent = None self.H = 0 self.G = float('inf') self.F = 0#Gen Tilesfor y in range(len(map)): for x in range(len(map[0])): char = map[y][x] tile = Tile((x,y), char) tile_data[(x,y)] = tiledef a_star(start, end, map): unchecked_tiles = [] checked_tiles = [] # set start position tile_data[start].parent = None tile_data[start].pos = start tile_data[start].G = 0 unchecked_tiles.append(tile_data[start]) while unchecked_tiles: #Get the tile with lowest F score current_tile = min(unchecked_tiles, key=lambda tile: tile.F) #move tile to checked list checked_tiles.append(current_tile) unchecked_tiles.remove(current_tile) # If the End is found return the path of parent tiles if current_tile.pos == end: path = [] while current_tile.parent is not None: path.append(current_tile.pos) # Sets current tile to parent tile current_tile = current_tile.parent for tile in path: print(tile, ": F = ", tile_data[tile].F, ": G = ", tile_data[tile].G, ": H = ", tile_data[tile].H) return path[::-1] # Return reversed path # Gets valid neighbors for current tile neighbors = [] for dir in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: #get tile pos neighbor = (current_tile.pos[0] + dir[0], current_tile.pos[1] + dir[1]) #check if tile on map and is valid if 0 <= neighbor[0] < len(map[0]) and 0 <= neighbor[1] < len(map) and tile_data[neighbor].char == 'w' and tile_data[neighbor] not in checked_tiles: # Set parent for neighbors tile_data[neighbor].parent = current_tile # Add neighbor to lists unchecked_tiles.append(tile_data[neighbor]) neighbors.append(neighbor) for neighbor in neighbors: # Set G cost (14 for diagonal, 10 for othogonal move + parent.G cost) if tile_data[neighbor].pos[0] == current_tile.pos[0] or tile_data[neighbor].pos[1] == current_tile.pos[1]: tile_data[neighbor].G = 10 + current_tile.G else: tile_data[neighbor].G = 14 + current_tile.G if tile_data[neighbor].G < current_tile.G: current_tile.parent = tile_data[neighbor].parent # Set H cost (a**2 + b**2 = c**2) tile_data[neighbor].H = ((neighbor[0] - end[0]) ** 2) + ((neighbor[1] - end[1]) ** 2) # Set F cost (G + H) tile_data[neighbor].F = tile_data[neighbor].H + tile_data[neighbor].G print('finished')a_star((0,2),(4,2),map)回答：
问题是我之前将重复的邻居节点移动到“未检查”列表中时，G成本是错误的。无论如何，这里有一个可用的A星算法 🙂
”’
map = [['w','w','w','w','w'],['w','w','x','w','w'],['w','w','x','w','w'],['w','w','x','w','w'],['w','w','w','w','w'],]""" make copy of dict in the function! """tile_data = {}class Tile: def __init__(self, pos, char): self.pos = pos self.char = char self.parent = None self.H = 0 self.G = 0 self.F = 0#Gen Tilesfor y in range(len(map)): for x in range(len(map[0])): char = map[y][x] tile = Tile((x,y), char) tile_data[(x,y)] = tiledef a_star(start, end, map): unchecked_tiles = [] checked_tiles = [] # set start position tile_data[start].parent = None tile_data[start].pos = start tile_data[start].G = 0 unchecked_tiles.append(tile_data[start]) while unchecked_tiles: #Get the tile with lowest F score current_tile = min(unchecked_tiles, key=lambda tile: tile.F) #move tile to checked list checked_tiles.append(current_tile) unchecked_tiles.remove(current_tile) # If the End is found return the path of parent tiles if current_tile.pos == end: path = [] while current_tile.parent is not None: path.append(current_tile.pos) # Sets current tile to parent tile current_tile = current_tile.parent for tile in path: print(tile, ": F = ", tile_data[tile].F, ": G = ", tile_data[tile].G, ": H = ", tile_data[tile].H) return path[::-1] # Return reversed path # Gets valid neighbors for current tile neighbors = [] for dir in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: #get tile pos neighbor = (current_tile.pos[0] + dir[0], current_tile.pos[1] + dir[1]) #check if tile on map and is valid if 0 <= neighbor[0] < len(map[0]) and 0 <= neighbor[1] < len(map) and tile_data[neighbor].char == 'w' and tile_data[neighbor] not in checked_tiles: if tile_data[neighbor] not in unchecked_tiles: # Add neighbor to lists unchecked_tiles.append(tile_data[neighbor]) neighbors.append(neighbor) # Set parent for neighbors tile_data[neighbor].parent = current_tile for neighbor in neighbors: # Set G cost (14 for diagonal, 10 for othogonal move + parent.G cost) if tile_data[neighbor].pos[0] == current_tile.pos[0] or tile_data[neighbor].pos[1] == current_tile.pos[1]: tile_data[neighbor].G = 10 + current_tile.G else: tile_data[neighbor].G = 14 + current_tile.G if tile_data[neighbor].G < current_tile.G: current_tile.parent = tile_data[neighbor].parent if tile_data[neighbor].pos[0] == current_tile.pos[0] or tile_data[neighbor].pos[1] == current_tile.pos[1]: current_tile.G = tile_data[neighbor].G + 10 else: current_tile.G = tile_data[neighbor].G + 14 # Set H cost (a**2 + b**2 = c**2) tile_data[neighbor].H = ((neighbor[0] - end[0]) ** 2) + ((neighbor[1] - end[1]) ** 2) # Set F cost (G + H) tile_data[neighbor].F = tile_data[neighbor].H + tile_data[neighbor].G print('finished')a_star((0,2),(4,2),map)”’
