Streckenberechnung / Route

[angelshouse]

Hallo,

ich mach grad so eine kleine Stadtkarte mit Routenberechnung, nur irgendwie komm ich nicht so richtig weiter.

Habe also meine Karte und da drin liegen 6 Punkte, man wählt in der Karte den Startpkt und in einer danenben liegenden Tabelle den Zielpunkt.
Mein Algorithmus soll durchchecken über welchen der anderen Punkte man am kürzesten zum Zielpunkt kommt.
Die Entfernungen zu den einzelnen Punkte habe ich festgelegt. Nur scheitere ich bei der Fkt.

Habe es mit (mehreren) if-Schleifen gemacht, bloß das is viel zu umständlich und wenn mal noch ein Pkt in der Karte dazu kommt,
nochmal riesig viel Arbeit.... (muß da ja jede Möglichkeit einzeln festhalten)

Gibt es im ActionScript irgend eine Fkt, die so was durchchecken kann???
Könnt ihr mir da mal nen Tipp geben, bin dankbar für jede Hilfe.
angelshouse

[sonar]

Als Suchbegriff kann ich dir mal 'pathfinder' nennen... muss allerdings gleich dazu sagen, dass das harter Tobak is..!

[astro-susi]

also im prinzip kannst du das so machen (so ungefähr der viterbi-algorithmus, wenn ich's richtig im kopf habe... )

du hast deine punkte, die heißen A, B, ... F
manche sind verbunden, jede strecke hat eine länge; z.B. (A,B): 5
diese strecken mit längen musst du irgendwie gespeichert haben, zum Beispiel in einem zweidimensionalen array: laenge[A][B] = 5 heißt: Länge von A nach B ist 5.

angenommen, du willst von A nach E und hast folgende strecken:
(A,B): 3, (A,C): 5
(B,A): 3 (die gegenrichtung), (B,D): 1
(C,A): 5, (C,D): 7, (C,B): 1
(D,E): 2

du beginnst bei A und folgst allen kanten und speicherst die kosten:
weg A-B: 3 (*), weg A-C: 5

von jedem erreichten punkt folgst du wieder allen kanten:
weg A-B-D: 3+1 = 4, weg A-C-D: 5+7 = 12, weg A-C-B: 5+1 = 6, ...

der dritte weg fällt weg, weil du oben (*) gespeichert hast, dass man nach B über den weg A-B mit nur 3 statt 6 kommt. der zweite fällt weg, weil man D über A-B-D schneller erreicht.

schließlich gehst du von D nach E und bist angekommen.

also: für jeden punkt allen ausgehenden kanten folgen, in jedem punkt die minimalen weg-kosten (die kürzeste strecke) und den weg dorthin (also z.B. A-B) speichern, wenn du angekommen bist diesen weg im zielpunkt auslesen.


klaro?

viel spaß...

[sonar]

sagichja...

[angelshouse]

danke, ich probier mich heut abend mal daran...
vielleicht habe ich ja mal noch ne frage an euch.
vielen dank...

[angelshouse]

geht doch auch so

[astro-susi]

ist doch so wie ich's oben geschrieben habe...?
da berechnest du auch für jeden punkt die dahinterliegenden, und die streckenlänge und den weg musst dir eh merken. dadurch, dass du in jedem punkt prüfst, welcher aktuelle weg der kürzeste ist, sparst dir rechenarbeit und verhinderst gleichzeitig auch endlosschleifen in deinem weg.

und rekursion in as geht wie überall sonst auch:

function rec (startpunkt, endpunkt) {
  if (startpunkt == endpunkt) {
      return 1;
  } else if ( startpunkt.naechste.length == 0) {
      return 0;
  } else {
     for (p = 0; p < startpunkt.naechste.length; p++) {
         rec (startpunkt.naechste[p], endpunkt);
    }
  }
} 

durchläuft alle punkte, falls du die nachfolgepunkte als eigenschaft im jeweiligen punkt als array speicherst.