Bewegungs-Algorithmen

Chrisel

Cadet 4th Year
Registriert
Sep. 2010
Beiträge
70
Hallo alle zusammen,

Mich interessiert folgendes:
Ein Kreis soll eine KI sein. Sie geht auf ein viereckiges Objekt zu welches ein Hindernis ist zu.
Da diese KI nun per Zufall das Spielfeld absuchen soll schicke ich sie an Kreuzungen per Zufall in eine verfügbare Richtung.
Das klappt soweit eigendlich ganz gut nur mich nervt das meine KI eckig geht. Ich würde gerne das sie einen Bogen der auch menschlich aussieht um die kante des Hindernisses macht um dann geradeaus weiterzugehen.( Ich habe mal einen Bild dazu gemalt ).
Wenn jemand irgendwelche Dokumente/Links/... für mich hätte wäre ich suuuper glücklich:)

Viele Grüße
Chrisel

PS: Zur Erklärung des Bildes:
Schwarzes Viereck=Hindernis
Roter Kreis= KI
Graue Linie= so läuft meine KI
Grüne Linie= ungefähr so soll sie laufen
 

Anhänge

  • BewegungsAlgorithmus.JPG
    BewegungsAlgorithmus.JPG
    8,3 KB · Aufrufe: 244
Lang, lang ist's her. Such mal A*-Algorithmus, damit hab ich mal ein paar Spielefiguren durch ein Labyrinth geschickt. Falls Interesse besteht, irgendwo müsste der Source-Code noch rumliegen.
 
Du musst die Prüfung auf ein Objekt mit schon bei größerer Distanz einstellen, dann muss die Breite berechnet werden und aus Breite und Entfernung kannst du dann einen kleinschrittigen(eckigen) Weg errechnen der beim Ablaufen rund wirkt.

So hätte ich es jedenfalls umgesetzt ;)
 
@Simpson474

Klingt schonmal sehr interessant:) Dauert bei mir noch ein wenig bis ich das alle verstehe:D ...bzw bis ich das umgesetzt habe:D
Aber klingt ziemlich nach dem dijkstra-algorythmus über den ich mal ein kleines Programm geschrieben hab:) Das erleichtert das Verständnis ein wenig.
Danke für deine Idee:)

@Mike Lowrey

Schöne Idee:) Klingt recht einfach aber trotzdem gut. Sowas in der Art habe ich mir auch überlegt aber ich fand es recht schwer umzusetzen da ich mit einer Matrix arbeite und somit die felder die "kurz vor dem Hindernis" bedeuten sich bei mehreren hindernissen überschneiden können. Ich hoffe ich habe das verständlich erzählt:D
Ich teste das mal indem ich die matrix wegnehme und durch einfache abfrage ersetze..
Danke für die Idee:)
 
Der A*-Algorithmus ist absolut nicht ähnlich dem Dijkstra-Algorithmus. Beim Dijkstra-Algo sind alle Informationen (Entfernungen) bekannt, bevor der kürzeste Weg berechnet wird. Der A*-Algorithmus nutzt eine heuristische Funktion und berücksichtigt zudem die bisherigen Kosten, um eine optimale Lösung zu finden. Es ist wichtig, dass die heuristische Funktion niemals überschätzt, denn nur so ist die Lösung auch eine optimale Lösung.
 
Mein Interesse ist auf jedenfall geweckt:)
ich werde mich die tage daran machen den algorithmus zu verstehen und erstmal in einem anderen programm umzusetzen bevor ich ihn ihn mein programm einbinde...
Danke für eure Hilfe:) Wenn es noch neue Ideen gibt immer her damit:)

Viele Grüße
Chrisel
 
Wenn du Interesse an Suchverfahren hast, kann ich dir folgendes Buch empfehlen:

Wissensverabeitung

Hier sind uninformierte und informierte Suchverfahren ausführlich beschrieben. Ist gut angelegtes Geld, wenn du an KI interessiert bist.
 
Öh du kannst direkt bei der Wegfindung Ecken notieren, zwischen denen du dann glätten musst.
 
Der A*-Algorithmus ist absolut nicht ähnlich dem Dijkstra-Algorithmus.
Es ist ein veränderter Dijkstra, Unterscheidet sich im Pseudocode nur an einer Stelle. Er is aber für ein anderen Problem konzipiert. So würde ich es sagen,
 
Die Bézierkurven passen ja perfekt:) da muss ich mir mal viel gedanken machen wie ich das programmieren kann. aber danke!:):) es macht mir großen spaß soetwas auszuprobieren.
Ein glück sieht eine Kurve zweiten Gerades noch nicht so kompiliziert aus:D ab dritten grades würde mein kopf bestimmt lange zeit rauchen bis ich die lösung finde:D
Danke nochmal:)
 
in einer richtigen kurve ums hindernis fahren geht ohnehin nur dann, wenn die sensoren die wand schon er kennen, bevor der kreis davor steht.
 
Denk nicht das man dazu irgend einen Algorithmus auffahren muss.
Auch rund gehen dürfte nicht sinngemäß sein.
Die Frage ist ob die Information hast wann links bzw rechts das object aufhört.
der normale Mensch wird keinen Bogen um ein Object gehen sondern wird auf die Kante zu gehen.
Bézierkurven ist mathematisch auch sicher nicht die einfachste Lösung.

Entscheide dich erst einmal ob due Interpolieren under Approximieren willst und dann such dir einen einfachen Algorithmus aus. Nachdem dein Pfad für das oben erwähnt praktisch nur aus 3 punkten besteht dürfte das kein großes Problem werden.

Wieso hier wer mit der A* Suche kommt ist mir unklar das ist Algorithmus für die Informierte Graphen/Baum Suche. Das ist hier nicht so wirklich von nöten.
 
Das Problem was er hat, ist aber sehr wohl ein Suchproblem. Sein Kreis soll das Spielfeld absuchen und hat für jeden Schritt ja verschiedene Möglichkeiten sich zu bewegen. Daher entsteht also ein Suchbaum und es bietet sich hier einfach A* an, um den Suchbaum so zu traversieren, dass man eine optimale Lösung erhält!
 
Genau.. A* würde quasi automatisch die beste (zur Not auch kurvige) Bahn finden, die zurückgelegt werden müsste um die Hindernisse möglichst effizient zu umgehen.
Schwierig wirds nur bei reel-wertigen Positionen. A* geht ja von diskreten Positionen aus.. oder gibts da was angepasstes? Stell ich mir nicht so leicht vor
 
Der kürzeste Weg ist eine Gerade und keine Kurve.
Daher versteh ich nicht was ihr hier mit Suchalgorithem rumgetan wird.
Wenn er möglichst schnell sein will muss er einen gerade gehen.

Im grunde sollte wenn ein Algorithmus verwendet werden der einen möglichst guten Weg für jeden fall zurück gibt. Wenn ihr da immer nenn Suchbaum erstellst und den durchsuchts werdets alt werden.
 
Du hast glaube ich gar nicht verstanden, worum es beim A*-Algorithmus und generell beim Suchen geht. Der A*-Algo verwendet eine heuristische Funktion und schätzt die Entfernung zum Ziel. Bei A* wirst du sicher nicht alt werden, denn er liefert dir die optimale Lösung und wenn es bei einem Suchproblem eine Lösung gibt, findet er sie auf jeden Fall. Und zwar beweisbar optimal. Hier gibt es definitiv eine Lösung, also klappt auch der Algo! A*-Algo ist eben auch optimal, weil er nicht den kompletten Suchbaum durchlaufen muss. Diesen Suchbaum baut man sich außerdem auch dynamisch auf, es wird halt jedes mal überlegt, welcher Knoten als nächstes expandiert werden soll. So wie du dich äußerst hast du keine Ahnung von KI und auch nicht, was ein Suchproblem ist!

Nenne mal einen besseren Algorithmus.

Ergänzung: Der A*-Algorithmus ist übrigens so ein Algo., der dir für jeden Fall einen möglichst guten Weg zurückliefert ;-)
 
Zuletzt bearbeitet:
Die entscheidende Frage ist halt ob die Welt quasi wie ein Schachbrett (ganzzahlige endlich x/y Koordinaten) behandelt werden darf oder ob die Position des Objekts reelwertig ist.
Falls so eine Schachbrett / Karopapierannahme ok ist, ist A* natürlich perfekt.

BTW: Wenn die Schachbrett-Annahme ok ist kommts auch noch auf die Bewegungsmöglichkeiten an. Nur waagerecht + senkrecht oder auch diagonal?
(Stichwort 4er bzw 8er Zusammenhang)
Bei "nur rechts/links & oben unten" ist die ganze Diskussion nämlich witzlos weil ein schräger Weg genau so lang ist wie ein "Erst ans Hindernis ran und dann drumrum"
Stichwort: Cityblock-Metrik
 
Du wirst es nicht Glauben aber ich hab grad eine Prüfung hinter mir die eine A* Suche inkludierte (höheres Informatik Semester)
A* ist vorallem zum Suchen in Bäumen und Graphen was hier aber nicht gegeben ist.
Wenn du alle möglichen Wege hast kann dir A* den optimalen weg zurück geben.

Und worauf ich die ganze Zeit hinaus will ist das du dir hier das erstellen des Suchbausm sparen kannst und der kürzeste weg die Gerade zur Ecke ist. (Anscheinend wissen wir ja wo die ecke ist)

Denn sonst kannst dein A* sowieso vergessen weils eine informierte Suche ist.
Ich seh an der Beschreibung aber nix was auf einen Informierten Graphen hindeutet und seh hier auch keine heuritsche funktion.

Vielleicht zum Abschluss mein Algorithmus lautet eine Gerade zur Ecke.
Der pimpt deine kurve weg.

PS: Ich hasse es wenn hier eine mit sowas wie A* rumprollen will obwohl das etwas total triviales ist.
Aber wennst dir dann besser geht kann ich dir noch erklären wann eine heuristik zulässig und wann sie Konsistent ist und was das für A* bedeutet, etc etc. Hoch lebe der Keks.
 
Zuletzt bearbeitet:
Also, wenn ich an die autonome mobile Robotik-Vorlesung denke, kann ich mich nur anschliessen, dass Menschen manchmal doch eckiger gehen als man glauben möchte.

Aber besonders wenn es mehrere Objekte gibt sehe ich eine gute Möglichkeit einen Suchalgorithmus wie Dijkstra oder A* anzuwenden, so als kleiner Denkansatz:

- Als Knoten nimmt man die Eckpunkte aller geometrischen Figuren, in dem Beispiel also die vier Eckpunkte des Rechtecks, verschoben um einen kleinen Abstand aus der Figur raus natürlich.
Hierzu fügt man noch seine aktuelle Position und die Zielpunkte hinzu.

- Als Kanten nimmt alle möglichen unterbrechungsfreien Verbindungen zwischen zwei Knoten. Also jede Möglichkeit zwei Knoten so zu verbinden, dass kein Hindernis im Weg ist.

Damit könnte man dann auch durch komplexere Szenen hindurch navigieren, wenn man durch diesen Graph dann seinen Weg mit einem der bekannten Algorithmen plant.
 
Zurück
Oben