Mars, anbei habe ich Hindernisse eingefügt, allerdings steigt dann ab und zu die Func __Area_GetRichtung() mit Rekursionsoverflow aus... ![]()
Spoiler anzeigen
#include <Array.au3>
[/autoit] [autoit][/autoit] [autoit]Global $__aArea[1][1], $__aAreaMap[1][1], $__aAreaUx, $__aAreaUy, $__aAreaStart[2], $__aAreaZiel[2]
[/autoit] [autoit][/autoit] [autoit]; Nur zum Testen
Global $aLabel[1][1]
_Test()
[/autoit] [autoit][/autoit] [autoit]Func _Test()
Local $ix = 10, $iy = 10, $hBtn_Neu, $aStart[2], $aZiel[2], $t, $p, $aPosTest[2]
Local $hGUI = GUICreate('Test', 400, 445)
ReDim $aLabel[$iy][$ix]
_Area_SetSize($ix, $iy)
$hBtn_Neu = GUICtrlCreateButton('Neuer Weg', 10, 410, 100, 25)
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]For $i = 0 To $ix - 1 Step 1
For $e = 0 To $iy - 1 Step 1
$aLabel[$e][$i] = GUICtrlCreateLabel('', $i * (400 / $ix), $e * (400 / $iy), (400 / $ix), (400 / $iy), 0x0201)
GUICtrlSetBkColor(-1, 0xD0D0D0 + IsInt(($e + $i) / 2) * 0x101010)
Next
Next
GUISetState()
[/autoit] [autoit][/autoit] [autoit]While True
Switch GUIGetMsg()
Case -3
Exit
Case $hBtn_Neu
Do
For $i = 0 To 1 Step 1
$aStart[$i] = Random(0, $ix - 1, 1)
$aZiel[$i] = Random(0, $ix - 1, 1)
Next
Until (Abs($aStart[0] - $aZiel[0]) + Abs($aStart[1] - $aZiel[1])) > (($ix ^ 2 + $iy ^ 2) ^ 0.5 / 2)
_Area_SetPath($aStart, $aZiel)
For $i = 0 To $ix - 1 Step 1
For $e = 0 To $iy - 1 Step 1
If $i = $aStart[0] And $e = $aStart[1] Then
GUICtrlSetBkColor($aLabel[$e][$i], 0x4040DD)
ElseIf $i = $aZiel[0] And $e = $aZiel[1] Then
GUICtrlSetBkColor($aLabel[$e][$i], 0xDD4040)
Else
GUICtrlSetBkColor($aLabel[$e][$i], 0xD0D0D0)
EndIf
Next
Next
For $y = 0 To $iy - 1 Step 1 ;Hindernisse festlegen
If $y = 2 Then ContinueLoop
$__aAreaMap[$y][5] = 1000
Next
_Area_Calc()
For $i = 0 To $ix - 1 Step 1
For $e = 0 To $iy - 1 Step 1
GUICtrlSetData($aLabel[$e][$i], Round($__aAreaMap[$e][$i], 1))
Next
Next
$t = TimerInit()
$p = _Area_FindPath()
$t = TimerDiff($t)
ConsoleWrite('Pfad: ' & $p & ' (' & Round($t, 2) & 'ms)' & @CRLF)
$aPosTest = $__aAreaStart
$p = StringSplit($p, '', 2)
For $i = 0 To UBound($p) - 2 Step 1
Switch $p[$i]
Case 1 ; Links
$aPosTest[0] -= 1
Case 2 ; Oben
$aPosTest[1] -= 1
Case 3 ; Rechts
$aPosTest[0] += 1
Case 4 ; Unten
$aPosTest[1] += 1
EndSwitch
GUICtrlSetBkColor($aLabel[$aPosTest[1]][$aPosTest[0]], 0x40DD40)
Next
EndSwitch
WEnd
EndFunc ;==>_Test
[/autoit] [autoit][/autoit] [autoit]Func _Area_FindPath($aPos = $__aAreaStart)
If $aPos[0] = $__aAreaZiel[0] And $aPos[1] = $__aAreaZiel[1] Then Return
Local $sPath = ''
Local $aList = __Area_GetRichtung($aPos), $tPos[2], $sTemp
__Area_SortArray2D($aList)
;~ If $aList[0][1] = 1 Then Return
;~ ConsoleWrite('Pos: [' & $aPos[0] & '|' & $aPos[1] & ']' & @CRLF)
;~ For $i = 0 To UBound($aList) - 1 Step 1
;~ If $aList[$i][1] Then ConsoleWrite($aList[$i][0] & ': ' & $aList[$i][1] & @CRLF)
;~ Next
;~ ConsoleWrite(@CRLF)
For $i = 0 To UBound($aList) - 1 Step 1
If Not $aList[$i][1] Then ContinueLoop
$tPos = $aPos
Switch $aList[$i][0]
Case 1 ; Links
$tPos[0] -= 1
Case 2 ; Oben
$tPos[1] -= 1
Case 3 ; Rechts
$tPos[0] += 1
Case 4 ; Unten
$tPos[1] += 1
EndSwitch
If $tPos[0] = $__aAreaZiel[0] And $tPos[1] = $__aAreaZiel[1] Then Return $aList[$i][0]
$sPath = $aList[$i][0]
;~ Sleep(500)
;~ GUICtrlSetBkColor($aLabel[$tPos[1]][$tPos[0]], 0x40DD40)
;~ ConsoleWrite('tPos: [' & $tPos[0] & '|' & $tPos[1] & ']' & @CRLF)
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]$sTemp = _Area_FindPath($tPos)
If Not ($sTemp = -1) Then Return $sPath & $sTemp
;~ If $aList[$i][1] Then ConsoleWrite($aList[$i][0] & ': ' & $aList[$i][1] & @CRLF)
Next
If Not $sPath Then
;~ _ArrayDisplay($aList)
Return -1
EndIf
EndFunc ;==>_Area_FindPath
Func __Area_SortArray2D(ByRef $a)
Local $c[2], $t[2]
For $i = 0 To UBound($a) - 1 Step 1
$t[0] = $a[$i][0]
$t[1] = $a[$i][1]
For $e = $i - 1 To 0 Step -1
$c[0] = $a[$e][0]
$c[1] = $a[$e][1]
If $t[1] >= $c[1] Then ExitLoop
$a[$e + 1][0] = $c[0]
$a[$e + 1][1] = $c[1]
Next
$a[$e + 1][0] = $t[0]
$a[$e + 1][1] = $t[1]
Next
EndFunc ;==>__Area_SortArray2D
Func __Area_GetRichtung($aPos)
Local $a[4][2] = [[1],[2],[3],[4]] ; LORU
If $aPos[0] > 0 Then $a[0][1] = $__aAreaMap[$aPos[1]][$aPos[0] - 1]
If $aPos[1] > 0 Then $a[1][1] = $__aAreaMap[$aPos[1] - 1][$aPos[0]]
If $aPos[0] < $__aAreaUx - 1 Then $a[2][1] = $__aAreaMap[$aPos[1]][$aPos[0] + 1]
If $aPos[1] < $__aAreaUy - 1 Then $a[3][1] = $__aAreaMap[$aPos[1] + 1][$aPos[0]]
Return $a
EndFunc ;==>__Area_GetRichtung
Func _Area_Calc()
If Not ($__aAreaStart[0] < $__aAreaUx And $__aAreaStart[1] < $__aAreaUy And $__aAreaZiel[0] < $__aAreaUx And $__aAreaZiel[1] < $__aAreaUy) Then Return -1
For $x = 0 To $__aAreaUx - 1 Step 1
For $y = 0 To $__aAreaUy - 1 Step 1
If $__aAreaMap[$y][$x] <> 1000 Then
$__aAreaMap[$y][$x] = (($__aAreaZiel[0] - $x) ^ 2 + ($__aAreaZiel[1] - $y) ^ 2) ^ 0.5 + 1
EndIf
Next
Next
EndFunc ;==>_Area_Calc
Func _Area_SetPath($aStart, $aZiel)
$__aAreaStart = $aStart
$__aAreaZiel = $aZiel
EndFunc ;==>_Area_SetPath
Func _Area_SetTitle($x, $y, $bBlocked)
If $x < $__aAreaUx And $y < $__aAreaUy Then $__aArea[$y][$x] = $bBlocked
EndFunc ;==>_Area_SetTitle
Func _Area_Reset()
ReDim $__aArea[1][1]
$__aArea[0][0] = ''
$__aAreaMap = $__aArea
$__aAreaUx = 1
$__aAreaUy = 1
$__aAreaStart[0] = ''
$__aAreaStart[1] = ''
$__aAreaZiel[0] = ''
$__aAreaZiel[1] = ''
EndFunc ;==>_Area_Reset
Func _Area_SetSize($x, $y)
_Area_Reset()
ReDim $__aArea[$y][$x]
$__aAreaMap = $__aArea
$__aAreaUx = $x
$__aAreaUy = $y
EndFunc ;==>_Area_SetSize
//EDIT
ahhh, habe mir das mal genauer angeschaut, du errechnest nicht von jedem freien Feld den Abstand sondern gehst davon aus, dass der Weg Hindernisfrei ist
Wieso du dir aber dermassen die Finger brichst weiss ich nicht
Starte am Start
Springe auf jedes freie Nachbarfeld und notiere dort den Abstand zum bereits berechneten Feld (plus dessen Wert) , dieses ist der "Wert" des neuen Feldes
Fülle so das gesamte Spielfeld aus
Gehe vom Ziel aus immer auf das nächste Feld mit dem kleinsten Wert, bis du bei Start bist
Texos, du hast den Algorithmus nicht verstanden...Wenn das Feld einen bestimmten Wert hat , dann musst du nicht in einem weiteren Array oder Index diesen Wert nochmal speichern.
Wenn ein Feld bspw den Wert 1000 hat, dann wird dort nie "hingelaufen", weil alle anderen angrenzenden Felder einen kleineren Wert haben.