Dijkstra-Algorithmus übersetzen - AS3

[Matze]

Hallo!

Ich steh' gerade vor dem Problem, dass ich versuche den Pfad eines per "Drag" gezogenen Elements bei "Drop" wieder zurück zu dessen Ursprung zu ermitteln.
Das sollte eigentlich mit dem Dijkstra-Algorithmus möglich sein, aber ich versteh es nicht.

Die Sprache ist ActionScript 3, dürfte aber auch für andere Ecma-Derivate gelten. Ich hab den Code mal als JS markiert, damit er im Text beachtet wird.

Ich habe es zuerst so gelöst. Die Funktion triggert bei jedem Frame-Aufruf bis das Element wieder bei xLoc und yLoc ist:

private var xLoc:int = 50;  
private var yLoc:int = 50;  
private var speed:int = 10;  
  
private function moveElementHome(e):void {  
			  
    // X-Achse  
    if((e.currentTarget.x - speed) > xLoc){  
        e.currentTarget.x -= speed;  
    }else if((e.currentTarget.x + speed) < xLoc){  
        e.currentTarget.x += speed;  
    }else{  
        e.currentTarget.x = xLoc;  
    }  
  
    // Y-Achse			  
    if((e.currentTarget.y - speed) > yLoc){  
        e.currentTarget.y -= speed;  
    }else if((e.currentTarget.y + speed) < yLoc){  
        e.currentTarget.y += speed;  
    }else{  
        e.currentTarget.y = yLoc;  
    }  
  
    // Schleife beenden  
    if(e.currentTarget.x == xLoc && e.currentTarget.y == yLoc){  
        e.currentTarget.removeEventListener(Event.ENTER_FRAME, moveElementHome);  
    }  
}

Das bringt mein Element auch wieder zurück zum Startpunkt, aber halt nicht auf dem kürzesten Weg.

Leider hab ich arge Probleme den Pseudocode zu übersetzen.

Könnte mir bitte jemand dabei helfen? Gibt es dafür Beispiele?

Danke, Matze

[bleicher]

Grüße,

Das sollte eigentlich mit dem Dijkstra-Algorithmus möglich sein, aber ich versteh es nicht.

wir hatten den mal als aufgabe im 2en semester^^ - kann versuchen zu erklären, bei wiki ist er aber recht gut -
blöde frage - aber warum bringst du das Element nicht auf einem geraden Pfad zurück? dijxtra ist dazu da um bei mehreren wegmöglichkeiten zu entscheiden - ein drag&drop kannst du doch auf einer geraden zurückfallen lassen?
MFG
bleicher

[Matze]

Hallo bleicher,

blöde frage - aber warum bringst du das Element nicht auf einem geraden Pfad zurück? dijxtra ist dazu da um bei mehreren wegmöglichkeiten zu entscheiden - ein drag&drop kannst du doch auf einer geraden zurückfallen lassen?

Ich würde ja gerne die gerade berechnen. Ich wüsste (noch) nicht, womit ich das automatisch erledigen lassen kann.
Im Moment ist es so, dass ich mich in 10-Pixel-Schritten auf das Ziel "z" zubewege. Wenn aber z.B. der X-Abstand zu z kleiner ist als der Y-Abstand, dann erreiche ich X vor Y und der Weg zu z auf der Y-Achse wird eine gerade Line. Das ist unschön. Der Weg soll immer die kürzere Diagonale sein.

Vielleicht gibts dafür auch schon eine fertige Funktion und ich hab sie nur noch nicht gefunden. Vielleicht gibts auch eine andere Lösung?
Ich dachte mit dem Dijkstra-Algorithmus wäre ich richtig, damit lässt sich auch die kürzeste Verbindung zwischen 2 Punkten ermitteln.

Grüße, Matze

[Der-Dennis]

Hallo Matze,

mit AS kenne ich mich nicht aus. Schau Dir aber mal die Seite http://script.aculo.us/ an. Die Kreise auf der Startseite können durch Klick auf die Überschrift verschoben werden, beim Loslassen geht's auf direktem Weg zurück zum Ursprung. Vielleicht kannst Du Dir da mal den Quelltext der Funktion anschauen und auf AS übertragen?

Gruß, Dennis

[Matze]

Hi Dennis,

danke, von der Animation her möchte ich es genau so haben.

Ich werde mir das Script anschauen.

Grüße, Matze

[Richard]

Hallo Matze,

Ich dachte mit dem Dijkstra-Algorithmus wäre ich richtig, damit lässt sich auch die kürzeste Verbindung zwischen 2 Punkten ermitteln.

Vermutlich verstehe ich dich gerade völlig falsch, aber die kürzeste Verbindung zwischen zwei Punkten ist eine Gerade. Wenn du die Koordinaten zweier Punkte gegeben hast, kannst du die doch problemlos ermitteln:

Sei Punkt X = (20,40)
Sei Punkt Y = (60,100)

Anstieg m = delta(X) / delta(Y) = 40 / 60 = 2/3
Da das Koordiatensystem am Monitor oben links seinen Ursprung hat, müssen wir den Ansteig negieren, also m = -2/3

Die (lineare) Funktion heißt also y = -2/3 * x + n

Setzen wir dort den ersten Punkt ein, erhalten wir:
40 = -2/3 * 20 + n = -40/3 + n und damit: n = 160/3, was wir wieder negieren müssen, also n = -160/3

Die Funktion, die diese Gerade beschreibt, heißt also f(x) = y = -2/3 * x - 160/3

Mit dieser Funktion kannst du dir nun für jeden beliebigen x- (y-)Wert den zugehörigen y- (x-)Wert ausrechnen.

Grüße
Richard

[Richard]

Hallo,

Nachtrag: der Dijkstra-Algorithmus sucht kürzeste Wege in ungerichteten, bewerteten Graphen. Einen solchen kann ich deiner Beschreibung nicht entnehmen. Also habe ich dich entweder falsch verstanden oder du versuchst einen Algorithmus auf ein Problem anzuwenden, für das er nicht geeignet ist.

Grüße
Richard

[Matze]

Hallo Richard,

Also habe ich dich entweder falsch verstanden oder du versuchst einen Algorithmus auf ein Problem anzuwenden, für das er nicht geeignet ist.

kann sein. Das Beispiel von Richard tut genau das was ich will.
Dein Beispiel leg ich mir auch mal zur Seite, danke dafür!
Im Moment hab ich erstmal wieder ein anderes Problem ;)

Grüße Matze