a* A-Star Algorithmus (Grafik!!)

  • Hi,

    nachdem ein einzelnes Forenmitglied 8) eine Nachfrage nach dem a*-Algorithmus gestellt hatte, bekam ich Lust, den Lösungsweg in "schöner" Form in ein Script zu giessen.

    Schön ist hier nicht der Code, sondern die Darstellung^^
    Man beginnt mit einem leeren Feld, auf dem man den Startpunkt und den Zielpunkt markieren kann.
    Entweder man klickt jetzt nochmal auf den Startpunkt und der Algorithmus sucht den kürzesten Weg zum Ziel, oder man klickt auf ein leeres Feld, um dort ein "Hindernis" zu erstellen.
    So kann man auch ein Labyrinth erstellen, durch das sich a* den kürzesten Weg zum Ziel sucht....

    Viel Spass!

    Spoiler anzeigen
    [autoit]

    Global $feldgroesse_x = 40
    Global $feldgroesse_y = 30
    Global $startx, $starty, $zielx, $ziely, $start = 0
    Global $listenindex, $ziel_gefunden = 0

    [/autoit] [autoit][/autoit] [autoit]

    Dim $feld[$feldgroesse_x * $feldgroesse_y + 1] ;warum eindimensional? damit man es in eine struct umwandeln kann^^
    Dim $liste[$feldgroesse_x * $feldgroesse_y + 1][3] ;liste der besten kandidaten

    [/autoit] [autoit][/autoit] [autoit]

    $w = 1200
    $h = 900
    $abstand = 1

    [/autoit] [autoit][/autoit] [autoit]

    $hgui = GUICreate("a-star", $w, $h)

    [/autoit] [autoit][/autoit] [autoit]

    $breite = Round(($w - 2 * $abstand - ($feldgroesse_x - 1) * $abstand) / $feldgroesse_x)
    $hoehe = Round(($h - 2 * $abstand - ($feldgroesse_y - 1) * $abstand) / $feldgroesse_y)

    [/autoit] [autoit][/autoit] [autoit]

    For $y = 0 To $feldgroesse_y - 1
    For $x = 0 To $feldgroesse_x - 1
    $feld[$y * $feldgroesse_x + $x] = GUICtrlCreateButton("", $x * ($breite + $abstand) + $abstand, $y * ($hoehe + $abstand) + $abstand, $breite, $hoehe)
    If $x = 0 Or $y = 0 Or $x = $feldgroesse_x - 1 Or $y = $feldgroesse_y - 1 Then ;rand einfärben
    GUICtrlSetBkColor($feld[$y * $feldgroesse_x + $x], 0x000000) ;Rand schwarz
    GUICtrlSetColor($feld[$y * $feldgroesse_x + $x], 0x000000)
    GUICtrlSetData($feld[$y * $feldgroesse_x + $x], "X")
    EndIf
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    WinSetTitle($hgui, "", "a* DEMO: Bitte Startpunkt auswählen ")

    [/autoit] [autoit][/autoit] [autoit]

    GUISetState()

    [/autoit] [autoit][/autoit] [autoit]

    $rot = 0xFF0000
    $gruen = 0x00FF00
    $blau = 0x0000FF
    $schwarz = 0x000000
    $weiss = 0xFFFFFF
    $grau = 0xF6F6F4

    [/autoit] [autoit][/autoit] [autoit]

    $i = 1

    [/autoit] [autoit][/autoit] [autoit]

    While 1
    $msg = GUIGetMsg()
    Switch $msg
    Case -3
    ExitLoop
    Case $feld[$start] ; a* starten
    If $i > 2 Then
    If _astar() = 1 Then
    WinSetTitle($hgui, "", "a* DEMO: Bitte Hindernisse auswählen und danach auf 'Start' drücken")
    $i = 3 ;nochmal
    EndIf
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    Case $feld[0] To $feld[$feldgroesse_x * $feldgroesse_y - 1]
    $msg -= $feld[0] ;korrektur buttonindex
    $xx = Mod($msg, $feldgroesse_x) + 1 ;x-und y- koordinaten des buttons
    $yy = Int($msg / $feldgroesse_x) + 1
    If $xx > 1 And $yy > 1 And $xx < $feldgroesse_x And $yy < $feldgroesse_y Then ;innerhalb des Randbereichs
    Switch $i
    Case 1 ;startpunkt ausgewählt
    $i += 1
    GUICtrlSetBkColor($feld[$msg], $rot) ;startpunkt
    GUICtrlSetData($feld[$msg], "Start")
    WinSetTitle($hgui, "", "a* DEMO: Bitte Zielpunkt auswählen")
    $startx = $xx
    $starty = $yy
    $start = ($yy - 1) * $feldgroesse_x + ($xx - 1)
    Case 2 ;zielpunkt
    $i += 1
    GUICtrlSetBkColor($feld[$msg], $gruen)
    WinSetTitle($hgui, "", "a* DEMO: Bitte Hindernisse auswählen und danach auf 'Start' drücken")
    GUICtrlSetData($feld[$msg], "Ziel")
    $zielx = $xx
    $ziely = $yy
    Case 3 To $feldgroesse_x * $feldgroesse_y - 3
    $i += 1
    If GUICtrlRead($feld[$msg]) = "X" Then ;Hindernis entfernen
    GUICtrlSetBkColor($feld[$msg], $grau);hintergrund
    GUICtrlSetColor($feld[$msg], $schwarz);schrift
    GUICtrlSetData($feld[$msg], "");leer
    Else
    GUICtrlSetBkColor($feld[$msg], $schwarz)
    GUICtrlSetColor($feld[$msg], $weiss)
    GUICtrlSetData($feld[$msg], "X")
    EndIf
    EndSwitch
    EndIf
    EndSwitch

    [/autoit] [autoit][/autoit] [autoit]

    WEnd

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func _astar() ;sucht kürzeste strecke vom start zum ziel
    WinSetTitle($hgui, "", "a* DEMO: Berechnung... ")

    [/autoit] [autoit][/autoit] [autoit]

    ; $optimum = Sqrt(($startx - $zielx) ^ 2 + ($starty - $ziely) ^ 2)

    [/autoit] [autoit][/autoit] [autoit]

    $index_x = $startx
    $index_y = $starty

    [/autoit] [autoit][/autoit] [autoit]

    While 1

    [/autoit] [autoit][/autoit] [autoit]

    suche_nachbar($index_x, $index_y) ;sucht leere nachbarfelder und füllt sie aus mit kleinstem abstand

    [/autoit] [autoit][/autoit] [autoit]

    If $ziel_gefunden = 1 Then
    Switch Auf_kuerzestem_Weg_zurueck() ;nochmal?
    Case 6 ;Ja
    Dim $liste[$feldgroesse_x * $feldgroesse_y + 1][3];liste leeren
    $listenindex = 0
    $ziel_gefunden = 0
    $gesamt = 0
    For $i = 1 To $feldgroesse_x * $feldgroesse_y;felder leeren
    If Number(GUICtrlRead(($feld[$i]))) <> 0 Then ;keine Buchstaben, nur Ziffern im Feld
    GUICtrlSetData($feld[$i], "");inhalt löschen
    GUICtrlSetBkColor($feld[$i], $grau);grau
    EndIf
    Next
    Return 1

    [/autoit] [autoit][/autoit] [autoit]

    Case 7 ;abbrechen
    Exit
    EndSwitch
    Exit
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    $kleinstes = 2 ^ 30
    For $i = 1 To $listenindex ;kleinster abstand zum ziel suchen
    If $liste[$i][0] < $kleinstes Then ;kleinstes gefunden
    $kleinstes = $liste[$i][0]
    $index = $i ;index kleinster abstand
    EndIf
    Next
    If $kleinstes = 2 ^ 30 Then Exit (MsgBox(0, "a* DEMO", "Ziel nicht gefunden!"))
    ; ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $kleinstes = ' & $kleinstes & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

    [/autoit] [autoit][/autoit] [autoit]

    $index_x = $liste[$index][1] ;koordinaten für nächsten durchlauf
    $index_y = $liste[$index][2] ;koordinaten für nächsten durchlauf
    $liste[$index][0] = 2 ^ 30 ;aus liste herausnehmen
    ;_arraydisplay($liste)

    [/autoit] [autoit][/autoit] [autoit]

    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    EndFunc ;==>_astar

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func suche_nachbar($x, $y) ;sucht leere nachbarfelder und füllt sie aus mit kleinstem abstand

    [/autoit] [autoit][/autoit] [autoit]

    ;abstand gerade = 1
    ;abstand schräg =1.4 =sqrt(2)

    [/autoit] [autoit][/autoit] [autoit]

    For $yy = $y - 1 To $y + 1 ;3x3 matrix
    For $xx = $x - 1 To $x + 1
    If $yy = $y And $xx = $x Then ContinueLoop ;mittelpunkt erreicht
    $index = ($yy - 1) * $feldgroesse_x + ($xx - 1)
    ; ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $index = ' & $index & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    $inhalt = GUICtrlRead($feld[$index])
    ; ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $inhalt = ' & $inhalt & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    If $inhalt = "Ziel" Then
    MsgBox(0, "a* DEMO", "Ziel gefunden!!!")
    $ziel_gefunden = 1
    EndIf
    If $inhalt = "" Then ;leeres feld gefunden, dort den kürzesten abstand zu allen angrenzenden mit zahlen ausgefüllten feldern finden
    $kleinster_nachbar = 2 ^ 30
    $add = 0
    For $yyy = $yy - 1 To $yy + 1 ;3x3 matrix
    For $xxx = $xx - 1 To $xx + 1
    If $yyy = $yy And $xxx = $xx Then ContinueLoop ;mittelpunkt erreicht
    $index2 = ($yyy - 1) * $feldgroesse_x + ($xxx - 1)
    $inhalt2 = GUICtrlRead($feld[$index2])
    If $inhalt2 <> "X" And $inhalt2 <> "" And $inhalt2 <> "Ziel" And $inhalt <> "Start" Then
    $inhalt2 = Number($inhalt2)
    ;MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @LF & '$inhalt2' & @LF & @LF & 'Return:' & @LF & $inhalt2) ;### Debug MSGBOX
    If ($yyy = $yy - 1 And ($xxx = $xx - 1 Or $xxx = $xx + 1)) Or ($yyy = $yy + 1 And ($xxx = $xx - 1 Or $xxx = $xx + 1)) Then ;diagonal
    If $inhalt2 < $kleinster_nachbar Then
    $kleinster_nachbar = $inhalt2 ;diagonal
    $add = 1.16
    EndIf
    Else
    If $inhalt2 < $kleinster_nachbar Then
    $kleinster_nachbar = $inhalt2 ;waagrecht und senkrecht
    $add = 1
    EndIf
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    Next
    Next
    $abstand_zum_ziel = Int(Sqrt(($xx - $zielx) ^ 2 + ($yy - $ziely) ^ 2) * 10) / 10 ;eine nachkommastelle
    $listenindex += 1 ;neuen kandidaten gefunden
    $liste[$listenindex][0] = $kleinster_nachbar + $add + $abstand_zum_ziel ;gesamtgewicht
    ; $liste[$listenindex][0] = $abstand_zum_ziel ;gesamtgewicht
    $liste[$listenindex][1] = $xx ;koordinaten
    $liste[$listenindex][2] = $yy
    GUICtrlSetData($feld[$index], $kleinster_nachbar + $add) ;startfeld
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ; MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @LF & '$inhalt' & @LF & @LF & 'Return:' & @LF & $inhalt) ;### Debug MSGBOX
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    EndFunc ;==>suche_nachbar

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func Auf_kuerzestem_Weg_zurueck()
    $x = $zielx
    $y = $ziely
    $Kleinster_nachbar_index = 2 ^ 30
    $gesamt = 0 ;kürzeste gesamtstrecke
    While 1
    $kleinster_nachbar = 2 ^ 30
    For $yy = $y - 1 To $y + 1 ;3x3 matrix
    For $xx = $x - 1 To $x + 1
    If $yy = $y And $xx = $x Then ContinueLoop ;mittelpunkt erreicht
    $index = ($yy - 1) * $feldgroesse_x + ($xx - 1)
    ; ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $index = ' & $index & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    $inhalt = GUICtrlRead($feld[$index])
    If $inhalt = "Start" Then ;am start angekommen
    Return MsgBox(4, "a* DEMO", "Kürzeste Strecke = " & $gesamt & @CRLF & @CRLF & "Labyrint ändern?")
    EndIf
    If $inhalt <> "X" And $inhalt <> "" And $inhalt <> "Ziel" Then ;Zahl gefunden
    $abstand = Number($inhalt)
    ;ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $abstand = ' & $abstand & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    If $abstand < $kleinster_nachbar Then
    $kleinster_nachbar = $abstand
    $Kleinster_nachbar_x = $xx
    $Kleinster_nachbar_y = $yy
    $Kleinster_nachbar_index = $index
    EndIf
    EndIf
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    $gesamt += $kleinster_nachbar
    $x = $Kleinster_nachbar_x
    $y = $Kleinster_nachbar_y
    GUICtrlSetBkColor($feld[$Kleinster_nachbar_index], $blau)
    ;msgbox(0,0,$kleinster_nachbar)
    WEnd

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    EndFunc ;==>Auf_kuerzestem_Weg_zurueck

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit]


    Mit 30x30 Feldern und 1200x900 Pixeln sieht das bspw. so aus:
    autoit.de/wcf/attachment/20507/

    /EDIT/
    Die gemächliche Geschwindigkeit ist dem GuiCtrlSet/GuiCtrlGet/GuiCtrlRead-Gedöns geschuldet. Die reine Rechenzeit liegt im Millisekundenbereich.

    ciao
    Andy


    "Schlechtes Benehmen halten die Leute doch nur deswegen für eine Art Vorrecht, weil keiner ihnen aufs Maul haut." Klaus Kinski
    "Hint: Write comments after each line. So you can (better) see what your program does and what it not does. And we can see what you're thinking what your program does and we can point to the missunderstandings." A-Jay

    Wie man Fragen richtig stellt... Tutorial: Wie man Script-Fehler findet und beseitigt...X-Y-Problem

    7 Mal editiert, zuletzt von Andy (5. April 2013 um 15:24)

  • Da hatte jemand wohl eine lange Nacht gehabt! ;)


    Sehr schön geworden! :thumbup:

    Cool wäre es, wenn man schwarze Linien zeichnen könnte anstatt "mühselig" die Punkte zu setzen! Und ich kann das Ziel löschen.

    Gruß,
    UEZ

    Auch am Arsch geht ein Weg vorbei...

    ¯\_(ツ)_/¯

    Einmal editiert, zuletzt von UEZ (5. April 2013 um 13:17)

  • Hi,
    der Algorithmus ist ausbaufähig bzw.bei der Wegfindung zu beeinflussen.
    Es gibt die "schnelle" Lösung, die auch Umwege beinhalten kann, oder eine Lösung, welche den Weg etwas ausführlicher untersucht und daher ggf. kürzere Strecken zum Ziel findet (und damit auch ggf. länger sucht).

    In den Zeilen

    [autoit]

    $liste[$listenindex][0] = $kleinster_nachbar + $add + $abstand_zum_ziel ;gesamtgewicht
    $liste[$listenindex][0] = $abstand_zum_ziel ;gesamtgewicht

    [/autoit]

    kann man auswählen, welche Daten der einzelnen Wegpunkte in die Liste geschrieben und zur Findung des am nächsten liegenden möglichen Wegpunktes herangezogen werden.

    Dort wäre es bspw. auch möglich, "Berge" und "Autobahnen" einzubauen, die den Weg nicht völlig versperren bzw. den Weg zum Ziel verkürzen.
    autoit.de/wcf/attachment/20517/autoit.de/wcf/attachment/20522/

    UEZ, mir schwebt da eher eine Speicher/Ladefunktion des Labyrinth´s vor, Buttons dafür hats ja auf der GUI reichlich :D

    Zitat

    Cool wäre es, wenn man schwarze Linien zeichnen könnte

    Ich hatte mir schon überlegt, keine Buttons, sondern Pixel als Wegpunkte anzusteuern, dann wird die "Zeichenfunktion" automatisch nötig.
    Allerdings kann man hier bei entsprechend kleinen Feldern sehr schön mitverfolgen, wie der Algorithmus funktioniert. Das war die Intention.
    autoit.de/wcf/attachment/20527/autoit.de/wcf/attachment/20532/

  • Hab den auch mal in PHP benutzt ist recht praktisch bei vielen Dingen. Warum wertest du allerdings digonale Felder schlechte als horizontal und vertikale Felder, eigentlich müsst es umgekehrt sein, da du mit diagonalen Sprüngen mehr "Weg" zurücklegen kannst also mit einfacher horizontaler bzw. vertikaler Bewegung.

    Andy hat mir ein Schnitzel gebacken aber da war ein Raupi drauf und bevor Oscar das Bugfixen konnte kam Alina und gab mir ein AspirinJunkie.

  • Hi,

    Zitat

    Warum wertest du allerdings digonale Felder schlechte als horizontal und vertikale Felder, eigentlich müsst es umgekehrt sein, da du mit diagonalen Sprüngen mehr "Weg" zurücklegen kannst also mit einfacher horizontaler bzw. vertikaler Bewegung.

    Gute Frage, aber der "Wert" der zurückzulegenden Strecke ist imho die Entfernung. Und die ist bei einem diagonalen Sprung sqrt(2) also ca. 1,4 mal länger als ein horizontaler bzw. vertikaler Sprung. Und das stimmt auch, denn einmal nach rechts laufen und dann nach unten sind 2 Wegstrecke, während einmal diagonal gesprungen nur 1,4 Wegstrecke ist!

    Habe aber, damit die "Optik" stimmt, das Script etwas angepasst und auch eine Editierfunktion eingebaut.
    Man kann nun die Hindernisse mit einem Klick "löschen" und auch nach der Wegfindung das Labyrinth verändern.

    /EDIT/ geändertes Script im ersten Post

    ciao
    Andy


    "Schlechtes Benehmen halten die Leute doch nur deswegen für eine Art Vorrecht, weil keiner ihnen aufs Maul haut." Klaus Kinski
    "Hint: Write comments after each line. So you can (better) see what your program does and what it not does. And we can see what you're thinking what your program does and we can point to the missunderstandings." A-Jay

    Wie man Fragen richtig stellt... Tutorial: Wie man Script-Fehler findet und beseitigt...X-Y-Problem

    2 Mal editiert, zuletzt von Andy (5. April 2013 um 15:36)

  • Nur als Hinweis, man kann das Ziel wegklicken aber nicht neu setzen :)
    Aber sonst wirklich sehr gut! :thumbup: