Ich weiß nicht, ob ich das richtig verstanden habe, biLo88. Es gibt feste Positionen (Waypoints) in der Spielwelt, und das Objekt kann nur jeweils von Position zu Position zu springen oder sich auf dem kürzesten direkten Weg dorthin begeben (was aufs gleiche hinausläuft). Dann wäre das wohl ein vollständiger Graph, so dass jede Position mit jeder anderen verbunden ist, und man soden kürzesten Weg findet. Aber das ginge dann wohl einfacher ohne Dijkstra. Oder gibt es doch feste Pfade/Kanten?
Oh, ich merke gerade, dass ich mich total Falsch ausgedrückt habe. Es geht eher um die Nachbarn. Ich setze Positionen in der Spielewelt ein. Z.b. (10,10,0) und ein anderer Punkt ist (10,15,0) noch einer (5,5,0) usw. Da gibst also keine Nachbarn (weil es uach noch keine Kollisionen gibt nur das man nicht runterfallen kann. Klippen usw.). Was ich mindestens machen kann, das mein Objekt sich über die Wegpunkte entlang bewegen kann (oder in der Nähe). Naja ein schwieriges Thema für mich denke ich.
Erst mal danke für dieses Video. Ich habe die Basis wissen mit einmaligen ansehen verstanden, aber dennoch habe ich eine Frage dazu. Wie ist das, wenn man die Vorgänger gar nicht kennt. Ich arbeite mit Waypoints in einem Spiel und da ist es schwer zu ermitteln welches davon der Vorgänger ist. In diesem Video wird erklärt Vorgänger der C ist B (Laut Buchstaben ja ^^), aber guckt man die Linien an ist C mit A auch verbinden. Wieso kann dann A nicht Vorgänger von C sein.
@MrAustraliarules Ist zumindest denkbar, AVL habe ich mal angerissen (aber ohne Erklärung des Algorithmus), Quicksort mache ich sicher mal irgendwas. Mal.
als erstes: ich finde es super das es menschen gibt die solche vids machen! und das is das vid durch den ich den algo wirklich verstanden habe!! hab auch scho daumen nach oben gemacht =). danke.
also nich falsch verstehen, aber ich glaube das irgendwas in deiner definition nich stimmt. nämlich erstens:
wenn man den knoten mit geringster distanz sucht kann es auch vorkommen das in ihm noch unendlich steht (akt dist.) und wenn man was zu unendlich addiert -> nich so toll.
2. wenn der ziel knoten noch einen knoten hat der ins leere fürt gibt es auch probleme. dann gehe ich vom ziel zu vorherigen -> der hat aber keinen vorgänger da er ja nur mim ziel verbunden ist!! bin mir nich sicher ob es stimmt glaube aber schon.
arbeite atm an einer wegfindung und deshalb brauche ich es genau wie möglich. korrigiere mich wenn ich falsch liege...
@bhbblblblllb Das stimmt wohl auch nicht. Ich weiß nicht genau, was du mit Zielknoten oder ins Leere meinst, aber der Algorithmus dürfte so schon stimmen.
@bhbblblblllb Nein, das stimmt schon. Es ja nie etwas zu unendlich addiert, sondern nur die Summe von (Distanz des aktuellen Knotens + Kantengewicht) mit der Distanz der Nachbarknoten *verglichen*, die durchaus unendlich sein kann. Dann wird der unendlich Wert ersetzt durch den neuen, nicht dazu addiert.
ja aber wenn: (Distanz des aktuellen Knotens + Kantengewicht) zutrifft und Distanz des aktuellen Knotens = unedlich ist hat man das problem. und das kommt durchaus vor bei der definition wie du sie gegeben hast. wahrscheinlich weist du es schon aber man sollte die offnen knoten in eine priority queue tun... dann kann es nich passieren das man einen knoten hat bei dem die distanz des aktuellen knotens unendlich ist. vorallem wir die distanz dieses knoten auch nich mehr geändert...
@bhbblblblllb Da ist das Missverständnis: die Distanz des aktuellen Knotens kann nie unendlich sein. Sie beginnt beim Startknoten mit 0, und der neue aktuelle Knoten (ermittelt in der Implementierung durch eine priority queue) ist (0+Kantengewicht), und so weiter. Ein Knoten wird ja erst dann aktuell gemacht, wenn seine Distanz eben nicht unendlich ist (sondern in der quee ganz vorne steht).
@2VisionsPhotography Es ist mathematisch aber richtig, hier von einem "Kantengewicht" zu sprechen. Es wäre "total dumm" das Meter zu nennen...was willst du z.B. mit Metern, wenn du die Wege zur Kommunikation zwischen Servern berechnest?
@Chasmo90 Wenn man statt Server Orte und statt Kantengewicht Meter nimmt und sich so bildlich anders vorstellt ist das für die Grundübung recht einfacher zu verstehen.
@Pagai Nein, die Frage "geringste Distanz zum aktuellen Knoten" taucht im Algorithmus gar nicht auf. Beim aktuellen Knoten geht es nur immer darum, alle noch nicht besuchten Nachbarn mal probeweise auszurechnen und eventuell zu aktualisieren - in welcher Reihenfolge man das macht, ist egal.
Danke!
Hat mir geholfen den Algorithmus endlich zu verstehen und meine java-Umsetzung ist hiernach euch schon recht weit.
ClanAbLeSquAd 3 weeks ago
boah ich krieg echt nen hals wenn ich mir das anschau. Das ist echt für begriffsstuzige oder...
metamurk 1 month ago
Labber
metamurk 1 month ago
Vielen Dank, das ist allemal verständlicher als die Wikipedia-Pseudocode-Erklärungen... (:
gletschering 1 month ago
top!
BeHotSiii 5 months ago
Schöne erklärung
Gell1welt69 8 months ago
Super, vielen Dank!
Sinngh 8 months ago
Sehr Nice, danke hat mir das ganze wudnerbarerklärt
xinox1 8 months ago
Ich weiß nicht, ob ich das richtig verstanden habe, biLo88. Es gibt feste Positionen (Waypoints) in der Spielwelt, und das Objekt kann nur jeweils von Position zu Position zu springen oder sich auf dem kürzesten direkten Weg dorthin begeben (was aufs gleiche hinausläuft). Dann wäre das wohl ein vollständiger Graph, so dass jede Position mit jeder anderen verbunden ist, und man soden kürzesten Weg findet. Aber das ginge dann wohl einfacher ohne Dijkstra. Oder gibt es doch feste Pfade/Kanten?
HerrRau2 9 months ago
Bzw. hat alles Nachbarn wollte ich noch hinzufügen
biLo88 9 months ago
Oh, ich merke gerade, dass ich mich total Falsch ausgedrückt habe. Es geht eher um die Nachbarn. Ich setze Positionen in der Spielewelt ein. Z.b. (10,10,0) und ein anderer Punkt ist (10,15,0) noch einer (5,5,0) usw. Da gibst also keine Nachbarn (weil es uach noch keine Kollisionen gibt nur das man nicht runterfallen kann. Klippen usw.). Was ich mindestens machen kann, das mein Objekt sich über die Wegpunkte entlang bewegen kann (oder in der Nähe). Naja ein schwieriges Thema für mich denke ich.
biLo88 9 months ago
Erst mal danke für dieses Video. Ich habe die Basis wissen mit einmaligen ansehen verstanden, aber dennoch habe ich eine Frage dazu. Wie ist das, wenn man die Vorgänger gar nicht kennt. Ich arbeite mit Waypoints in einem Spiel und da ist es schwer zu ermitteln welches davon der Vorgänger ist. In diesem Video wird erklärt Vorgänger der C ist B (Laut Buchstaben ja ^^), aber guckt man die Linien an ist C mit A auch verbinden. Wieso kann dann A nicht Vorgänger von C sein.
biLo88 9 months ago
thx
EinEinhalber 10 months ago
Perfekt für meine GLF.. DANKE!
Babylovegirl20 10 months ago
gibt es auch ein video auf deutsch, dass den kürzesten weg allen knoten zu allen knoten zeigt??
Spongimongi 11 months ago
Dank :)
CovHax 11 months ago
Find das Video echt gut!
Himbeerbrause19 1 year ago
Finde das Video auch super! Kann man das vielleicht auch zum Ford-Algorithmus erstellen....?!?! Wäre total gut :-)
ratona14100 1 year ago
@ratona14100 Wenn's mal in der Schule drankommt (oder ich das als Referat verteilen kann), gerne. Sieht aber erst mal nicht so wahrscheinlich aus.
HerrRau2 1 year ago
@HerrRau2 Wäre es möglich einmal Quicksort v die Rotation des AVL Baums von dir erklärt zu bekommen.
Fand die Erklärung hier sehr schön simple gehalten. Weiter so !!
MrAustraliarules 1 year ago
@MrAustraliarules Ist zumindest denkbar, AVL habe ich mal angerissen (aber ohne Erklärung des Algorithmus), Quicksort mache ich sicher mal irgendwas. Mal.
HerrRau2 1 year ago
Besten Dank!!!!
Super erklärt ich hab's verstanden!!!
realmelofan 1 year ago
als erstes: ich finde es super das es menschen gibt die solche vids machen! und das is das vid durch den ich den algo wirklich verstanden habe!! hab auch scho daumen nach oben gemacht =). danke.
also nich falsch verstehen, aber ich glaube das irgendwas in deiner definition nich stimmt. nämlich erstens:
wenn man den knoten mit geringster distanz sucht kann es auch vorkommen das in ihm noch unendlich steht (akt dist.) und wenn man was zu unendlich addiert -> nich so toll.
bhbblblblllb 1 year ago
@bhbblblblllb
2. wenn der ziel knoten noch einen knoten hat der ins leere fürt gibt es auch probleme. dann gehe ich vom ziel zu vorherigen -> der hat aber keinen vorgänger da er ja nur mim ziel verbunden ist!! bin mir nich sicher ob es stimmt glaube aber schon.
arbeite atm an einer wegfindung und deshalb brauche ich es genau wie möglich. korrigiere mich wenn ich falsch liege...
aber trozdem danke!!! super von dir...
bhbblblblllb 1 year ago
@bhbblblblllb Das stimmt wohl auch nicht. Ich weiß nicht genau, was du mit Zielknoten oder ins Leere meinst, aber der Algorithmus dürfte so schon stimmen.
HerrRau2 1 year ago
@bhbblblblllb Nein, das stimmt schon. Es ja nie etwas zu unendlich addiert, sondern nur die Summe von (Distanz des aktuellen Knotens + Kantengewicht) mit der Distanz der Nachbarknoten *verglichen*, die durchaus unendlich sein kann. Dann wird der unendlich Wert ersetzt durch den neuen, nicht dazu addiert.
HerrRau2 1 year ago
@HerrRau2
ja aber wenn: (Distanz des aktuellen Knotens + Kantengewicht) zutrifft und Distanz des aktuellen Knotens = unedlich ist hat man das problem. und das kommt durchaus vor bei der definition wie du sie gegeben hast. wahrscheinlich weist du es schon aber man sollte die offnen knoten in eine priority queue tun... dann kann es nich passieren das man einen knoten hat bei dem die distanz des aktuellen knotens unendlich ist. vorallem wir die distanz dieses knoten auch nich mehr geändert...
bhbblblblllb 1 year ago
@bhbblblblllb Da ist das Missverständnis: die Distanz des aktuellen Knotens kann nie unendlich sein. Sie beginnt beim Startknoten mit 0, und der neue aktuelle Knoten (ermittelt in der Implementierung durch eine priority queue) ist (0+Kantengewicht), und so weiter. Ein Knoten wird ja erst dann aktuell gemacht, wenn seine Distanz eben nicht unendlich ist (sondern in der quee ganz vorne steht).
HerrRau2 1 year ago
@HerrRau2
dann passt es =)
bhbblblblllb 1 year ago
Total dumm das "GEWICHT" zu nennen... wenn man von Wege spricht wären Meter oder Kilometer viel intelligenter gewesen.
2VisionsPhotography 1 year ago
@2VisionsPhotography Es ist mathematisch aber richtig, hier von einem "Kantengewicht" zu sprechen. Es wäre "total dumm" das Meter zu nennen...was willst du z.B. mit Metern, wenn du die Wege zur Kommunikation zwischen Servern berechnest?
Chasmo90 1 year ago
@Chasmo90 Wenn man statt Server Orte und statt Kantengewicht Meter nimmt und sich so bildlich anders vorstellt ist das für die Grundübung recht einfacher zu verstehen.
2VisionsPhotography 1 year ago
hätte Knoten D nicht vor Knoten E kommen müssen? wg. der geringsten Distanz zum aktuellen Knoten?
Pagai 1 year ago
@Pagai Nein, die Frage "geringste Distanz zum aktuellen Knoten" taucht im Algorithmus gar nicht auf. Beim aktuellen Knoten geht es nur immer darum, alle noch nicht besuchten Nachbarn mal probeweise auszurechnen und eventuell zu aktualisieren - in welcher Reihenfolge man das macht, ist egal.
HerrRau2 1 year ago
Gut erklärt. Gut wäre eine Anschauung mit gewichteten graphen, da dies häufiger auftaucht!
LimpBisquit2000 1 year ago