python - 一颗星，更新节点的 G 成本

Question

我在这里有一个有点工作的 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)

标签： pythonartificial-intelligencepath-findinga-star

Answer 1

问题是我将重复的邻居移动到 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)

'''