Das deutsche Python-Forum

Im Rahmen meines Snake-Programmes möchte ich nun eine kleine KI basteln. Habe mir also für das Pfad finden den A* Algorithmus ausgeguckt. Nun habe ich, musste ja so kommen, einige Performance Probleme. Funktionieren tut es einwandfrei nur dauert es ewig wenn ein Bildschirmpixel eine Position einnimmt.
Die Diagonalen konnte ich ja bei Snake schon aussparen, dennoch werde ich ein größeres Raster für die KI brauchen.

Meine eigentliche Frage wäre, wie könnte ich am besten von meinem Node-Objekt wegkommen, denn es werden logischer Weise zu viele Objekte angelegt. Wenn ich das also wegstreichen wäre es auf jedenfall um einiges schneller.
Aber wenn ich es durch ein "tuple" ersetze kann ich nicht die Referenz auf das vorherige "tuple" halten und damit wäre der Algorithmus ziemlich Sinnfrei. Wie könnte ich das noch machen?, ich sitze irgendwie auf dem Schlauch.

Script: https://github.com/xynon/snake/blob/master/source/ai.py

Geht es dir um's reine Speichersparen? Dann gibt's slots. Oder gleich dicts/listen, denn die sind mutable, und du koenntes damit deine Verkettung machen.

Ist mir bekannt, aber nein der Speicher ist kein Problem. Es dauert einfach zulange soviele Objekte zu erstellen. Was das Spiel stocken bzw. stehen lässt.

Ich werde die Sache noch mal als Liste angehen und sehen ob es eflüssiger läuft als so.

Also, ich habe jetzt dein Programm nicht wirklich betrachtet, aber rein von der Theorie her wuerde ich versuchen, die "Aufloesung" zu reduzieren. Ein paar Dinge, die mir da so aus dem Kopf einfallen:

- anderes Rastermass, statt pixel zb 8x8 [edit: damit meine ich, jedes 8te Pixel...], wird der Nutzer kaum merken, aber reduziert die Komplexitaet um den Faktor 64
- die Modellierung des freien Raumes kann viel, viel groeber sein, du musst nur Knoten in hoeherer Dichte um die Hindernisse plazieren - je nach deren Form nur an den Eckpunkten
- die Datenstruktur einmal aufbauen, aber die Hindernisse dynamisch "raushauen"
- Vornoi-Diagramme. Helfen bestimmt

Ich hab vor Urzeiten mal ne Robotik-Sicht-Modellierungs-Vorlesung gehoert, und Vornoi-Diagramme kamen darin vor, darum fuehlt sich das so an, als ob's helfen koennte ... ist aber 98% Bauch.
- auf "Sicht" fahren, und nur ein sehr grobes Raster ueber das Level legen, das sozusagen garantiert guenstige Eintrittspunkte fuer eine Suche um ein Hindernis bereitstellt. Das koennten dann zB die Vornoi-Diagramm-Schnittpunkte sein. Wenn also der Gegner die Schlange nicht sieht, weil sie verdeckt ist, dann versucht er den naechsten "Stuetzpunkt" bei ihrem Kopf aufzusuchen.

1. War mir schon klar, das ich da nicht drum rum komme.
2. Ist auch klar.
3. So weit bin ich noch nicht, werde da aber Aufgrund der sich bewegenden Schlangen auch nicht drum rumkommen. Hierzu hatte ich eigentlich geplant das erstmal der optimale Weg ermittelt wird und wenn dann eine bevorstehende Kollision kommt, ich dann eine erneute Berechnung durchführen lasse. Es muss schließlich keine Super-KI werden.
4. Vornoi-Diagramme, kenn ich noch nicht, werde ich mir aber mal ansehen.
5. Werde ich auch machen um Fressen zu orten

. Hatte mir zusätzlich etwas in der Art vorgestellt - Schlange fährt rum und wenn sie in einem kleinen Kreisausschnitt etwas auftaucht ist das ihr nächster Zielort. Allerdings gibt es bei der Sache zwei kleine Schwierigkeiten, 1. Wäre es so gegen einen menschlichen Spieler nicht so praktisch das die Schlange wohl kaum Beute macht und 2. das ist Momentan noch Zukunftsmusik. Erstmal möchte ich eine funktionierende mir Konkurierende Schlange haben

Edit: Mit Listen-Verschachtlung ist es wesentlich schneller, noch nicht schnell genug für ein flüssiges Spiel, aber mit einem gröberen Raster, sollte das kein Problem werden. Allerdings sieht es durch die Indizies jetzt um einiges unschöner aus.

deets hat geschrieben: - Vornoi-Diagramme. Helfen bestimmt Ich hab vor Urzeiten mal ne Robotik-Sicht-Modellierungs-Vorlesung gehoert, und Vornoi-Diagramme kamen darin vor, darum fuehlt sich das so an, als ob's helfen koennte ... ist aber 98% Bauch.

Ich hatte vor einigen Jahren eine Unterhaltung mit Sebastian Thrun. Er hat den verwendeten Algorithmus für den damals von ihm eingesetzten autonomen Roboter nicht beim Namen genannt, aber im Nachhinein scheint es mir so, als habe er reinrassiges A* beschrieben.

deets hat geschrieben: - auf "Sicht" fahren, und nur ein sehr grobes Raster ueber das Level legen, das sozusagen garantiert guenstige Eintrittspunkte fuer eine Suche um ein Hindernis bereitstellt. Das koennten dann zB die Vornoi-Diagramm-Schnittpunkte sein. Wenn also der Gegner die Schlange nicht sieht, weil sie verdeckt ist, dann versucht er den naechsten "Stuetzpunkt" bei ihrem Kopf aufzusuchen.

Wenn jetzt noch jemand einen Code-Ansatz für Voronoi-Diagramme (und Delauney-Triangulation) hat, dann wäre das prima.

deets hat geschrieben:anderes Rastermass, statt pixel zb 8x8 [edit: damit meine ich, jedes 8te Pixel...], wird der Nutzer kaum merken, aber reduziert die Komplexitaet um den Faktor 64

Also wenn man ganz genau ist, was wir hier natürlich sind

, dann wird nicht die Komplexität verändert sondern nur ein konstanter Faktor.

@/me: Der von Thrun beschriebene Algorithmus, in seiner ursprünglichen Form, ist auch nicht viel mehr als A*. Das komplexe daran ist die Schätzfunktion, welche im Prinzip aus zwei teilen besteht: Eine Planung von Start zum Ziel mit Betrachtung der Hindernisse aber ohne Fahrzeugeigenschaften (non-holonomic with obstacles) und eine Planung unter Vernachlässigung der Hindernisse, daber mit Fahrzeugeigenschaften (holonomic without obstacles). Diese werden dann kombiniert (Maximum) und als Schätzwert verwendet. Es gibt auch Erweiterungen mit D* oder Anytime D*.

EyDu hat geschrieben:Das komplexe daran ist die Schätzfunktion

Yupp, ich habe mir einige angesehen, aber mich letztendlich für die einfachste entschieden. Einfach die Felder in X- und Y- Richtung vom Startfeld bis zum Zielfeld zu zählen. Dabei brauche ich nicht mal einen Faktor, da ich keine Diagonalen habe. Das vereinfacht das ganze sehr, aber ich denke für Snake reicht es.

EyDu hat geschrieben:
deets hat geschrieben:anderes Rastermass, statt pixel zb 8x8 [edit: damit meine ich, jedes 8te Pixel...], wird der Nutzer kaum merken, aber reduziert die Komplexitaet um den Faktor 64
Also wenn man ganz genau ist, was wir hier natürlich sind , dann wird nicht die Komplexität verändert sondern nur ein konstanter Faktor..

Wenn man's genau nimmt, dann habe ich genau das geschrieben. Und konstante Faktoren koennen schon einen immensen Unterschied machen. Die Komplexitaet eines Algorithmus ist schon genauer zu spezifizieren, und hat auch Elemente niedrigerer Ordnung.Dass man sie bei der O-Notation weglaesst hat ja andere Gruende.

Praktisch kann im konkreten Fall der Faktor 64 den Unterschied zwischen "ruckelt" und "ruckelt nicht" machen.

Ich weiß jetzt nicht, wie wirklich aktuelle Spiele das handeln, aber im Echtzeitstrategiespiel Warcarft3, welches auf echter 3D-Grafik basiert, wird intern auch mit einem Raster gearbeitet, welches an die alten Tile-basierten Engines erinnert. Insofern ist die Rasterung durchaus sinnvoll, da man bei Pixel genauen Ergebnissen wohl nicht wirklich zum Ziel kommt.

Was ich mir noch vorstellen könnte, wäre eine "Multi-Layer"-Rasterung. Also je weiter weg ein Gegner ist, umso grober ist das Raster, je näher er kommt, desto feiner macht man es und begrenzt entsprechend den Suchraum.

/me hat geschrieben:Wenn jetzt noch jemand einen Code-Ansatz für Voronoi-Diagramme (und Delauney-Triangulation) hat, dann wäre das prima.

Würde ich auch gerne haben, bzw. hat jemand ein Dokument das die Voronoi-Diagramme Schritt für Schritt erklärt. Das meiste was ich gefunden habe war alles ein sehr schneller Einstieg und dann verliert sich es immer im Detail.

Hyperion hat geschrieben:Insofern ist die Rasterung durchaus sinnvoll

Hat auch niemand das Gegenteil behauptet, ich wollte nur erst das Objekt noch aus dem Code haben und ein wenig optimieren, da sieht man die Verzögerung besser. Im Übrigen ist jetzt ein freiwählbares Raster drin. Könnt ihr euch auf GitHub ansehen, oben steht der Link.

Was die "Multi-Layer"-Rasterung angeht, ist sicher nicht schwer umzusetzen, aber bei Snake denke ich nicht Notwendig. Theoretisch müsste das Raster ja maximal so klein sein wie der Kopf der Schlange, vorrausgsetzt der Kopf ist immer Größer als die Körperteile.
Viel schwieriger stelle ich mir die Kollisionserkennung mit bewegten Objekten vor. Da der Pfad ja statisch erechnet wird. Hat dazu jemand eine Idee?

deets hat geschrieben:die Datenstruktur einmal aufbauen, aber die Hindernisse dynamisch "raushauen"

Hier hatte wir schon damit angefangen, ich hatte auch schon eine mögliche Lösung geschrieben, aber gibt es noch andere Ideen.

Hat keiner eine Idee für die dynamische Erkennung?

Xynon1 hat geschrieben:
/me hat geschrieben:Wenn jetzt noch jemand einen Code-Ansatz für Voronoi-Diagramme (und Delauney-Triangulation) hat, dann wäre das prima.
Würde ich auch gerne haben, bzw. hat jemand ein Dokument das die Voronoi-Diagramme Schritt für Schritt erklärt. Das meiste was ich gefunden habe war alles ein sehr schneller Einstieg und dann verliert sich es immer im Detail.

*push*

@Xynon1:

Na, da wird wohl derzeit niemand eine Lösung parat haben oder keine Lust haben, sich tiefer mit deinem Problem zu beschäftigen. Sowas soll auch schon mal vorkommen...

Bist du die Links auf der PyGame-Website schon alle durchgegangen?

EDIT: Das habe ich jetzt mal oberflächlich getan und bin schnell auf ein englischsprachiges Forum speziell für Spieleprogrammierung unter Python gestoßen: http://www.pyedpypers.org/forum/. Vielleicht kann man dir da ja helfen oder deren Forensuche bringt dich evenutell schon auf den richtigen Weg.

Nein war ich noch nicht, danke. Diese hier http://www-cs-students.stanford.edu/~am ... eprog.html hilft mir schon sehr, allerdings hat diese nichts mit Voronoi-Diagrammen zu tun. Werde mich erstmal um mein Snakespiel (wofür ich diese nicht zwangsläufig brauche) kümmern und mich dann später wieder damit befassen. Meine Interesse haben sie jedenfalls geweckt.

Hier noch ein passender Wikipedia-Artikel (falls du den noch nicht gefunden hast): http://de.wikipedia.org/wiki/Voronoi-Interpolation. Vielleicht willst du auch mal nach der genannten Alternativbezeichnung "Sibson-Interpolation" suchen.

Und noch was zum Code: Bist du sicher, dass du in der ``ai.py`` bei der ``min_node()``-Funktion keine Generator Comprehension verwenden willst? Ich weiß ja nicht, wie groß die Anzahl an Nodes werden kann.

snafu hat geschrieben:Hier noch ein passender Wikipedia-Artikel (falls du den noch nicht gefunden hast): http://de.wikipedia.org/wiki/Voronoi-Interpolation. Vielleicht willst du auch mal nach der genannten Alternativbezeichnung "Sibson-Interpolation" suchen.

Doch hatte ich schon, bringt mir nur nichts, da es auf Voronoi-Diagrammen basiert, die ich ja noch nicht verstanden habe. bzw. nicht wüsste wie man die am besten angeht, der Nutzen ist klar, nur wie werden aus den einzelnen Punkten die Linien berechnet. Klar jetzt könnte ich einfach sagen per euklidische Distanz (habe ich ja schon in ai.distance) und bei zwei Punkten ist das auch kein Problem, aber bei drei und mehr steig ich noch nicht durch. Da findet man zwar immer schöne Bilder und bunte Kreise dazu, rechts und links auch mal ein paar definitionen von Punkten oder Funktionen, dennoch gibt es kaum geschlossenen Verständlichen Text, der einem das näher bringt. Die einzigen Texte die ich gefunden hatte stiegen wiederum voll ins Thema ein, wo man die Grundlagen nur vorne weg als kurze Wiederholung bekommt. Ich glaub nicht mal das es sonderlich schwierig ist, nur irgendwie kapier ich es nicht.

snafu hat geschrieben:Und noch was zum Code: Bist du sicher, dass du in der ``ai.py`` bei der ``min_node()``-Funktion keine Generator Comprehension verwenden willst? Ich weiß ja nicht, wie groß die Anzahl an Nodes werden kann.

Danke, hatte ich übersehen, werde ich ändern. Die maximale Anzahl der Nodes kann man eigentlich leicht ausrechnen.

Code: Alles auswählen

mul(*map(div, SCREEN_SIZE, GRID_SIZE)) - len(snakes)

Gut, len(snakes) wird so jetzt nicht funktionieren, aber bildlich gesprochen. Sind bei der jetzigen Einstellung also maximal 625-1 Nodes.

Das deutsche Python-Forum

Performance Problem

Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem

Re: Performance Problem