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.")

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

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.")

 

 

Expert Solution
steps

Step by step

Solved in 5 steps

Blurred answer
Knowledge Booster
Time complexity
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education