-
Notifications
You must be signed in to change notification settings - Fork 0
/
A-Star.py
211 lines (168 loc) · 7.61 KB
/
A-Star.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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
from queue import PriorityQueue
import math
import random
class heuristic:
@staticmethod
def heuristicChebyshovDist(nodeA, nodeB):
# distancai Chebyshov
return max(abs(nodeA.row-nodeB.row), abs(nodeA.col-nodeB.col))
def heuristicManhattanDist(nodeA, nodeB):
# distancia Manhattan
return abs(nodeA.row-nodeB.row) + abs(nodeA.col-nodeB.col)
def heuristicEuclideanDist(nodeA, nodeB):
# distancia Euclidiana
return math.sqrt( abs(nodeA.row-nodeB.row)**2 + abs(nodeA.col-nodeB.col)**2)
class Node:
def __init__(self, row, col):
self.row = row
self.col = col
self.totalDist = -1
self.path = []
self.size = 0
def __eq__(self, other):
if not isinstance(other, Node):
return False
return self.row == other.row and self.col == other.col
#return (self.heuritcValue == other.heuritcValue)
def __ne__(self, other):
return not (self == other)
def __lt__(self, other):
return (self.totalDist < other.totalDist)
def __gt__(self, other):
return (self.totalDist > other.totalDist)
'''
def __le__(self, other):
return (self < other) or (self == other)
def __ge__(self, other):
return (self > other) or (self == other)
'''
class World:
def __init__(self):
#creamos mundo aleatorio
self.world = self.createRandomWorld(10, 10, 50, 50, 5, 40)
self.rows = len(self.world)
self.cols = len(self.world[0])
# 8 movimientos del caballo: L
self.HorseMovement = [[-1, -2], [-1, 2], [1, -2], [1, 2],
[-2, 1], [-2, -1], [2, 1], [2, -1]]
def createRandomWorld(self, minRows, minCols, maxRows, maxCols, minPercentageObstacles, maxPercentageObstacles):
cols = random.randint(minRows, maxRows)
rows = random.randint(minCols, maxCols)
world = [['.'] * cols for _ in range(rows)]
percentageObstacles = random.randint(minPercentageObstacles, maxPercentageObstacles)
amountObstacles = cols * rows * percentageObstacles // 100
while amountObstacles > 0:
row = random.randint(0, rows - 1)
col = random.randint(0, cols -1)
if (row, col) == (rows-1, 0) or (row, col) == (0, cols-1):
continue
if world[row][col] != 'x':
world[row][col] = 'x'
amountObstacles -= 1
return world
def bestFirstSearch(self, iniRow, iniCol, endRow, endCol, heuristic):
# Incializamos la matriz de visitados
self.visitedMatrix = [[False] * self.cols for _ in range(self.rows)]
# incializamos la cola para el bfs
pq = PriorityQueue()
# creamos el nodo origen y final
source = Node(iniRow, iniCol)
target = Node(endRow, endCol)
#metemos el vertice origen
pq.put(source)
# lo marcamos para siempre
# self.visitedMatrix[iniRow][iniCol] = True
# mientras haya nodos no explorados
while not pq.empty():
# obtenemos el nodo siguiente
currNode = pq.get()
if(self.visitedMatrix[currNode.row][currNode.col]):
continue
else:
self.visitedMatrix[currNode.row][currNode.col] = True
#agregamos a la ruta el de mayor prioridad
# currNode.path.append(currNode)
#pq.queue.clear()
# comparar si currNode es el nodo target
if currNode == target:
# si es, lo agregamos al path de currNode
# currNode.path.append(currNode) #no es necesario ya que al ser el mismo nodo ya se incluyo con la maxima prioridad
# imprimimos el path
'''
print("_____________________")
print(" PATH: HEURISTIC:")
print(" x ", " y ")
for i in currNode.path:
print("[",i.col,",",i.row,"] h:",i.heuritcValue)
# terminamo
print("Numero de movimientos:", len(currNode.path) -1)
'''
return currNode.size
for i in self.HorseMovement:
# i[0] -> mov de fila
# i[1] -> mov de columna
# calcular nueva casilla currNode.row + mov
casilla = [currNode.row + i[0], currNode.col +i[1]]
# comprobar que la nueva casilla este dentro del mundo
# Despues, compruebo que este libre
# despues, compruebo que no esta visitada
if(casilla[0] >= 0 and casilla[1] >= 0 and casilla[0] < self.rows and casilla[1] < self.cols
and self.world[casilla[0]][casilla[1]] == '.' and not self.visitedMatrix[casilla[0]][casilla[1]]):
#print("currNodeeee:",casilla[0], casilla[1])
#print("target nodeeee:",target.row,target.col)
# Marcar como visitado
#self.visitedMatrix[casilla[0]][casilla[1]] = True
# Crear un nuevo nodo
newNode = Node(casilla[0], casilla[1])
# Calcular ladistancia total con la heuristica mas el tamaño del path
newNode.totalDist = heuristic(newNode, target) + 2*(currNode.size+1)
#print("h:",newNode.heuritcValue,"- ",newNode.row,newNode.col)
# copio el path de currNode
newNode.path = currNode.path.copy()
newNode.size = currNode.size + 1
# newNode.path = currNode.path
# Agreagamos a la ruta
newNode.path.append(newNode)
# Agregamos el nuevo nodo a la pq
pq.put(newNode)
#imprimir que no hay solución
# print("No hay solución")
#terminamos
return -1
worldMap = [['.', 'x', '.', 'x', '.', '.'],
['.', '.', '.', 'x', '.', 'x'],
['.', 'x', '.', '.', '.', '.'],
['.', '.', '.', 'x', 'x', '.'],
['x', 'x', '.', '.', 'x', '.'],
['.', '.', '.', 'x', '.', '.']]
# promedio de las distancias
AverageManhattanDis = 0
AverageChebyshovDist = 0
AverageEuclideanDist = 0
# numero de casos no fallidos
ManhattanTest = 0
ChebyshovTest = 0
EuclideanTest = 0
for i in range(1,100):
# creamos nuevo mundo
world = World()
# r es la distancia de la esquina iferiori a izquierda hacia la superior derecha
r = world.bestFirstSearch(world.rows-1, 0, 0, world.cols-1,heuristic.heuristicManhattanDist)
# si es -1 no se encontró solución
if (r!=-1):
AverageManhattanDis += r
ManhattanTest += 1
r = world.bestFirstSearch(world.rows-1, 0, 0, world.cols-1,heuristic.heuristicChebyshovDist)
if (r!=-1):
AverageChebyshovDist += r
ChebyshovTest += 1
r = world.bestFirstSearch(world.rows-1, 0, 0, world.cols-1,heuristic.heuristicEuclideanDist)
if (r!=-1):
AverageEuclideanDist += r
EuclideanTest += 1
AverageManhattanDis /= ManhattanTest
AverageChebyshovDist /= ChebyshovTest
AverageEuclideanDist /= EuclideanTest
print("Promedio de la distancia Manhattan:",round(AverageManhattanDis,2))
print("Promedio de la distancia Chebyshov:",round(AverageChebyshovDist,2))
print("Promedio de la distancia Euclidean:",round(AverageEuclideanDist,2))