Hi,
nachdem ein einzelnes Forenmitglied 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
Global $feldgroesse_x = 40
Global $feldgroesse_y = 30
Global $startx, $starty, $zielx, $ziely, $start = 0
Global $listenindex, $ziel_gefunden = 0
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
$w = 1200
$h = 900
$abstand = 1
$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)
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
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
$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
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
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... ")
; $optimum = Sqrt(($startx - $zielx) ^ 2 + ($starty - $ziely) ^ 2)
[/autoit] [autoit][/autoit] [autoit]$index_x = $startx
$index_y = $starty
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
Case 7 ;abbrechen
Exit
EndSwitch
Exit
EndIf
$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
$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)
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)
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
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
; MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @LF & '$inhalt' & @LF & @LF & 'Return:' & @LF & $inhalt) ;### Debug MSGBOX
Next
Next
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
$gesamt += $kleinster_nachbar
$x = $Kleinster_nachbar_x
$y = $Kleinster_nachbar_y
GUICtrlSetBkColor($feld[$Kleinster_nachbar_index], $blau)
;msgbox(0,0,$kleinster_nachbar)
WEnd
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.