pathfinding.py

import heapq

class Tile:
    def __init__(self, x, y, tile_type):
        self.x = x
        self.y = y
        self.tile_type = tile_type

    def cost(self):
        if self.tile_type == "water":
            return 2
        elif self.tile_type == "fire":
            return 1
        else:
            return 1

    def is_fire(self):
        return self.tile_type == "fire"

def heuristic(a, b):
    return abs(a.x - b.x) + abs(a.y - b.y)

def a_star_search(grid, start, goal, max_movement):
    frontier = []
    heapq.heappush(frontier, (0, 0, start))
    came_from = {start: None}
    cost_so_far = {start: 0}
    counter = 1

    while frontier:
        _, _, current = heapq.heappop(frontier)

        if current == goal:
            break

        for neighbor in get_neighbors(current, grid):
            new_cost = cost_so_far[current] + neighbor.cost()
            if new_cost <= max_movement and (neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]):
                cost_so_far[neighbor] = new_cost
                priority = new_cost + heuristic(goal, neighbor) + (1000 if neighbor.is_fire() and not (current.is_fire() and neighbor == goal) else 0)
                heapq.heappush(frontier, (priority, counter, neighbor))
                came_from[neighbor] = current
                counter += 1

    return came_from, cost_so_far

def get_neighbors(tile, grid):
    neighbors = []
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        x, y = tile.x + dx, tile.y + dy
        if 0 <= x < len(grid) and 0 <= y < len(grid[0]):
            neighbors.append(grid[x][y])
    return neighbors

def reconstruct_path(came_from, start, goal):
    path = [goal]
    current = goal
    while current != start:
        current = came_from[current]
        path.append(current)
    return path[::-1]

def find_best_path(grid, start, goal, max_movement):
    came_from, cost_so_far = a_star_search(grid, start, goal, max_movement)
    if goal not in came_from:
        return None
    return reconstruct_path(came_from, start, goal)



def create_tile_grid(letter_grid):
    tile_grid = []
    for x, row in enumerate(letter_grid):
        tile_row = []
        for y, tile_type in enumerate(row):
            if tile_type == "R":
                tile_row.append(Tile(x, y, "regular"))
            elif tile_type == "W":
                tile_row.append(Tile(x, y, "water"))
            elif tile_type == "F":
                tile_row.append(Tile(x, y, "fire"))
        tile_grid.append(tile_row)
    return tile_grid


def test_case(letter_grid, start_coords, goal_coords, max_movement):
    grid = create_tile_grid(letter_grid)
    start = grid[start_coords[0]][start_coords[1]]
    goal = grid[goal_coords[0]][goal_coords[1]]
    path = find_best_path(grid, start, goal, max_movement)

    if path:
        print("Path found:")
        for tile in path:
            print(f"({tile.x}, {tile.y}) -> {tile.tile_type}")
    else:
        print("No path found within the movement range.")


letter_grid = [
    ["R", "F", "F", "F", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
    ["R", "R", "R", "R", "R", "R", "R", "R", "R", "R"],
]

start_coords = (0, 0)
goal_coords = (0, 3)
max_movement = 20

test_case(letter_grid, start_coords, goal_coords, max_movement)