A Star, Updating G Cost for Nodes

Question

I have a somewhat working A* algorithm here. It can find a path to the destination, however, it is unable to update its path if a better one becomes available.

for example:

s = start
e = end
x = wall
. = path

it is doing this:

       x
s......x   e
      .x  .
      .x .
      .x.
       .

and I want it to do this:

       x
s .    x   e
   .   x  .
    .  x .
     . x.
       .

What I need is for the tiles(nodes) to change their parent node to one with a lower G - cost if it is available. The struggle in implementing this is real.

Any help is greatly appreciated,

Cheers

    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)

Answer 1

def aStarSearch(problem: SearchProblem, heuristic=None):
    """Search the node that has the lowest combined cost and heuristic first."""
    "*** YOUR CODE HERE ***"
    class Node:  
      def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.g = 0
        self.h = 0
        self.f = 0

    def __repr__(self):
        return "Node(state=%s, g=%s, h=%s, f=%s)" % (self.state, self.g, self.h, self.f)

    print("There is A* start",problem.getStartState())
    start=problem.getStartState()
    openSet=[]
    closeSet=[]
    openSet.append(start)
    while (openSet):
        current=openSet.pop(0)
        print("current:",current)
        if problem.isGoalState(current):
            path = reconstruct_path(curren)
            return path
        closeSet.append(current)
        print("In Close set we add current value",current)
        successors=problem.getSuccessors(current)
        print("There we add s",successors)
        for successor in successors:
            if successor in closeSet:
                continue
            successor_node=Node(successor,current)
            successor_node.g= current.g + cost_to_move(current.state, successor)
            successor_node.h = heuristic(successor, start)
            successor_node.f = successor_node.g + successor_node.h
            print("successor.g we have:",successor.g)
            if successor_node in open_list and successor_node.f >= open_list[open_list.index(successor_node)].f:
                continue
            open_list.append(successor_node)
 #In this i still face some issue like Error Like:
successor_node.g= current.g + cost_to_move(current.state, successor)
AttributeError: 'tuple' object has no attribute 'g'
​

Answer 2

The problem was I was moving duplicate neighbors to "unchecked" tiles with incorrect G-costs. Anyhow here is a working A* algorithm :)

'''

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)

'''