一颗星星，更新节点的G Cost
A Star, Updating G Cost for Nodes
我这里有一个有点工作的 A* 算法。它可以找到到达目的地的路径，但是，如果有更好的路径可用，它无法更新它的路径。
例如：
s = start
e = end
x = wall
. = path
它正在这样做：
x
s......x e
.x .
.x .
.x.
.
我希望它这样做：
x
s . 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 Tiles
for 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)] = tile
def 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 Tiles
for 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)] = tile
def 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)
'''
我这里有一个有点工作的 A* 算法。它可以找到到达目的地的路径，但是，如果有更好的路径可用，它无法更新它的路径。
例如：
s = start
e = end
x = wall
. = path
它正在这样做：
x
s......x e
.x .
.x .
.x.
.
我希望它这样做：
x
s . 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 Tiles
for 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)] = tile
def 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 Tiles
for 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)] = tile
def 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)
'''