-
-
Save TylerGlaiel/6f161204ad3180395222b471e515b47a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment