• Logik, Programmierung...

    Ich wollte gerade diesen Algorithmus umsetzen...

    https://www.inf.hs-flensburg.de/lang/algorithmen/graph/breadth-first-tree.htm

    ... und dachte mir, das müsste doch rekursiv ganz einfach sein. 2D-Feld, ich rufe die Funktion mit dem
    Startfeld auf und beginne mit 1, weil alle Felder zu Beginn 0 sind.

    FindWay
    ..... Item( StartX, StartY, 1 )

    Item( x, y, n )
    ..... Feld( x, y ) = n
    ..... Wenn Feld Rechts = 0 dann Item( x + 1, y, n + 1 )
    ..... Wenn Feld Links = 0 dann Item( x - 1, y, n + 1 )
    ..... Wenn Feld Oben = 0 dann Item( x, y + 1, n + 1 )
    ..... Wenn Feld Unten = 0 dann Item( x, y - 1, n + 1 )

    Klappt aber nicht. Und wenn ich es recht bedenke, kann ja auch nicht. Oder irre ich?

    • warum..

      .. wird mir bei diesem Beitrag im Werbebanner Damenwäsche angezeigt? Du solltest die Berechnung überdenken!
      Sonst expedia und Herrenmasshemden, was ich genauso oft wie Damenwäsche kaufe: nie.
        • Nichts passiert ohne Grund...

          ich hätte gedacht, der Grund war dein Beitrag.
          Weil jetzt wird wieder "Assistenzarzt und Facharzt Chirurgie gesucht"
          Wenn der Algorithmus was taugen würde wüssten sie, dass ich dafür überqualifiziert bin.
    • zwei allg. Ansätze

      Du hast ja verschiedene Möglichkeiten durch ein LAbyrint zu kommen. Zwei Wege sind vom Algorithmus identisch, nur die Richgtung variiert. Gehe immer nach (links|rechts), wenn es möglich ist. Stehste un einer Sackgasse drehe um und mach weiter. Damit findest du IMMER den Ausgang, ob es der schnellste Weg ist, kannst du nur erkennen, wenn du beide Varianten miteinander vergleichst (Anzahl der Schritte zum Ziel). Da brauchste nicht mal ne Rekursion, sondern eine Schleife bis zum Ziel. Aber du brauchst einen Marker, der dir sagt in welche Richtung du gerade gehst. Die Prüfung auf eine Abzweigung ist ja vom Marker abhängig ("in welche Richtung gucke ich und wo ist links?").
      • Besten Dank...

        ... das ist eine typische Breitensuche. Es geht darum den kürzesten Weg zu finden und jedes Feld mit der Schrittzahl zu markieren. Sodass von jedem Feld aus klar ist, wie das Ziel am schnellsten zu erreichen ist. Damit die kleinen Monster nachher wissen, in welche Richtung der Feind erreichbar ist, ohne das Labyrinth überhaupt lösen zu müssen. Es ist (am Ende) auch kein Labyrinth sondern eine sich verändernde Landschaft.

        Ich habe das jetzt klassisch iterativ mit einem Queue gelöst. Was ungleich komplexer ist. Warum der rekursive Weg nicht ging, weiß ich aber immer noch nicht. Egool.
        • Klassische Aufgabe für Dijkstra

          Dijkstra war ein niederländischer Mathematiker, der das Problem der kürzester Route zwischen zwei Endknoten und beliebig vielen Zwischenknoten gelöst hat.

          In jeder Routingsoftware wird das verwendet. Knoten sind dort Kreuzungen.

          Vielleicht hilft dir das.
      • Danke, aber der Algo war klar...

        ... es ging nur um die Übersetzung, ich hätte es gerne rekursiv gehabt, es gelang mir aber nur iterativ. Und ich wollte wissen, warum der rekursive Ansatz nicht klappte, er war so elegant

        Aber da bin ich hier dann doch etwas falsch
        • Deine Rekursion funktioniert nicht, weil …

          … Deine Verzweigungen alle ihre Nachbarn abarbeiten, bevor Dein Ursprungsfeld mit seinem nächsten Nachbarn fortfährt.

          Du gehst zuerst soweit es geht nach rechts, dann von jenem Feld aus soweit wie möglich nach oben (nach links geht nicht, da kommst Du her, die Felder sind nicht mehr frei). Erst wenn es keine unbesuchten Nachbarfelder mehr gibt gehst Du den Weg wieder zurück zur nächsten möglichen Kreuzung.

          Dein Algorithmus auf einem 5x5-Feld bei Start in der Mitte:
          item(3, 2, 1)
          Show Plain Text
          1. 0  0  0  0  0
          2. 0  0  1  0  0
          3. 0  0  0  0  0


          rechts = 0 => item(4, 2, 2)
          Show Plain Text
          1. 0  0  0  0  0
          2. 0  0  1  2  0
          3. 0  0  0  0  0


          rechts = 0 => item(5, 2, 3)
          Show Plain Text
          1. 0  0  0  0  0
          2. 0  0  1  2  3
          3. 0  0  0  0  0


          rechts ≠ 0, links ≠ 0, oben = 0 => item(5, 1, 4)
          Show Plain Text
          1. 0  0  0  0  4
          2. 0  0  1  2  3
          3. 0  0  0  0  0


          rechts ≠ 0, links = 0 => item(4, 1, 5)
          Show Plain Text
          1. 0  0  0  5  4
          2. 0  0  1  2  3
          3. 0  0  0  0  0


          rechts ≠ 0, links = 0 => item(3, 1, 6)
          Show Plain Text
          1. 0  0  6  5  4
          2. 0  0  1  2  3
          3. 0  0  0  0  0


          rechts ≠0, links = 0 => item(2, 1, 7)
          Show Plain Text
          1. 0  7  6  5  4
          2. 0  0  1  2  3
          3. 0  0  0  0  0


          rechts ≠ 0, links = 0 => item(1, 1, 8)
          Show Plain Text
          1. 8  7  6  5  4
          2. 0  0  1  2  3
          3. 0  0  0  0  0


          rechts ≠ 0, links ≠ 0, oben ≠ 0, unten = 0 => item(2, 1, 9)
          Show Plain Text
          1. 8  7  6  5  4
          2. 9  0  1  2  3
          3. 0  0  0  0  0


          rechts ≠ 0 => item(2, 2, 10)
          Show Plain Text
          1. 8  7  6  5  4
          2. 9  10 1  2  3
          3. 0  0  0  0  0


          rechts ≠ 0, links ≠ 0, oben ≠ 0, unten = 0 => item(2, 3, 11)
          Show Plain Text
          1. 8  7  6  5  4
          2. 9  10 1  2  3
          3. 0  11 0  0  0


          rechts = 0 => item(3, 3, 12)
          Show Plain Text
          1. 8  7  6  5  4
          2. 9  10 1  2  3
          3. 0  11 12 0  0


          rechts = 0 => item(4, 3, 13)
          Show Plain Text
          1. 8  7  6  5  4
          2. 9  10 1  2  3
          3. 0  11 12 13 0


          rechts = 0 => item(5, 3, 14)
          Show Plain Text
          1. 8  7  6  5  4
          2. 9  10 1  2  3
          3. 0  11 12 13 14


          rechts ≠ 0, links ≠ 0, oben ≠ 0, unten ≠ 0 => zurück in Funktion (n = 13)
          rechts ≠ 0, links ≠ 0, oben ≠ 0, unten ≠ 0 => zurück in Funktion (n =12)
          rechts ≠ 0, links ≠ 0, oben ≠ 0, unten ≠ 0 => zurück in Funktion (n = 11)
          rechter Abzweig schon erledigt, links = 0 => item(1, 3, 12)
          Show Plain Text
          1. 8  7  6  5  4
          2. 9 10  1  2  3
          3. 12 11 12 13 14



          Dein Call-Stack sieht so aus:
          Show Plain Text
          1. item(3, 2, 1)
          2. |-- item(4, 2, 2)
          3. |   '-- item(5, 2, 3)
          4. |       '-- item(5, 1, 4)
          5. |           '-- item(4, 1, 5)
          6. |               '-- item(3, 1, 6)
          7. |                   '-- item(2, 1, 7)
          8. |                       '-- item(1, 1, 8)
          9. |                           '-- item(2, 1, 9)
          10. |                               '-- item(2, 2, 10)
          11. |                                   ‘-- item(2, 3, 11)
          12. |                                       |-- item(3, 3, 12)
          13. |                                       |   '-- item(4, 3, 13)
          14. |                                       |       '-- item(5, 3, 14)
          15. |                                       '-- item(1, 3, 12)
          • Super, vielen Dank...

            ... es kam mir auch verdächtig einfach vor

            Die Lösung hier funktioniert ganz gut, mit Queue halt (list of pair), aber gut.
            way ist das Feld mit den Schrittzahlen. Die Funktion funktioniert auch als Test und gibt False zurück wenn Start und Ziel nicht verbunden sind. Höhlen haben Null, die brauche ich auch nicht.


            Var list( -1 ) As Pair
            Var i, x, y as integer

            i = 0
            list.Add New Pair( StartFieldX, StartFieldY )

            Do
                 x = list( 0 ).x
                 y = list( 0 ).y
                 list.Remove( 0 )

                 i = way( x, y )

                 If (Weg nach Rechts möglich und frei) Then
                      way( x + 1, y) = i + 1
                      list.add New pair( x + 1, y)
                 End If

                 If (Weg nach Links möglich und frei) Then
                 way( x - 1, y ) = i + 1
                 list.add New pair( x - 1, y )
                 End If

                 If (Weg nach Unten möglich und frei) Then
                      way( x, y + 1 ) = i + 1
                      list.Add New pair( x, y + 1 )
                 End If

                 If (Weg nach Oben möglich und frei) Then
                      way( x, y - 1 ) = i + 1
                      list.Add New pair( x, y - 1 )
                 End If

            Loop Until list.count = 0

            way( StartFieldX, StartFieldY ) = 0

            If way( FinishFieldX, FinishFieldY ) = 0 Then
                 Return False
            End If

            Return True