The following code is implementing a Treasure map use the A* algorithm to find the shortest path between two points in a map. It appears that the initial compare looks at the f_cost and decides that we are at the point in the map and exits the routine and prints only the starting point. I'm not sure how to fix it, any help would get appreciated. Example of the output from the following Python program: start place = (0, 0) Treasure location: (29, 86) Path to treasure: (0, 0) Python Code: import heapq import random class Tile: def __init__(self, x, y): self.x = x self.y = y self.is_obstacle = False self.g_cost = 0 self.h_cost = 0 self.f_cost = 0 self.parent = None # Define comparison methods for Tile objects based on their f_cost def __lt__(self, other): return self.f_cost < other.f_cost def __eq__(self, other): return self.f_cost == other.f_cost class Map: def __init__(self, width, height): self.width = width self.height = height self.tiles = [[Tile(x, y) for y in range(height)] for x in range(width)] self.start_tile = self.get_tile(0, 0) self.treasure_tile = None self.generate_treasure() def generate_treasure(self): self.treasure_tile = self.get_random_tile() self.treasure_tile.is_obstacle = True def get_random_tile(self): x = random.randint(0, self.width - 1) y = random.randint(0, self.height - 1) return self.get_tile(x, y) def get_tile(self, x, y): return self.tiles[x][y] def get_adjacent_tiles(self, tile): adjacent_tiles = [] for x in range(tile.x - 1, tile.x + 2): for y in range(tile.y - 1, tile.y + 2): if x == tile.x and y == tile.y: continue if x < 0 or x >= self.width or y < 0 or y >= self.height: continue adjacent_tiles.append(self.get_tile(x, y)) return adjacent_tiles class AStar: def __init__(self, game_map, start_tile, treasure_tile): self.game_map = game_map self.start_tile = start_tile self.treasure_tile = treasure_tile def find_path(self): open_list = [] closed_list = [] start_tile = self.start_tile treasure_tile = self.treasure_tile heapq.heappush(open_list, (start_tile.f_cost, start_tile)) while len(open_list) > 0: current_tile = heapq.heappop(open_list)[1] closed_list.append(current_tile) if current_tile == treasure_tile: path = [] while current_tile != start_tile: path.append((current_tile.x, current_tile.y)) current_tile = current_tile.parent path.append((start_tile.x, start_tile.y)) path.reverse() return path adjacent_tiles = self.game_map.get_adjacent_tiles(current_tile) for tile in adjacent_tiles: if tile.is_obstacle or tile in closed_list: continue g_cost = current_tile.g_cost + 1 h_cost = abs(tile.x - treasure_tile.x) + abs(tile.y - treasure_tile.y) f_cost = g_cost + h_cost if (tile.f_cost, tile) in open_list: if tile.g_cost > g_cost: tile.g_cost = g_cost tile.h_cost = h_cost tile.f_cost = f_cost tile.parent = current_tile heapq.heapify(open_list) else: tile.g_cost = g_cost tile.h_cost = h_cost tile.f_cost = f_cost tile.parent = current_tile heapq.heappush(open_list, (tile.f_cost, tile)) return None # Create the game board game_board = Map(100, 100) # starting_place = Tile(0, 0) starting_place = game_board.start_tile treasure_place = game_board.treasure_tile print("Treasure location:", (treasure_place.x, treasure_place.y)) # Find the path using A* algorithm path_finder = AStar(game_board, starting_place, treasure_place) path = path_finder.find_path() if path: print("Path to treasure:") for step in path: print(step) else: print("No path to treasure found.")
The following code is implementing a Treasure map use the A*
start place = (0, 0)
Treasure location: (29, 86)
Path to treasure:
(0, 0)
Python Code:
import heapq
import random
class Tile:
def __init__(self, x, y):
self.x = x
self.y = y
self.is_obstacle = False
self.g_cost = 0
self.h_cost = 0
self.f_cost = 0
self.parent = None
# Define comparison methods for Tile objects based on their f_cost
def __lt__(self, other):
return self.f_cost < other.f_cost
def __eq__(self, other):
return self.f_cost == other.f_cost
class Map:
def __init__(self, width, height):
self.width = width
self.height = height
self.tiles = [[Tile(x, y) for y in range(height)] for x in range(width)]
self.start_tile = self.get_tile(0, 0)
self.treasure_tile = None
self.generate_treasure()
def generate_treasure(self):
self.treasure_tile = self.get_random_tile()
self.treasure_tile.is_obstacle = True
def get_random_tile(self):
x = random.randint(0, self.width - 1)
y = random.randint(0, self.height - 1)
return self.get_tile(x, y)
def get_tile(self, x, y):
return self.tiles[x][y]
def get_adjacent_tiles(self, tile):
adjacent_tiles = []
for x in range(tile.x - 1, tile.x + 2):
for y in range(tile.y - 1, tile.y + 2):
if x == tile.x and y == tile.y:
continue
if x < 0 or x >= self.width or y < 0 or y >= self.height:
continue
adjacent_tiles.append(self.get_tile(x, y))
return adjacent_tiles
class AStar:
def __init__(self, game_map, start_tile, treasure_tile):
self.game_map = game_map
self.start_tile = start_tile
self.treasure_tile = treasure_tile
def find_path(self):
open_list = []
closed_list = []
start_tile = self.start_tile
treasure_tile = self.treasure_tile
heapq.heappush(open_list, (start_tile.f_cost, start_tile))
while len(open_list) > 0:
current_tile = heapq.heappop(open_list)[1]
closed_list.append(current_tile)
if current_tile == treasure_tile:
path = []
while current_tile != start_tile:
path.append((current_tile.x, current_tile.y))
current_tile = current_tile.parent
path.append((start_tile.x, start_tile.y))
path.reverse()
return path
adjacent_tiles = self.game_map.get_adjacent_tiles(current_tile)
for tile in adjacent_tiles:
if tile.is_obstacle or tile in closed_list:
continue
g_cost = current_tile.g_cost + 1
h_cost = abs(tile.x - treasure_tile.x) + abs(tile.y - treasure_tile.y)
f_cost = g_cost + h_cost
if (tile.f_cost, tile) in open_list:
if tile.g_cost > g_cost:
tile.g_cost = g_cost
tile.h_cost = h_cost
tile.f_cost = f_cost
tile.parent = current_tile
heapq.heapify(open_list)
else:
tile.g_cost = g_cost
tile.h_cost = h_cost
tile.f_cost = f_cost
tile.parent = current_tile
heapq.heappush(open_list, (tile.f_cost, tile))
return None
# Create the game board
game_board = Map(100, 100)
# starting_place = Tile(0, 0)
starting_place = game_board.start_tile
treasure_place = game_board.treasure_tile
print("Treasure location:", (treasure_place.x, treasure_place.y))
# Find the path using A* algorithm
path_finder = AStar(game_board, starting_place, treasure_place)
path = path_finder.find_path()
if path:
print("Path to treasure:")
for step in path:
print(step)
else:
print("No path to treasure found.")
Step by step
Solved in 5 steps
