Autopilot (Software)

Martin Vogel ⌂ @, Dortmund / Bochum, Mon, 03.07.2017, 23:28 (vor 2459 Tagen) @ Martin Vogel

Da Menschen wohl nicht in der Lage sind, so ein perfektes Spiel hinzubekommen …

[image]

… habe ich mal einen Autopiloten in das Hamster-vs-Python-Spiel eingebaut, der mit Pos1 (Home) gestartet werden kann. Er reicht allerdings bei Weitem nicht an den Algorithmus aus dem GIF oben heran.

[image]

Verbesserungsvorschläge sind willkommen.

Download: [image]ZIP-Archiv_DTN3OFPF1.zip

  1. #! /usr/bin/python3
  2.  
  3. from tkinter import Tk, Canvas, PhotoImage
  4. from tkinter.messagebox import showinfo, askyesno
  5. from tkinter.simpledialog import askstring
  6. from random import randint, choice, sample
  7. from getpass import getuser
  8. from webbrowser import open as showpage
  9. from urllib.parse import urlencode
  10. from time import sleep, strftime
  11.  
  12. # Python vs. Hamster
  13. # ~~~~~~~~~~~~~~~~~~
  14. #
  15. # Ein Beispielprogramm zur Auswertung der Daten von Eventhandlern für
  16. # Tastendrücke und zur simplen Datenübermittlung an eine Webseite
  17. #
  18. # Version vom 1. Juli 2017
  19. # Autor: Dipl.-Ing. Martin Vogel, Hochschule Bochum
  20. # Lizenz: cc-by-3.0 https://creativecommons.org/licenses/by/3.0/de/
  21. #
  22. # Diese Abwandlung des klassischen Snake-Spiels lässt eine Schlange
  23. # kleine blaue Java-Hamster fressen.
  24. #
  25. # Das Spielfeld ist 29×29 Felder groß und wird auf einer Canvas in 24-facher
  26. # Größe wiedergegeben.
  27. #
  28. # Die Schlange wird mit den Cursortasten gesteuert.
  29. #
  30. # Jeder Hamster lässt die Schlange um 5 Segmente wachsen und 5% schneller
  31. # werden. Für den ersten Hamster gibt es 100 Punkte, für den zweiten 200
  32. # und so weiter. Für jeden Bewegungsschritt wird wieder ein Punkt abgezogen.
  33. #
  34. # Das Spiel endet, wenn die Schlange gegen die Wand stößt oder mit sich
  35. # selbst kollidiert.
  36. #
  37. # Auf einer Webseite lässt sich durch das Programm ein Highscorewert eintragen.
  38. url = "http://ruhrhochschule.de/hamsterscore.py"
  39. #
  40. # Diese Version des Spiels verfügt über einen Autopiloten, der mit "Pos1"
  41. # gestartet, mit "End" in den Turbomodus geschaltet und mit den Cursortasten
  42. # wieder beendet wird.
  43. Algorithmusname = "Große Welle 5"
  44. #
  45. #
  46. # Vorlage für den Hamsterkopf war das bekannte Motiv von Daniel Jasper und
  47. # Dietrich Boles aus ihrem freien Programmierlernprogramm Hamster-Simulator.
  48. #
  49.  
  50.  
  51. class countdown:
  52. "Zählt von 3 bis 1 rückwärts."
  53. # Jede anfangs riesige bildfüllende Ziffer wird innerhalb einer Sekunde
  54. # immer kleiner.
  55. def __init__(self, event=None):
  56. # Mauszeiger für die Canvas abschalten
  57. C.config(cursor="none")
  58. # Bildschirm aufräumen
  59. C.delete("Schlange")
  60. Hamster.verstecken()
  61. # Anfangswert
  62. self.counter = 3
  63. # Ziffer rot und mittig anzeigen
  64. self.text = C.create_text(360, 360, fill="red")
  65. # Zähler starten
  66. self.count()
  67.  
  68.  
  69. def count(self):
  70. "Animationsschritt des Countdowns"
  71. # Das Attribut counter zählt Sekundenbruchteile; angezeigt werden nur
  72. # die ganzen Sekunden.
  73. n = int(self.counter) + 1
  74. # Die Zifferngröße in Pixeln entspricht dem Nachkommawert mal 1000
  75. s = (self.counter*1000) % 1000
  76. # Neue Größe setzen
  77. C.itemconfig(self.text, text=n, font="helvetica -%i bold" % s)
  78. # Alle 17 ms soll ein Animationsschritt erfolgen.
  79. self.counter -= 0.017
  80. if self.counter > 0 and not Schlange.Turbo:
  81. C.after(17, self.count)
  82. else:
  83. C.delete(self.text)
  84. Schlange.Start()
  85.  
  86.  
  87. def username():
  88. "Gibt den Spielernamen zurück"
  89. # Wurde der schon eingegeben?
  90. if hasattr(Hamster, "username"):
  91. un = Hamster.username
  92. else:
  93. # Fragen wir doch mal das Betriebssystem nach dem Anmeldenamen:
  94. un = getuser()
  95. # Dieser kann übernommen oder geändert werden.
  96. un = askstring("Hallo, äh … "+un+"?",
  97. "Gib Deinen Namen ein:",
  98. initialvalue=un)
  99. # Wurde die Eingabe mit "OK" bestätigt?
  100. if un:
  101. Hamster.username = un
  102. # Oder wurde der Eingabedialog abgebrochen?
  103. else:
  104. un = ""
  105. return un
  106.  
  107.  
  108. class C_Hamster:
  109. """Der Hamster weiß, wo er ist, wie er aussieht und alles wichtige
  110. über den Spieler."""
  111. def __init__(self):
  112. # Das Hamsterbild (24×24 Pixel, GIF) muss im Verzeichnis des
  113. # Pythonprogramms liegen.
  114. try:
  115. # Wenn es da ist, merkt sich der Hamster sein Aussehen.
  116. self.bilddatei = PhotoImage(file="Hamster24.gif")
  117. self.bild_ID = C.create_image(-24, -24, image=self.bilddatei)
  118. except:
  119. # Falls nicht, gibt's 'nen schnöden Ersatzhamster: ⬤ u2b24
  120. self.bild_ID = C.create_text(-24, -24, text="⬤",
  121. font="courier -24 bold",
  122. fill="blue")
  123. # Immer, wenn die persönliche Bestleistung übertroffen wird,
  124. # gibt es das Angebot, es in die Highscoreliste einzutragen.
  125. self.highscore = 0
  126.  
  127. # Zu Beginn jeder Runde:
  128. self.reset()
  129.  
  130. def reset(self):
  131. # Anzahl der Wiederbelebungen
  132. self.zähler = 0
  133.  
  134. # Aktuell erreichte Punktzahl
  135. self.punkte = 0
  136.  
  137. #
  138. # Philosophischer Einschub:
  139. #
  140. # F: „Wieso bekommt eigentlich der Hamster die Punkte und nicht die
  141. # Schlange?“
  142. #
  143. # A: „Nun, wer glaubt, dass es in diesem Spiel darum geht, Hamster zu
  144. # besiegen, hat die Fabel vom Hasen und Igel nicht verstanden.
  145. # In Wirklichkeit gewinnt nämlich immer der Hamster die Spielrunden
  146. # und die Schlange stirbt.“
  147. #
  148. # F: „…“
  149. #
  150. # A: „Schockierend. Ich weiß.“
  151. #
  152.  
  153. #
  154. # F: „Mooment! Wieso gibt es dann umso mehr Punkte für den Hamster, je
  155. # häufiger die Schlange gefüttert wird?“
  156. #
  157. # A: „*seufz* OK, das war vorhin doch nicht die ganze Wahrheit über das
  158. # Spiel; in wirklicher Wirklichkeit gibt es die Punkte für die
  159. # heimliche, weil illegale, Entsorgung der ganzen veganen
  160. # Biodinkelriegel, die der Hamster versehentlich gehortet hat und
  161. # die er nun an die Schlange verfüttert.“
  162. #
  163. # Jetzt aber weiter im Quelltext:
  164. #
  165.  
  166. def umsetzen(self):
  167. """Setzt den Hamster auf ein zufälliges Feld, das noch nicht von
  168. der Schlange belegt ist."""
  169.  
  170. # Liste der freien Koordinaten, die mindestens 2 Felder vom Rand
  171. # entfernt sind (der Hamster soll nicht am Rand oder in einer
  172. # Ecke hocken):
  173. Frei = [(x, y) for x in range(3, 28) for y in range(3, 28)
  174. if (x, y) not in Schlange.Felder]
  175.  
  176. for Versuch in range(100, 0, -1):
  177. # irgendein freies Feld auswürfeln
  178. self.xy = choice(Frei)
  179. # gewünschter Abstand
  180. Abstand = Versuch//10 + 1
  181. # Wenn die Schlange zu dicht ist, ist das Feld tabu
  182. Tabu = False
  183.  
  184. # Nachbarschaft scannen
  185. for x in range(self.xy[0]-Abstand, self.xy[0]+Abstand+1):
  186. for y in range(self.xy[1]-Abstand, self.xy[1]+Abstand+1):
  187. if (x,y) in Schlange.Felder:
  188. Tabu = True
  189. break
  190. if Tabu: break
  191.  
  192. if not Tabu:
  193. # Freies Feld gefunden. Schleife abbrechen!
  194. break
  195.  
  196. # Das Hamsterbild auf die neue Canvas-Position verschieben:
  197. x, y = self.xy
  198. C.coords(Hamster.bild_ID, 24*x, 24*y)
  199.  
  200. # Titelzeile des Fensters aktualisieren
  201. if Schlange.benutzeAutopilot:
  202. s = Algorithmusname+" sucht den"
  203. else:
  204. s = "Füttere den Python mit dem"
  205. T.title(s+" %i. Java-Hamster!" %
  206. (self.zähler+1))
  207.  
  208. def verstecken(self):
  209. "Setzt den Hamster auf eine nicht sichtbare Koordinate"
  210. C.coords(Hamster.bild_ID, -100, -100)
  211.  
  212.  
  213. def Highscore(Grund, Punkte):
  214. "Zeigt den Highscore-Dialog an"
  215.  
  216. # Mauszeiger für die Canvas wieder einschalten
  217. C.config(cursor="arrow")
  218.  
  219. # Kennen wir uns?
  220.  
  221. try:
  222. un = ", "+Hamster.username
  223. # nö.
  224. except AttributeError:
  225. un = ""
  226.  
  227. # Wie laut müssen wir jubeln?
  228.  
  229. if Punkte > Hamster.highscore:
  230. # Konfetti, Sekt, Fanfaren!
  231. Jubel = "Bravo"+un+", das ist Deine neue persönliche "
  232. "Bestleistung!"
  233. # Das wird der neue Highscore
  234. Hamster.highscore = Punkte
  235.  
  236. elif Punkte:
  237. # Schlechter geworden?
  238. Jubel = "Beim nächsten Mal schaffst Du wieder mehr"+un+"!"
  239.  
  240. else:
  241. # 0 Punkte? Sei trotzdem nett zu dem N00b:
  242. Jubel = "Tipp: Steuere den Python mit den Pfeiltasten!"
  243.  
  244. # Bei menschlichen Spielern Dialog anzeigen, bei Autopilot
  245. # nur protokollieren.
  246. if Schlange.benutzeAutopilot:
  247. # Datum und Uhrzeit für die Logdatei
  248. jetzt = strftime("%F %T")
  249. # Jedes einzelne Ergebnis wird in der großen Logdatei protokolliert
  250. with open(Algorithmusname+".log","a") as log:
  251. print(jetzt,Punkte,sep="t",file=log)
  252. # Neuer Highscore?
  253. if Hamster.highscore == Punkte:
  254. # Kleine Logdatei nur für neue Highscores
  255. with open(Algorithmusname+"_highscore.log","a") as log:
  256. print(jetzt,Punkte,sep="t",file=log)
  257. # Canvas als Bilddatei speichern
  258. C.postscript(file=Algorithmusname+strftime(" %F %T ")
  259. +str(Punkte)+".eps",
  260. colormode='color')
  261. # Highscore auf der Website eintragen
  262. showpage(url+"?"+urlencode((("n", Algorithmusname),
  263. ("p", Punkte),
  264. ("b", 1))))
  265. T.title("Algorithmus ""+Algorithmusname+
  266. "" wird fortgesetzt.")
  267. countdown()
  268. elif askyesno(Grund, "Du hast %i Hamsterpunkte!nn%s" % (Punkte, Jubel) +
  269. "nnMöchtest Du Dich in die Highscoreliste eintragen?"):
  270. # Highscore auf der Website eintragen
  271. if Schlange.AutopilotWurdeVerwendet:
  272. showinfo(title="Problem",
  273. message="Du hast den Autopiloten verwendet",
  274. detail="Einträge in die Highscoreliste sind nur möglich, "
  275. "wenn die Schlange während der ganzen Runde von Hand "
  276. "gesteuert wurde.")
  277. else:
  278. showpage(url+"?"+urlencode((("n", username()),
  279. ("p", Punkte))))
  280. T.title("Neustart mit der Eingabetaste!")
  281. else:
  282. T.title("Mache Dich bereit!")
  283. sleep(1)
  284. countdown()
  285.  
  286. class C_Schlange:
  287. """Die Schlange merkt sich die durch sie belegten Felder und deren
  288. Canvas-Objekte sowie die letzte Hamstermahlzeit."""
  289.  
  290. def __init__(self):
  291. "Die Schlange schlüpft."
  292. # Sie bewegt sich noch nicht vom Fleck.
  293. self.dx = self.dy = 0
  294. self.benutzeAutopilot = False
  295. self.Turbo = False
  296. self.reset()
  297.  
  298. def reset(self):
  299. "Startwerte der Schlange werden gesetzt."
  300. # Zufällige Startpostition 10 Felder vom Rand entfernt
  301. self.x = randint(10, 20)
  302. self.y = randint(10, 20)
  303. # Zufällige Richtung: nach rechts, links, oben oder unten.
  304. # Setzt dx und dy entsprechend auf -1, 0 oder +1.
  305. self.Richtung(choice("rlou"))
  306. # Die Elemente der Liste "Felder" bestehen aus (x,y)-Tupeln.
  307. # Der Kopf der Schlange ist auf (self.x, self.y).
  308. self.Felder = [(self.x, self.y)]
  309. # Fünf Rumpfsegmente entgegen der Bewegungsrichtung anhängen:
  310. for i in range(1, 6):
  311. self.Felder.append((self.x-i*self.dx, self.y-i*self.dy))
  312. # Wartezeit zwischen zwei Schritten: anfangs 100 Millisekunden,
  313. # später wird die Schlange immer schneller.
  314. self.ms = 100
  315. # Die Schlange braucht 5 Schritte, um eine Mahlzeit zu verdauen und
  316. # dabei zu wachsen. Jetzt ist der Magen gerade leer.
  317. self.Mageninhalt = 0
  318. # Falls pro Bewegungsschritt mehrere Tasten gedrückt werden,
  319. # kommen die in einen Puffer, sodass pro Schritt nur eine
  320. # Richtungsänderung vorgenommen wird.
  321. self.Tastenpuffer = []
  322. # Highscoreeinträge der Kategorie "menschlicher Spieler" sollen
  323. # nur möglich sein, wenn zwischendurch nicht nachgeholfen wurde.
  324. self.AutopilotWurdeVerwendet = self.benutzeAutopilot
  325.  
  326. def Richtung(self, rlou):
  327. "Setzt den Delta-x- bzw. -y-Wert für die nächsten Bewegungsschritte"
  328. # Unmittelbar tödliche 180°-Kehren werden nicht zugelassen
  329. if rlou == "l":
  330. if not self.dx:
  331. self.dx = -1
  332. elif rlou == "r":
  333. if not self.dx:
  334. self.dx = 1
  335. else:
  336. self.dx = 0
  337. if rlou == "u":
  338. if not self.dy:
  339. self.dy = 1
  340. elif rlou == "o":
  341. if not self.dy:
  342. self.dy = -1
  343. else:
  344. self.dy = 0
  345.  
  346. def Taste(self, key):
  347. "Hängt einen Tastendruck an den Eingabepuffer an."
  348. self.Tastenpuffer.append(key)
  349. if self.benutzeAutopilot:
  350. T.title("Autopilot ausgeschaltet! Manuelle Steuerung aktiv.")
  351. self.benutzeAutopilot = False
  352. self.Turbo = False
  353.  
  354. def zeichneKopf(self):
  355. "Setzt den Kopf in richtiger Orientierung auf sein neues Feld."
  356. x, y = self.Felder[0]
  357. # Trapezförmigen Kopf je nach Bewegungsrichtung drehen:
  358. C.coords(self.Kopf,
  359. 24*x-10-2*self.dy, 24*y-10-2*self.dx,
  360. 24*x+10+2*self.dy, 24*y-10+2*self.dx,
  361. 24*x+10-2*self.dy, 24*y+10-2*self.dx,
  362. 24*x-10+2*self.dy, 24*y+10+2*self.dx)
  363. # Augenlinie (gestrichelt) von links nach rechts:
  364. C.coords(self.Augen,
  365. 24*x-2*self.dx-10*self.dy, 24*y-2*self.dy-10*self.dx,
  366. 24*x-2*self.dx+10*self.dy, 24*y-2*self.dy+10*self.dx)
  367.  
  368. def Start(self, event=None):
  369. "Setzt den Hamster um und baut die Schlange neu auf"
  370. # Die tatsächlichen Koordinaten einiger Elemente werden
  371. # erst bei Bewegung der Schlange gesetzt. Sie werden außerhalb
  372. # der Canvas zwischengelagert.
  373. außerhalb = -99, -99, -99, -99
  374. # Schlange zeichnen: zuunterst liegt eine dicke blaue Linie.
  375. # Gleich kommt noch eine zweite Linie hinzu, für sie ist hier der
  376. # Platzhalter "None".
  377. self.Körper = [C.create_line(self.Felder,
  378. fill="blue", smooth=1, tag="Schlange",
  379. joinstyle="round", capstyle="round",
  380. width=24),
  381. None]
  382.  
  383. # Der Kopf der Schlange wird ein Trapez, dessen kurze Seite stets in
  384. # Bewegungsrichtung zeigen wird.
  385. self.Kopf = C.create_polygon(außerhalb, width=4, fill="yellow",
  386. outline="blue", joinstyle="bevel",
  387. tag="Schlange")
  388.  
  389. # Auflösung des None-Rätsels von oben: Die gelbe Füllung des Körpers
  390. # liegt in der Zeichenreihefolge über dem Kopf, damit die "Nackenlinie"
  391. # nicht zu sehen ist. Beide Körperlinien werden in einer Liste
  392. # gespeichert, damit sie mittels einer Schleife modifiziert werden
  393. # können.
  394. self.Körper[1] = C.create_line(self.Felder,
  395. fill="yellow", smooth=1, tag="Schlange",
  396. joinstyle="round", capstyle="round",
  397. width=16, dash=(1,15))
  398.  
  399. # Die Strichelung der gelben Körperlinie kann dazu führen, dass
  400. # ein großes Stück des Schwanzes blau bleibt. Hier tupfen wir ein
  401. # wenig Make-Up in Form einer Kreisscheibe nach.
  402. self.Schwanzspitze = C.create_oval(außerhalb, fill="yellow",
  403. outline="yellow", tag="Schlange")
  404.  
  405. # Die Augen liegen zuoberst und bestehen aus einer einzigen
  406. # geschickt gestrichelten Linie: "* *".
  407. self.Augen = C.create_line(außerhalb, width=8, fill="black",
  408. tag="Schlange", capstyle="round",
  409. dash=(5,11,5))
  410.  
  411. # Hamster umsetzen
  412. # (In Wahrheit wird der nämlich gar nicht gefressen, sondern immer
  413. # rechtzeitig weggebeamt. Die arme Schlange erhält stattdessen
  414. # einen veganen Biodinkelriegel.)
  415. # (Ja, sowas erfährt man nur, wenn man Quelltextkommentare liest.)
  416. Hamster.umsetzen()
  417. # Go!
  418. C.after(self.ms, self.Bewege)
  419.  
  420. def Stirb(self, innenFarbe, außenFarbe):
  421. "Animation zeigt durch Farbveränderung das Ende der Spielrunde an."
  422. # Die Schlange verändert innerhalb einer Sekunde ihre
  423. # Farbe vom Kopf bis zur Schwanzspitze. Der nach jedem Abschnitt
  424. # erfolgende Aufruf von „update_idletasks“ sorgt dafür, dass die
  425. # Änderung sofort angezeigt wird und nicht erst, wenn das Programm
  426. # wieder in der Mainloop ist.
  427.  
  428. # Im Turbomodus entfällt diese hübsche Animation.
  429. if self.Turbo:
  430. return
  431.  
  432. # Kopf heben und Augen weit aufreißen!
  433. C.tag_raise(self.Kopf)
  434. C.tag_raise(self.Augen)
  435. C.itemconfig(self.Augen, width=20)
  436. C.update_idletasks()
  437. sleep(0.1)
  438.  
  439. # Augenfarbe ändern
  440. C.itemconfig(self.Augen, fill=außenFarbe)
  441. C.update_idletasks()
  442. sleep(0.1)
  443.  
  444. # Kopfinneres umfärben
  445. C.itemconfig(self.Kopf, fill=innenFarbe)
  446. C.update_idletasks()
  447. sleep(0.1)
  448.  
  449. # Kopfrand umfärben
  450. C.itemconfig(self.Kopf, outline=außenFarbe)
  451. C.update_idletasks()
  452. sleep(0.1)
  453.  
  454. # Körperinneres umfärben
  455. C.itemconfig(self.Körper[1], fill=innenFarbe)
  456. C.itemconfig(self.Schwanzspitze, fill=innenFarbe, outline=innenFarbe)
  457. C.update_idletasks()
  458. sleep(0.1)
  459.  
  460. # Augen schließen …
  461. C.itemconfig(self.Körper[0], fill=außenFarbe)
  462. for i in range(20,1,-1):
  463. C.itemconfig(self.Augen, width=i)
  464. C.update_idletasks()
  465. sleep(0.02)
  466.  
  467. # R.I.P.
  468. pass
  469.  
  470.  
  471. def starteAutopilot(self):
  472. "Die Steuerung der Schlange wird von einem Algorithmus übernommen."
  473. self.benutzeAutopilot = True
  474. self.AutopilotWurdeVerwendet = True
  475. self.Turbo = False
  476. T.title("Autopilot aktiviert. "
  477. "Algorithmus "%s" arbeitet." % Algorithmusname)
  478.  
  479. def starteTurbo(self):
  480. "Alle bremsenden Warteschleifen und Animationen deaktivieren"
  481. if self.benutzeAutopilot:
  482. self.Turbo = True
  483. T.title("Turbomodus aktiviert! Ende mit Pos1 oder Cursortasten")
  484.  
  485. def Autopilot(self):
  486. "Setzt self.dx und self.dy auf Basis eines Algorithmus."
  487. # Algorithmus: "Große Welle 5"
  488. #
  489. # Strategie: Kürzesten Weg zum Hamster markieren, Inseln vermeiden
  490. #
  491. # Ausgehend vom Hamsterfeld werden wellenförmig Ringe aus den im
  492. # jeweils nächsten Schritt erreichbaren Feldern gebaut.
  493. # In die Felder wird die Anzahl der Schritte bis zum Hamster
  494. # eingetragen. Die Schlange muss nun nur noch in Richtung des Feldes
  495. # mit der niedrigsten Nummer gleiten.
  496. #
  497. # 1. Matrix in Spielfeldgröße (29×29) anlegen, mit dem Wert 999 füllen.
  498. # Schlangenfelder erhalten den Wert 1000+s, wobei s die Entfernung
  499. # zum Kopf in Schlangensegmenten ist.
  500. # Das Hamsterfeld erhält den Wert 0.
  501. # Ringsum wird noch ein Rand mit Wert 9999 angeordnet, dadurch
  502. # vermeiden wir Indexfehler beim Untersuchen der Nachbarfelder.
  503. # 2. Vom Hamsterfeld beginnend erhalten alle noch nicht bewerteten
  504. # Nachbarfelder, die kein Schlangenfeld sind, den Wert n+1, wobei n
  505. # die Entfernung des aktuellen Feldes zum Hamster ist.
  506. # 3. Schritt 2 wird für alle gefundenen Nachbarfelder wiederholt.
  507. # 4. Sobald die "Welle" den Schlangenkopf erreicht, ist der kürzeste
  508. # Pfad gefunden.
  509. # 5. Die Schlange bewegt sich nun immer in Richtung des Feldes mit dem
  510. # geringsten Wert. Falls die Möglichkeit besteht, durch
  511. # Richtungswechsel zu einem gleichwertigen Feld am eigenen Körper
  512. # entlang zu gleiten, wird das zur Vermeidung von Inseln ausgeführt.
  513. # Stehen mehrere dieser Felder zur Auswahl, wird das mit den
  514. # wenigsten Segmenten vom Schwanz entfernte Schlangensegment
  515. # bevorzugt.
  516. #
  517. # Zu verbessern: Selbstmord durch Kurzsichtigkeit vermeiden!
  518. #
  519. # Es fehlt derzeit jede Rückzugstrategie. Die Schlange gleitet
  520. # gnadenlos in Sackgassen und verbaut sich selbst den Rückweg.
  521. # Die maximale Punktzahl dieser Strategie liegt bei etwa 450_000.
  522. #
  523. # So könnte eine optimale Lösung aussehen:
  524. # The Perfect Snake
  525. # Mike James, 2013
  526. # http://www.i-programmer.info/news/144-graphics-and-games/
  527. # 5754-the-perfect-snake.html
  528. #
  529. # Etwas simpler:
  530. # https://www.youtube.com/watch?v=kTIPpbIbkos
  531. #
  532. # Sterbenslangweilig, aber deprimierend erfolgreich:
  533. # http://www.datagenetics.com/blog/april42013/
  534. #
  535. # Literatur:
  536. # Snake: Artificial Intelligence Controller
  537. # Patrick Merrill, 2011
  538. # http://www.cs.unh.edu/~ruml/cs730/paper-examples/merrill-2011.pdf
  539. # Gaming is a hard job, but someone has to do it!
  540. # Giovanni Viglietta, 2013
  541. # https://arxiv.org/abs/1201.4995
  542. # A Knowledge-based Approach of Connect-Four
  543. # The Game is Solved: White Wins
  544. # Victor Allis, 1988
  545. # http://www.informatik.uni-trier.de/~fernau/DSL0607/
  546. # Masterthesis-Viergewinnt.pdf
  547.  
  548. # Die Bewertungsmatrix
  549. self.A = [[999 for i in range(31)] for i in range(31)]
  550.  
  551. # Randfelder
  552. for i in range(31):
  553. self.A[0][i] = 9999
  554. self.A[30][i] = 9999
  555. self.A[i][0] = 9999
  556. self.A[i][30] = 9999
  557.  
  558. # Startfeld
  559. xh, yh = Hamster.xy
  560. self.A[xh][yh] = 0
  561.  
  562. # Die Segmente der Schlange, die vom Kopf nicht erreicht werden
  563. # können, müssen nicht eingetragen werden.
  564.  
  565. # Kopfposition der Schlange
  566. xs, ys = self.Felder[0]
  567. # Alle Felder untersuchen
  568. for n, Feld in enumerate(self.Felder):
  569. x, y = Feld
  570. # Wenn der Kopf dieses Körpersegment in n Schritten
  571. # erreichen kann (unter der äußerst vereinfachenden Annahme,
  572. # dass der Weg dorthin frei sei):
  573. if abs(x-xs)+abs(y-ys) <= n + self.Mageninhalt:
  574. self.A[x][y] = 1000 + n
  575.  
  576. # Die Liste "Aktuell" wird in jedem Schleifendurchlauf auf
  577. # neu zu untersuchende Nachbarn hin ausgewertet.
  578. # Diese landen zunächst in der Liste "Neu".
  579. Neu = [(xh,yh)]
  580.  
  581. # Strecke bis zum Hamsterfeld
  582. n = 0
  583.  
  584. # Wenn ein Pfad vom Schlangenkopf zum Hamster gefunden wurde,
  585. # ist der Suchalgorithmus fertig.
  586. fertig = False
  587. while not fertig:
  588. # Ein Schritt mehr zum Hamster
  589. n += 1
  590. # Die neue hinzugekommenen Felder aus dem letzten Durchlauf
  591. # werden zu den aktuell zu untersuchenden Feldern.
  592. Aktuell = Neu[:]
  593. # Die Liste "Neu" sammelt die Kandidaten für den nächsten
  594. # Schleifendurchlauf.
  595. Neu = []
  596. # Für alle Felder, die in diesem Durchlauf dran sind:
  597. for Ak in Aktuell:
  598. # Alle vier Nachbarfelder durchgehen:
  599. for x, y in ((Ak[0]-1,Ak[1]),(Ak[0]+1,Ak[1]),
  600. (Ak[0],Ak[1]-1),(Ak[0],Ak[1]+1)):
  601. # Ein freies Feld?
  602. if self.A[x][y] == 999:
  603. # Schrittzahl zum Hamster eintragen
  604. self.A[x][y] = n
  605. # Feld für den nächsten Durchlauf merken
  606. Neu.append((x,y))
  607. # Ein Schlangenfeld?
  608. elif 9999 > self.A[x][y] >= 1000:
  609. # Der Kopf?
  610. if (x, y) == (xs, ys):
  611. # Der Pfad vom Kopf zum Hamster ist gefunden!
  612. fertig = True
  613. break
  614. if fertig:
  615. break
  616. # Wenn keine leeren Felder mehr erreichbar sind:
  617. if not Neu:
  618. # Suche ist abgeschlossen.
  619. fertig = True
  620.  
  621. # "Impulserhaltung": die Schlange behält zunächst einmal ihre
  622. # Richtung bei.
  623. Zielwert = self.A[self.x+self.dx][self.y+self.dy]
  624. # Falls jedoch eines der in zufälliger Reihenfolge untersuchten
  625. # Nachbarfelder attraktiver ist oder gleichwertig, aber dem
  626. # schwanznächsten Schlangensegment benachbart ist …
  627. snSS = 1000
  628. for x, y in sample(((self.x-1, self.y),
  629. (self.x+1, self.y),
  630. (self.x, self.y-1),
  631. (self.x, self.y+1)),4):
  632. # … weil es eine Abkürzung ist oder weil die Möglichkeit
  633. # besteht, am eigenen Körper entlangzugleiten und so Hohlräume
  634. # zu vermeiden …
  635. if self.A[x][y] < Zielwert or
  636. self.A[x][y] == Zielwert and
  637. 9999 > self.A[x-self.dx][y-self.dy] >= snSS:
  638. # … dann wenden wir uns dem zu.
  639. Zielwert = self.A[x][y]
  640. self.dx = x-self.x
  641. self.dy = y-self.y
  642. # War das Nachbarfeld ein attraktiveres Schlangensegment?
  643. if 9999 > self.A[x-self.dx][y-self.dy] > snSS:
  644. snSS = self.A[x-self.dx][y-self.dy]
  645.  
  646. def Bewege(self):
  647. "Alle paar Millisekunden bewegt sich die Schlange ein Feld weiter"
  648. # Wurden zwischendurch eine oder mehrere Cursortasten gedrückt?
  649. if self.Tastenpuffer:
  650. # Hole den ältesten Tastendruck ab,
  651. # setze dx und dy entsprechend.
  652. self.Richtung(self.Tastenpuffer.pop(0))
  653.  
  654. if self.benutzeAutopilot:
  655. # Lasse dx, dy automatisch setzen.
  656. self.Autopilot()
  657.  
  658. # Neue Kopfposition: Nächstes Feld in Bewegungsrichtung
  659. self.x += self.dx
  660. self.y += self.dy
  661.  
  662. # Ist da der Hamster?
  663. if (self.x, self.y) == Hamster.xy:
  664. # Punktzahl erhöhen.
  665. # Ja, der Hamster bekommt die Punkte!
  666. # Wer sagt, das Leben sei fair?
  667.  
  668. # Zahl der Hamster (-umsetzungen …)
  669. Hamster.zähler += 1
  670.  
  671. # Die zu addierende Punktzahl erhöht sich pro Hamster um 100.
  672. Hamster.punkte += 100 * Hamster.zähler
  673.  
  674. # Ein Hamster verlängert die Schlange um 5 Felder.
  675. self.Mageninhalt = 5
  676.  
  677. # Die Schlange wird 5% schneller.
  678. self.ms = int(0.95*self.ms)
  679.  
  680. # Die nächste Mahlzeit materialisiert sich irgendwo.
  681. Hamster.umsetzen()
  682.  
  683. # Spielfeldende erreicht?
  684. if self.x < 1 or self.x > 29 or self.y < 1 or self.y > 29:
  685. # Farbveränderung
  686. self.Stirb("black", "grey")
  687.  
  688. # Auswertungsdialog
  689. Highscore("Der Python ist vor die Wand geprallt.", Hamster.punkte)
  690. # DER Python! Meine Güte, schau' in den Duden!
  691.  
  692. # Schlange und Hamster zurücksetzen
  693. self.reset()
  694. Hamster.reset()
  695. return
  696.  
  697. # Ist noch etwas vom letzten Hamster übrig?
  698. if self.Mageninhalt:
  699. # bisschen verdauen
  700. self.Mageninhalt -= 1
  701. # Die Schlange wächst nun. Weil gleich das letzte
  702. # Feld abgeschnitten wird, hängen wir ein Dummy-Feld an.
  703. self.Felder.append(self.Felder[-1])
  704.  
  705. # Am Kopf ein neues Feld anfügen, Schwanzfeld entfernen.
  706. # Das Polygon wird als Trapez gezeichnet, dessen kurze Seite
  707. # in Bewegungsrichtung "schaut".
  708. self.Felder = [(self.x, self.y)] + self.Felder[:-1]
  709. self.zeichneKopf()
  710.  
  711. # Die Schlange gleitet weiter. Die Schleife ist nötig, weil
  712. # der gelbe Schlangenkörper und der blaue Rand zwei eigene
  713. # Canvas-Objekte mit denselben Koordinaten sind.
  714. for K in self.Körper:
  715. C.coords(K, [xy*24 for Feld in self.Felder for xy in Feld])
  716. # Was da gerade zwischen den eckigen Klammern geschah:
  717. # Das Tupel "Feld" nahm nacheinander alle Werte der Tupel in
  718. # "self.Felder" an und jedesmal wurde die Variable "xy"
  719. # nacheinander auf den x- und den y-Wert dieses Tupels gesetzt,
  720. # mit 24 multipliziert und an eine Liste angehängt. Mit dieser
  721. # Liste von Koordinaten [x0, y0, x1, y1, … xn, yn] wurden dann
  722. # die beiden dicken Linien des Schlangenkörpers modifiziert.
  723.  
  724. # Der gelbe Make-Up-Punkt für die Schwanzspitze:
  725. x, y = self.Felder[-1]
  726. C.coords(self.Schwanzspitze, x*24-7, y*24-7, x*24+7, y*24+7)
  727.  
  728. # Ist gerade etwas furchtbar dummes passiert?
  729. if self.Felder[0] in self.Felder[1:]:
  730. # Wenn an der neuen Kopfposition schon ein Schlangensegment ist,
  731. # dann ist die Runde ist zu Ende, weil die Schlange sich selbst
  732. # gebissen hat.
  733.  
  734. # Farbveränderung
  735. self.Stirb("red", "darkred")
  736.  
  737. # Auswertungsdialog
  738. Highscore("Der Python hat sich selbst gebissen.",
  739. Hamster.punkte)
  740.  
  741. # Schlange und Hamster zurücksetzen
  742. self.reset()
  743. Hamster.reset()
  744. return
  745.  
  746. # Punkteabzug wegen Trödelns:
  747. if Hamster.punkte:
  748. Hamster.punkte -= 1
  749.  
  750. # Anzeige der Punktzahl aktualisieren
  751. C.itemconfig(C.zähler, text="%05i" % Hamster.punkte)
  752.  
  753. # I'll be back
  754. if not self.Turbo:
  755. C.update_idletasks()
  756. C.after(self.ms, self.Bewege)
  757. else:
  758. C.after_idle(self.Bewege)
  759.  
  760. # Programmfenster
  761. T = Tk()
  762. T.title("Python-Hamster: Steuerung mit Pfeiltasten")
  763.  
  764. # Leinwand
  765. C = Canvas(width=720, height=720, bg="#e0ffe0", highlightthickness=0)
  766. C.pack()
  767.  
  768. # Spielfeldrand
  769. C.create_rectangle(6, 6, 714, 714, width=12, outline="#703030")
  770.  
  771. # Fugen im Spielfeldrand
  772. for a in range(61):
  773. for b, c in ((-1, "#501000"), (0, "#905030")):
  774. C.create_line(b+a*12, 0, b+a*12, 719, fill=c)
  775. C.create_line(0, b+a*12, 719, b+a*12, fill=c)
  776.  
  777. # Bodenkacheln
  778. for x in range(29):
  779. for y in range(29):
  780. # Der Rot- und Blauanteil der Kachelfarbe ist veränderlich,
  781. # jedoch pro Kachel gleich.
  782. # Der Grünanteil hat immer den Wert 255.
  783. rb = "%02x" % randint(210, 230)
  784. farbe = "#"+rb+"ff"+rb
  785. C.create_rectangle(24*x+12, 24*y+12,
  786. 24*x+35, 24*y+35,
  787. fill=farbe, outline=farbe)
  788.  
  789. # Punktezähler
  790. C.zähler = C.create_text(360, 360,
  791. text="00000",
  792. font="courier 96 bold",
  793. fill="#d0efd0")
  794.  
  795. # Der Hamster ist ein Objekt der Klasse C_Hamster
  796. Hamster = C_Hamster()
  797.  
  798. # Die Schlange ist ein Objekt der Klasse C_Schlange
  799. Schlange = C_Schlange()
  800. T.bind("<Return>", countdown)
  801.  
  802. # Pfeiltasten an zugehörige Funktionen binden
  803. T.bind("<Left>", lambda event: Schlange.Taste("l")) # ←
  804. T.bind("<Right>", lambda event: Schlange.Taste("r")) # →
  805. T.bind("<Up>", lambda event: Schlange.Taste("o")) # ↑
  806. T.bind("<Down>", lambda event: Schlange.Taste("u")) # ↓
  807. T.bind("<Home>", lambda event: Schlange.starteAutopilot()) # Pos1
  808. T.bind("<End>", lambda event: Schlange.starteTurbo()) # Ende
  809.  
  810. # Los geht’s
  811. countdown()
  812.  
  813. T.mainloop()

--
Dipl.-Ing. Martin Vogel
Leiter des Bauforums

Bücher:
CAD mit BricsCAD
Bauinformatik mit Python

Tags:
Python, Grafik, Spiel


gesamter Thread:

 RSS-Feed dieser Diskussion

powered by my little forum