[PYTHON] Résoudre des puzzles et 15 puzzles
Aperçu
Je voudrais essayer la solution de puzzle de diapositives et 15 puzzle.
Le langage utilisé est le python.
Vous pouvez jouer ici (avec un lien).
En déplaçant les cellules numériques vers les cellules vacantes, le but est de les organiser dans l'ordre de 1, 2, 3, ....
Complètement aléatoire
Bougez 20 fois, et s'ils ne correspondent pas, bougez à nouveau. Imprimez l'état actuel tous les 100 ensembles.
Système de coordonnées
Fonction de classe
slide.move(direction)
Déplacer la masse opérationnelle dans le sens de la direction 0: au-dessus 1: droite 2: ci-dessous 3 restants
slide.shuffle(num)
Déplacer au hasard nombre de fois
résultat
Je l'ai tourné pendant environ 10 minutes, mais il n'y avait pas de correspondance.
10105300times
[2, 7, 4, 1]
[3, 10, 8, 12]
[6, 5, 14, 15]
[0, 11, 9, 13]
10105400times
[0, 9, 2, 3]
[14, 1, 8, 7]
[13, 15, 11, 12]
[5, 10, 6, 4]
10105500times
[9, 10, 5, 6]
[15, 2, 13, 8]
[12, 7, 0, 1]
[4, 3, 11, 14]
Le programme exécutable ressemble à ceci:
import random
import numpy as np #Bibliothèque Numpy
class Slide():
"""
0 est la masse d'opération
Le coin supérieur gauche est l'origine
À côté de x
Verticalement y
Tosul
"""
def __init__(self):
self.puzzle = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,0]]
self.x = 3
self.y = 3
def shuffle(self,num):
for i in range(num):
j=0
while True:
j = random.randint(0,3)
break
self.move(j)
def move(self,direction):
"""
0
3 1
2
"""
if direction == 0:
if self.y != 0:
if self.fixed[self.y-1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y-1][self.x]
self.y = self.y - 1
self.puzzle[self.y][self.x] = 0
if direction == 1:
if self.x != 3:
if self.fixed[self.y][self.x+1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x+1]
self.x = self.x + 1
self.puzzle[self.y][self.x] = 0
if direction == 2:
if self.y != 3:
if self.fixed[self.y+1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y+1][self.x]
self.y = self.y + 1
self.puzzle[self.y][self.x] = 0
if direction == 3:
if self.x != 0:
if self.fixed[self.y][self.x-1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x-1]
self.x = self.x - 1
self.puzzle[self.y][self.x] = 0
def check(self):
for i in range(4):
for j in range(4):
if self.puzzle[i][j] != j+1+i*4:
return -1
return 0
if __name__ == '__main__' :
hoge = Slide()
hoge.shuffle(500)
print(hoge.puzzle)
n=0
while True:
hoge.shuffle(20)
flag = hoge.check()
if flag == 0:
break
n=n+1
if n%100 == 0:
print(str(n)+"times")
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
print("find")
print(str(n) + "times")
print(hoge.puzzle)
Lors de la fixation de la partie correspondante ・ Aléatoire
Utilisez la méthode de fixation à partir du carré qui peut être déplacé vers la bonne position. cependant,
[1, 2, 3, 11]
[5, 6, 7, 8]
[12, 11, 10, 9]
[15, 13, 4, 0]
Donc, si vous corrigez 1, 2, 3, vous pouvez déplacer 4 à la bonne position.
Donc,
- 3 coins (car le coin inférieur droit est vide)
- 2 carrés entre 3 coins (dehors s'ils n'apparaissent pas en même temps): côté supérieur, côté gauche
- 2 lignes
- 2 rangées
Terminez dans l'ordre de. (Tournez au hasard, corrigez une fois établi, passez au suivant) À ce stade, il n'y a que 4 carrés en bas à gauche, donc il y a 6 façons (peut-être confirmé), et cela peut être résolu au hasard.
En conséquence, c'est plutôt bon.
shuffled puzzle
[11, 5, 2, 7]
[1, 6, 12, 14]
[0, 13, 9, 3]
[8, 15, 4, 10]
start analyze
3652times
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 0]
Il a été complété avec 3652 sets (3652 * 20 coups). S'il est complètement aléatoire, il ne sera pas terminé même s'il dépasse 10105500 ensembles, donc je pense que c'est assez bon. Je l'ai fait plusieurs fois et cela prend moins d'une seconde, mais le nombre d'ensembles est limité.
(Ajout) Je l'ai changé car j'ai un meilleur programme dans les commentaires. Merci beaucoup.
import random
class Slide:
def __init__(self):
self.puzzle = [
[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9, 10, 11, 12],
[13, 14, 15, 0],
]
self.x = 3
self.y = 3
self.fixed = [False] * 16
def __iter__(self):
return iter(self.puzzle)
def shuffle(self, num):
DIRS = (0, -1), (1, 0), (0, 1), (-1, 0)
for _ in range(num):
dx, dy = random.choice(DIRS)
x = self.x + dx
y = self.y + dy
if 0 <= x <= 3 and 0 <= y <= 3 and not self.fixed[y * 4 + x]:
self.puzzle[self.y][self.x] = self.puzzle[y][x]
self.x = x
self.y = y
self.puzzle[self.y][self.x] = 0
def fix(self, numbers):
if all(self.fixed[number - 1] for number in numbers):
return True
if any(self.puzzle[(number - 1) // 4][(number - 1) % 4] != number
for number in numbers):
return False
for number in numbers:
self.fixed[number - 1] = True
return True
def solve(puzzle):
CORNER = 1, 4, 13
UPPERSIDE = 2, 3
LEFTSIDE = 5, 9
ROW2 = 6, 7, 8
COL2 = 6, 10, 14
RIGHTLOWER = 11, 12, 15
n = 0
while not puzzle.fix(CORNER):
puzzle.shuffle(20)
n += 1
while not puzzle.fix(UPPERSIDE) or not puzzle.fix(LEFTSIDE):
puzzle.shuffle(20)
n += 1
while not puzzle.fix(ROW2) or not puzzle.fix(COL2):
puzzle.shuffle(20)
n += 1
while not puzzle.fix(RIGHTLOWER):
puzzle.shuffle(20)
n += 1
return n
def main():
puzzle = Slide()
puzzle.shuffle(500)
print("shuffled puzzle")
print(*puzzle, sep='\n')
print("start analyze")
n = solve(puzzle)
print(n, "times")
print(*puzzle, sep='\n')
if __name__ == '__main__':
main()
Déplacer vers la position cible par calcul, pas de manière aléatoire
Considérez comment créer une procédure pour déplacer le «nombre» de n'importe quel endroit A vers n'importe quel endroit B. Pour déplacer A vers la gauche, déplacez la cellule d'opération (cellule 0) vers la gauche de A et déplacez la cellule d'opération vers la droite.
L'itinéraire pour déplacer la cellule opérationnelle est résolu par l'algorithme A * afin de ne pas déplacer A ou la cellule fixe. Enfin, je vais coller l'algorithme A * créé.
Astar(goal_x,goal_y,start_x,start_y,obstacle)
Si est donné, l'itinéraire le plus court est renvoyé. Sur la base de cet itinéraire, attachez la masse d'opération à côté de la cellule que vous souhaitez déplacer et déplacez-la vers le haut, le bas, la gauche et la droite. Cette fonction vous permet de déplacer A n'importe où.
Ensuite, décidez à partir de quelle case vous souhaitez confirmer.
- 1
- 2
- 4 et 3: si 3 est fixe, 4 ne conviendra pas.
- 5
- 9 et 13 6.6 (À partir de là, vous pouvez le résoudre en recherchant dans l'arborescence du jeu, je veux l'implémenter plus tard)
- 7 et 8
- 10 et 14
- 11 et 12 et 15: Ici, si 0 est déplacé vers le coin inférieur droit, il n'y a que trois façons.
Par conséquent, il sera terminé si vous divisez chaque motif en cas.
Affiche l'algorithme pour deux emplacements qui doivent être remplis en même temps (3, 4, etc.).
À titre exceptionnel, si 3 a été déplacé vers le coin supérieur droit lorsque 4 a été placé à côté de 2.
Compte tenu de la procédure de remplacement, elle est la suivante.
La procédure consiste à déplacer 3 plus loin, puis à faire une ligne verticale de 4-3.
Vous pouvez maintenant le résoudre complètement. Le nombre d'étapes est d'environ 200 à 50. J'en ai utilisé environ 80 000 au hasard pour le réparer, donc je pense que c'est une amélioration considérable.
Si vous programmez ce qui précède
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 29 13:35:47 2020
@author: kisim
"""
"""
Trouvez une solution à un puzzle de diapositives
En fin de compte, je veux l'appliquer à Pazudora. Et visez 10 combos
"""
"""
Déplacez-vous en évitant de corriger l'algorithme Astar
La classification des cas est problématique en raison de la cause de l'erreur
"""
import random
import numpy as np #Bibliothèque Numpy
import copy
import Astar as As
class Slide():
"""
0 est la masse d'opération
Le coin supérieur gauche est l'origine
À côté de x
Verticalement y
Tosul
"""
def __init__(self):
self.puzzle = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,0]]
self.x = 3 #Emplacement de l'opération masse 0
self.y = 3
self.fixed = np.zeros((4,4))
self.route = [[self.x,self.y]]
def route_clear(self):
self.route = [[self.x,self.y]]
def shuffle(self,num):
for i in range(num):
j=0
while True:
j = random.randint(0,3)
break
self.move(j)
def move(self,direction):
"""
0
3 1
2
Si tu ne bouges pas-1
S'il bouge, 0
"""
if direction == 0:
if self.y != 0:
if self.fixed[self.y-1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y-1][self.x]
self.y = self.y - 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
if direction == 1:
if self.x != 3:
if self.fixed[self.y][self.x+1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x+1]
self.x = self.x + 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
if direction == 2:
if self.y != 3:
if self.fixed[self.y+1][self.x] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y+1][self.x]
self.y = self.y + 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
if direction == 3:
if self.x != 0:
if self.fixed[self.y][self.x-1] == 0:
self.puzzle[self.y][self.x] = self.puzzle[self.y][self.x-1]
self.x = self.x - 1
self.puzzle[self.y][self.x] = 0
self.route.append([self.x,self.y])
return 0
else:
return -1
return -1
def move_0(self,x,y):
"""
Masse d'opération("0"truite)X,Déplacer vers y
Pensez d'abord à l'itinéraire, puis déplacez-vous une fois que vous savez que vous ne serez pas pris au piège.
C'est une sorte de labyrinthe.
A pour résoudre le labyrinthe avec une autre fonction*Implémentez l'algorithme et utilisez-le pour résoudre
"""
hoge = As.Astar(x,y,self.x,self.y,self.fixed)
result = hoge.explore()
route = []
if result == 0:
route = hoge.route
else:
return -1
for i in range(len(route)-1):
if route[i][0] < route[i+1][0]:
self.move(1)
elif route[i+1][0] < route[i][0]:
self.move(3)
elif route[i+1][1] < route[i][1]:
self.move(0)
elif route[i+1][1] > route[i][1]:
self.move(2)
if self.x !=x or self.y != y:
return -1
else:
return 0
def move_any(self,position,direction):
x=position[0]
y=position[1]
"""
tout"nombre"(x,y)Se déplacer dans le sens de la direction
0
3 1
2
Si tu ne bouges pas-1
S'il bouge, 0
"""
if direction == 0: #Monter Fixer la masse d'opération sur le dessus
self.fixed[y][x] = 1
hoge = self.move_0(x,y-1)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
elif direction == 2: #Descendre
self.fixed[y][x] = 1
hoge = self.move_0(x,y+1)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
elif direction == 1: #Déplacer vers la droite
self.fixed[y][x] = 1
hoge = self.move_0(x+1,y)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
elif direction == 3: #Déplacer vers la gauche
self.fixed[y][x] = 1
hoge = self.move_0(x-1,y)
self.fixed[y][x] = 0
if hoge == -1:
return -1
else:
self.move_0(x,y)
return 0
def find_position(self,num):
for i in range(4):
for j in range(4):
if self.puzzle[i][j] == num:
return (j,i)
def move_x(self,number,position):
target_x = position[0]
target_y = position[1]
"""
def move_any(self,position,direction):
tout"nombre"(x,y)Se déplacer dans le sens de la direction
0
3 1
2
Si tu ne bouges pas-1
S'il bouge, 0
"""
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
"""
Trouvez l'itinéraire numérique avec l'algorithme Astar
Suivez l'itinéraire et bougez_Bougez avec n'importe quel
Cependant, il ne sera établi que si la route est large, alors_tout peut échouer
－＞Astar ,Traiter l'ordre de fixation
"""
hoge = As.Astar(target_x,target_y,now_x,now_y,self.fixed)
result = hoge.explore()
route = []
if result == 0:
route = hoge.route
else:
return -1
for i in range(len(route)-1):
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
if route[i][0] < route[i+1][0]:
result = self.move_any((now_x,now_y),1)
if result == -1:
return -1
elif route[i+1][0] < route[i][0]:
result = self.move_any((now_x,now_y),3)
if result == -1:
return -1
elif route[i+1][1] < route[i][1]:
result = self.move_any((now_x,now_y),0)
if result == -1:
return -1
elif route[i+1][1] > route[i][1]:
result = self.move_any((now_x,now_y),2)
if result == -1:
return -1
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
if target_x != now_x or target_y != now_y:
return -1
else:
return 0
def exchange_row(self):
"""
4 3
x 0
y z
Remplacer par
"""
self.move(0)
self.move(3)
"""
0 4
x 3
y z
"""
self.move(2)
self.move(2)
self.move(1)
"""
x 4
y 3
z 0
"""
self.move(0)
"""
x 4
y 0
z 3
"""
self.move(3)
self.move(0)
self.move(1)
"""
4 0
x y
z 3
"""
def exchange_line(self):
"""
13 0 y
9 x z
"""
self.move(3)
self.move(2)
"""
9 13 y
0 x z
"""
self.move(1)
self.move(1)
self.move(0)
"""
9 13 0
x y z
"""
self.move(3)
"""
9 0 13
x y z
"""
self.move(2)
self.move(3)
self.move(0)
"""
0 y 13
9 x z
"""
def route_test(slide,route):
if route == []:
return -1
else:
for i in range(len(route)-1):
if route[i][0] < route[i+1][0]:
slide.move(1)
elif route[i+1][0] < route[i][0]:
slide.move(3)
elif route[i+1][1] < route[i][1]:
slide.move(0)
elif route[i+1][1] > route[i][1]:
slide.move(2)
return slide
if __name__ == '__main__' :
hoge = Slide()
hoge.shuffle(600)
hoge.route_clear()
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
#Pour le test
hoge2 = Slide()
hoge2.puzzle = copy.deepcopy(hoge.puzzle)
hoge2.x = hoge.x
hoge2.y = hoge.y
#1
hoge.move_x(1,(0,0))
hoge.fixed[0][0] =1
#2
hoge.move_x(2,(1,0))
hoge.fixed[0][1] =1
#3,4
hoge.move_x(4,(2,0))
hoge.fixed[0][2] =1
if hoge.x == 3 and hoge.y == 0 and hoge.puzzle[1][3] == 3:
hoge.move(2)
if hoge.puzzle[0][3] == 3:
hoge.fixed[0][2] = 0
hoge.move_0(3,1)
hoge.exchange_row()
print("errored 3-4")
hoge.move_x(3,(2,1))
hoge.fixed[1][2] = 1
hoge.move_0(3,0)
hoge.fixed[1][2] = 0
hoge.fixed[0][2] = 0
hoge.move(3)
hoge.move(2)
hoge.fixed[0][2] = 1
hoge.fixed[0][3] = 1
#5
hoge.move_x(5,(0,1))
hoge.fixed[1][0] =1
#9,13
hoge.move_x(9,(0,3))
hoge.fixed[3][0] =1
if hoge.x == 0 and hoge.y == 2 and hoge.puzzle[2][1] == 13:
hoge.move(1)
if hoge.puzzle[2][0] == 13:
hoge.fixed[3][0] = 0
hoge.move_0(1,2)
hoge.exchange_line()
print("error 9-13")
hoge.fixed[3][0] = 1
hoge.move_x(13,(1,3))
hoge.fixed[3][1] = 1
hoge.move_0(0,2)
hoge.fixed[3][1] = 0
hoge.fixed[3][0] = 0
hoge.move(2)
hoge.move(1)
hoge.fixed[2][0] = 1
hoge.fixed[3][0] = 1
#6
hoge.move_x(6,(1,1))
hoge.fixed[1][1] =1
#7,8
hoge.move_x(8,(2,1))
hoge.fixed[1][2] =1
if hoge.x == 3 and hoge.y == 1 and hoge.puzzle[2][3] == 7:
hoge.move(2)
if hoge.puzzle[1][3] == 7:
hoge.fixed[1][2] = 0
hoge.move_0(3,2)
hoge.exchange_row()
print("error 7-8")
hoge.move_x(7,(2,2))
hoge.fixed[2][2] = 1
hoge.move_0(3,1)
hoge.fixed[2][2] = 0
hoge.fixed[1][2] = 0
hoge.move(3)
hoge.move(2)
hoge.fixed[1][3] = 1
hoge.fixed[1][2] = 1
#Puisqu'il fait 6 carrés, peut-il être résolu en recherchant un arbre de jeu?
#10,14
result = hoge.move_x(10,(1,3))
print(str(result)+"result")
hoge.fixed[3][1] =1
if hoge.x == 1 and hoge.y == 2 and hoge.puzzle[2][2] == 14:
hoge.move(1)
if hoge.puzzle[2][1] == 14:
hoge.fixed[3][1] = 0
hoge.move_0(2,2)
hoge.exchange_line()
print("error10-14")
hoge.fixed[3][1] = 1
hoge.move_x(14,(2,3))
hoge.fixed[3][2] = 1
hoge.move_0(1,2)
hoge.fixed[3][2] = 0
hoge.fixed[3][1] = 0
hoge.move(2)
hoge.move(1)
hoge.fixed[2][1] = 1
hoge.fixed[3][1] = 1
#Je pensais que je pouvais aller avec ça, mais c'était un peu différent
hoge.move_0(3,3)
print("a")
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
print(hoge.fixed[0])
print(hoge.fixed[1])
print(hoge.fixed[2])
print(hoge.fixed[3])
if hoge.puzzle[3][2] == 11:
#Autour dans le sens antihoraire
hoge.move(0)
hoge.move(3)
hoge.move(2)
hoge.move(1)
elif hoge.puzzle[3][2] == 12:
#Autour des aiguilles d'une montre
hoge.move(3)
hoge.move(0)
hoge.move(1)
hoge.move(2)
print(hoge.puzzle[0])
print(hoge.puzzle[1])
print(hoge.puzzle[2])
print(hoge.puzzle[3])
print(len(hoge.route))
hoge2 = route_test(hoge2,hoge.route)
if hoge2 == -1:
print("error")
else:
print(hoge2.puzzle[0])
print(hoge2.puzzle[1])
print(hoge2.puzzle[2])
print(hoge2.puzzle[3])
Algorithme A *
Aster.py
import numpy as np #Bibliothèque Numpy
import random
import copy
class Node():
def __init__(self,x,y,cost,parent,num):
self.x = x
self.y = y
self.state = 1 # 0:none 1:open 2:closed
self.score = 0
self.cost = cost
self.parent = parent
self.expect_cost = 0
self.num = num
self.calculated = 0
def close(self):
self.state = 2
class Astar():
def __init__(self,g_x,g_y,s_x,s_y,obstacle):
self.width = obstacle.shape[1]
self.height = obstacle.shape[0]
self.g_x = g_x
self.g_y = g_y
self.s_x = s_x
self.s_y = s_y
self.x = s_x
self.y = s_y
self.obstacle_list = copy.deepcopy(obstacle)
self.maked_list = []
self.num = 0
start = Node(s_x,s_y,0,-1,self.num)
self.Node_list = [start]
self.num = self.num + 1
self.now = start #Nœud actuel
self.route = []
self.goal = -1 #nœud gaal
self.finished = 0 #Si vous avez atteint l'objectif
if g_x == s_x and g_y == s_y:
self.finished == 1
self.goal = start
self.route = [[s_x,s_y]]
def open(self):
self.now.close()
#Ouvert autour
"""
Impossible d'ouvrir lorsqu'il y a un mur / obstacle-> obstacle_list
Vous ne l'avez pas déjà fait? -> Maded_list
"""
cost = self.now.cost
parent = self.now.num
if self.x!=0:
if self.maked_list.count([self.x-1,self.y]) == 0 and self.obstacle_list[self.y][self.x-1] == 0 :
self.Node_list.append(Node(self.x-1,self.y,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x-1,self.y])
if self.x!=self.width-1:
if self.maked_list.count([self.x+1,self.y]) == 0 and self.obstacle_list[self.y][self.x+1] == 0 :
self.Node_list.append(Node(self.x+1,self.y,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x+1,self.y])
if self.y!=0:
if self.maked_list.count([self.x,self.y-1]) == 0 and self.obstacle_list[self.y-1][self.x] == 0 :
self.Node_list.append(Node(self.x,self.y-1,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x,self.y-1])
if self.y!=self.height-1:
if self.maked_list.count([self.x,self.y+1]) == 0 and self.obstacle_list[self.y+1][self.x] == 0 :
self.Node_list.append(Node(self.x,self.y+1,cost+1,parent,self.num))
self.num = self.num + 1
self.maked_list.append([self.x,self.y+1])
"""
#déboguer
print("test")
for i in self.Node_list:
print(i.state)
"""
#Calculez ce qui est ouvert
for i in self.Node_list:
if i.state == 1 and i.calculated == 0:
i.calculated = 1
i.expect_cost = abs(i.x - self.g_x)+abs(i.y-self.g_y)
i.score = i.cost + i.expect_cost
#Listez ceux qui sont ouverts et qui ont le score le plus bas
min_cost = 100
min_cost_list = []
for i in self.Node_list:
if i.state == 1:
if i.cost < min_cost:
min_cost = i.cost
min_cost_list = [i]
elif i.cost == min_cost:
min_cost_list.append(i)
if min_cost_list != []:
self.now = min_cost_list[random.randint(0,len(min_cost_list)-1)]
self.x = self.now.x
self.y = self.now.y
else:
print("none min")
return -1
if self.now.x == self.g_x and self.now.y == self.g_y:
return 1
else:
return 0
def explore(self):
"""
0 :goal
-1:ne peut pas viser
"""
if self.finished == 1:
return 0
else:
while True:
hoge = self.open()
if hoge == 1:
#print("goal!")
self.goal = self.now
self.finished = 1
self.Route()
return 0
elif hoge == -1:
return -1
def Route(self):
if self.finished == 1:
while True:
self.route.append((self.now.x,self.now.y))
if self.now.parent == -1:
break
else:
self.now = self.Node_list[self.now.parent]
self.route.reverse()
#print(self.route)
def Express(self):
if self.finished == 1:
if self.route ==[]:
print("not goaled")
else:
graph = self.obstacle_list
for i in self.route:
graph[i[1]][i[0]] = 2
print(graph)
if __name__ == '__main__' :
width = 5
height = 5
obstacle =np.zeros((height,width))
"""
obstacle[2][1] = 1
obstacle[2][2] = 1
obstacle[1][2] = 1
obstacle[3][2] = 1
"""
obstacle[1][0] = 1
print(obstacle)
g_x = 0
g_y = 2
s_x = 0
s_y = 0
hoge = Astar(g_x,g_y,s_x,s_y,obstacle)
result = hoge.explore()
if result == 0:
hoge.Express()
Recommended Posts