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, start))
    came_from = {start: None}
    cost_so_far = {start: 0}

    while frontier:
        current = heapq.heappop(frontier)[1]

        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]) and not neighbor.is_fire():
                cost_so_far[neighbor] = new_cost
                priority = new_cost + heuristic(goal, neighbor)
                heapq.heappush(frontier, (priority, neighbor))
                came_from[neighbor] = current

    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)