-
Notifications
You must be signed in to change notification settings - Fork 0
/
versao_final.py
145 lines (109 loc) · 4.81 KB
/
versao_final.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import random
from matplotlib.colors import ListedColormap
from matplotlib.patches import Rectangle
from collections import deque
import heapq
class Node:
def __init__(self, state, parent=None, cost=0, heuristic=0):
self.state = state
self.parent = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other):
return (self.cost + self.heuristic) < (other.cost + other.heuristic)
def astar(start, goal, neighbors, heuristic):
start_node = Node(state=start, cost=0, heuristic=heuristic(start))
frontier = [start_node]
explored = set()
while frontier:
current_node = heapq.heappop(frontier)
if current_node.state == goal:
path = []
while current_node:
path.append(current_node.state)
current_node = current_node.parent
return path[::-1]
explored.add(current_node.state)
for neighbor in neighbors(current_node.state):
if neighbor in explored:
continue
cost = current_node.cost + 1 # assume que todos os movimentos têm o mesmo custo
heuristic_value = heuristic(neighbor)
new_node = Node(state=neighbor, parent=current_node, cost=cost, heuristic=heuristic_value)
if new_node not in frontier:
heapq.heappush(frontier, new_node)
return None # Se não encontrar um caminho
def animate_path(path, start, goal, walls, maze_shape):
cmap = ListedColormap(['white', 'black', 'green', 'red', 'blue', 'gray'])
fig, ax = plt.subplots()
ax.set_xlim(0, maze_shape[1])
ax.set_ylim(0, maze_shape[0])
ax.set_aspect('equal')
maze = [[0] * maze_shape[1] for _ in range(maze_shape[0])]
for i in range(maze_shape[0]):
for j in range(maze_shape[1]):
maze[i][j] = Rectangle((j, maze_shape[0] - i - 1), 1, 1, color='white', ec='black')
ax.add_patch(maze[i][j])
start_rect = Rectangle((start[1], maze_shape[0] - start[0] - 1), 1, 1, color='green', ec='black')
goal_rect = Rectangle((goal[1], maze_shape[0] - goal[0] - 1), 1, 1, color='red', ec='black')
ax.add_patch(start_rect)
ax.add_patch(goal_rect)
for wall in random_walls:
maze[wall[0]][wall[1]].set_facecolor('black')
counter_text = ax.text(0.5, 1.01, '', transform=ax.transAxes, ha='center')
def update(frame):
current_state = path[frame]
maze[current_state[0]][current_state[1]].set_facecolor('blue')
counter_text.set_text(f'Movimentos: {frame }')
ani = animation.FuncAnimation(fig, update, frames=len(path), repeat=False)
plt.show()
# Exemplo de uso:
def neighbors(state, walls):
x, y = state
possible_moves = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] # movimentos para a direita, esquerda, cima, baixo
valid_moves = [(x, y) for x, y in possible_moves if 0 <= x < maze_shape[0] and 0 <= y < maze_shape[1] and (x, y) not in walls]
return valid_moves
def heuristic(state, goal):
return abs(state[0] - goal[0]) + abs(state[1] - goal[1])
def is_connected(start, goal, walls, maze_shape):
visited = set()
queue = deque([start])
while queue:
current = queue.popleft()
if current == goal:
return True
visited.add(current)
for neighbor in neighbors(current, walls):
if neighbor not in visited and neighbor not in queue:
queue.append(neighbor)
return False
def generate_random_walls(maze_shape, num_walls, start, goal):
walls = set()
while True:
walls.clear()
while len(walls) < num_walls:
wall_candidate = (random.randint(0, maze_shape[0] - 1), random.randint(0, maze_shape[1] - 1))
if wall_candidate != start and wall_candidate != goal:
walls.add(wall_candidate)
if is_connected(start, goal, walls, maze_shape):
break
return list(walls)
#PARAMETROS
# Aumente o tamanho do tabuleiro
maze_shape = (30, 30)
# Geração aleatória das posições inicial e final
start = (random.randint(0, maze_shape[0] - 1), random.randint(0, maze_shape[1] - 1))
goal = (random.randint(0, maze_shape[0] - 1), random.randint(0, maze_shape[1] - 1))
#Percentual de paredes (deve ser menor que 100%)
walls_percentage = 0.3
# Quantidade de paredes
num_walls = (maze_shape[0] * maze_shape[1]) * walls_percentage
# Geração aleatória da localização das paredes
if walls_percentage > 0.9:
print("Erro: O valor de 'walls_percentage' deve ser menor ou igual a 0.9.")
exit()
random_walls = generate_random_walls(maze_shape, num_walls, start, goal)
path = astar(start, goal, lambda state: neighbors(state, random_walls), lambda state: heuristic(state, goal))
animate_path(path, start, goal, random_walls, maze_shape)