[PYTHON] Lösen von Folienrätseln und 15 Rätseln
Überblick
Ich möchte die Lösung von Dia-Puzzle und 15-Puzzle ausprobieren.
Die verwendete Sprache ist Python.
Sie können hier (mit einem Link) spielen.
Der Zweck besteht darin, die Zahlen in der Reihenfolge 1, 2, 3, ... anzuordnen, indem die Zahlenzellen in die freien Zellen verschoben werden.
Völlig zufällig
Bewegen Sie sich 20 Mal, und wenn sie nicht übereinstimmen, bewegen Sie sich erneut. Drucken Sie den aktuellen Status alle 100 Sätze.
Koordinatensystem
Funktion der Klasse
slide.move(direction)
Bewegen Sie die Betriebsmasse in Richtungsrichtung 0: Oben 1: Richtig 2: Unten 3 übrig
slide.shuffle(num)
Bewegen Sie sich zufällig num mal
Ergebnis
Ich drehte es für ungefähr 10 Minuten, aber es gab keine Übereinstimmung.
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]
Das ausführbare Programm sieht folgendermaßen aus:
import random
import numpy as np #Numpy Bibliothek
class Slide():
"""
0 ist die Betriebsmasse
Oben links ist der Ursprung
Neben x
Vertikal 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)
Beim Fixieren des passenden Teils ・ Zufällig
Verwenden Sie die Befestigungsmethode vom Quadrat, das an die richtige Position verschoben werden kann. Jedoch,
[1, 2, 3, 11]
[5, 6, 7, 8]
[12, 11, 10, 9]
[15, 13, 4, 0]
Wenn Sie also 1,2,3 korrigieren, können Sie 4 an die richtige Position bringen.
Deshalb,
- 3 Ecken (weil die untere rechte Ecke leer ist)
- 2 Quadrate zwischen 3 Ecken (heraus, wenn nicht gleichzeitig angezeigt): Oberseite, linke Seite
- 2 Zeilen
- 2 Reihen
In der Reihenfolge von ausfüllen. (Nach dem Zufallsprinzip drehen, beim Einrichten korrigieren, zum nächsten wechseln) Zu diesem Zeitpunkt gibt es unten links nur 4 Quadrate, daher gibt es 6 Möglichkeiten (möglicherweise bestätigt), die zufällig gelöst werden können.
Infolgedessen ist es ziemlich gut.
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]
Es wurde mit 3652 Sätzen (3652 * 20 Züge) abgeschlossen. Wenn es völlig zufällig ist, wird es nicht abgeschlossen, selbst wenn es 10105500 Sätze überschreitet, also denke ich, dass es ziemlich gut ist. Ich habe es mehrmals gemacht und es dauert weniger als eine Sekunde, aber die Anzahl der Sätze ist gering.
(Ergänzung) Ich habe es geändert, weil ich in den Kommentaren ein besseres Programm habe. Vielen Dank.
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()
Bewegen Sie sich durch Berechnung nicht zufällig zur Zielposition
Überlegen Sie, wie Sie eine Prozedur erstellen, um die "Nummer" an einem beliebigen Ort A an einen beliebigen Ort B zu verschieben. Um A nach links zu verschieben, verschieben Sie die Operationszelle (0-Zelle) links von A und die Operationszelle nach rechts.
Der Weg zum Bewegen der Betriebszelle wird durch den A * -Algorithmus gelöst, um A oder die feste Zelle nicht zu bewegen. Zum Schluss werde ich den erstellten A * -Algorithmus einfügen.
Astar(goal_x,goal_y,start_x,start_y,obstacle)
Wenn angegeben, wird der kürzeste Weg zurückgegeben. Befestigen Sie basierend auf dieser Route die Operationsmasse neben der Zelle, die Sie verschieben möchten, und bewegen Sie sie nach oben, unten, links und rechts. Mit dieser Funktion können Sie A überall hin verschieben.
Entscheiden Sie als Nächstes, von welchem Quadrat Sie bestätigen möchten.
- 1
- 2
- 4 und 3: Wenn 3 fest ist, passt 4 nicht.
- 5
- 9 und 13 6.6 (Von hier an können Sie es lösen, indem Sie den Spielbaum durchsuchen. Ich möchte es später implementieren.)
- 7 und 8
- 10 und 14
- 11 und 12 und 15: Wenn 0 in die untere rechte Ecke verschoben wird, gibt es nur drei Möglichkeiten.
Daher wird es abgeschlossen, wenn Sie jedes Muster in Fälle unterteilen.
Zeigt den Algorithmus für zwei Stellen an, die gleichzeitig gefüllt werden müssen (3, 4 usw.).
Ausnahmsweise, wenn 3 in die obere rechte Ecke verschoben wurde, wenn 4 neben 2 platziert wurde.
In Anbetracht des Austauschverfahrens ist es wie folgt.
Das Verfahren besteht darin, sich 3 weiter zu bewegen und dann eine vertikale Reihe von 4-3 zu bilden.
Jetzt können Sie es vollständig lösen. Die Anzahl der Schritte beträgt etwa 200 bis 50. Ich habe ungefähr 80.000 zufällig verwendet, um es zu reparieren, also denke ich, dass es eine beträchtliche Verbesserung ist.
Wenn Sie das oben genannte programmieren
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 29 13:35:47 2020
@author: kisim
"""
"""
Finden Sie eine Lösung für ein Dia-Puzzle
Letztendlich möchte ich es auf Pazudora anwenden. Und strebe 10 Combo an
"""
"""
Bewegen Sie sich, während Sie vermeiden, dass dies durch den Astar-Algorithmus behoben wird
Die Fallklassifizierung ist aufgrund der Fehlerursache problematisch
"""
import random
import numpy as np #Numpy Bibliothek
import copy
import Astar as As
class Slide():
"""
0 ist die Betriebsmasse
Oben links ist der Ursprung
Neben x
Vertikal 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 #Ort der Betriebsmasse 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
Wenn Sie sich nicht bewegen-1
Wenn es sich bewegt, 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):
"""
Betriebsmasse("0"Forelle)X.,Gehe zu y
Denken Sie zuerst über die Route nach und bewegen Sie sich dann, nachdem Sie wissen, dass Sie nicht in den Fix geraten.
Dies ist eine Art Labyrinth.
A, um das Labyrinth mit einer anderen Funktion zu lösen*Implementieren Sie den Algorithmus und verwenden Sie ihn zum Lösen
"""
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]
"""
irgendein"Nummer"(x,y)Bewegen Sie sich in Richtungsrichtung
0
3 1
2
Wenn Sie sich nicht bewegen-1
Wenn es sich bewegt, 0
"""
if direction == 0: #Nach oben Die Operationsmasse oben anbringen
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: #Sich abwärts bewegen
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: #Gehe nach rechts
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: #Gehe nach links
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):
irgendein"Nummer"(x,y)Bewegen Sie sich in Richtungsrichtung
0
3 1
2
Wenn Sie sich nicht bewegen-1
Wenn es sich bewegt, 0
"""
position2 = self.find_position(number)
now_x = position2[0]
now_y = position2[1]
"""
Finden Sie die Nummernroute mit dem Astar-Algorithmus
Folgen Sie der Route und bewegen Sie sich_Bewegen Sie sich mit einem
Es wird jedoch erst eingerichtet, wenn die Straße breit ist. Bewegen Sie sich also_Jeder kann scheitern
－＞Astar ,Behandeln Sie die Reihenfolge der Befestigung
"""
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
Ersetzen mit
"""
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])
#Zum 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
#Kann es durch die Suche nach einem Spielbaum gelöst werden, da es sich um 6 Felder handelt?
#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
#Ich dachte, ich könnte damit anfangen, aber es war ein bisschen anders
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:
#Gegen den Uhrzeigersinn
hoge.move(0)
hoge.move(3)
hoge.move(2)
hoge.move(1)
elif hoge.puzzle[3][2] == 12:
#Etwa im Uhrzeigersinn
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])
Ein * Algorithmus
Aster.py
import numpy as np #Numpy Bibliothek
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 #Aktueller Knoten
self.route = []
self.goal = -1 #gaal Knoten
self.finished = 0 #Ob du das Ziel erreicht hast
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()
#Öffnen Sie herum
"""
Kann nicht geöffnet werden, wenn eine Wand / ein Hindernis vorhanden ist-> Hindernis_list
Hast du es nicht schon geschafft? -> Verrückt_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])
"""
#debuggen
print("test")
for i in self.Node_list:
print(i.state)
"""
#Berechnen Sie, was offen ist
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
#Listen Sie diejenigen auf, die offen sind und die niedrigste Punktzahl haben
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:kann nicht zielen
"""
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