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)
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)
'''