Wegfindung

**Mars**

Moin,
Ich wusste nicht so recht, ob der Thread in H&U oder in Skripte gehört, denn eigentlich habe ich eine Frage
Da es aber schon ein funktionsfähiges (aber ziemlich primitives) Skript gibt habe ich mich für Skripte entschieden.

"Geschichte von Adam und Eva"

Da ich irgendwann mal wieder ein TD basteln möchte was ggf mehr kann als meine bisherigen brauche ich natürlich erstmal eine ganze Menge Funktionen die mir das ermöglichen. Eine davon ist die Wegfindungsfunktion. Sie soll im 2D Raum den kürzesten Weg vom Start zum Ziel finden. Diagonales Laufen ist nicht möglich. Andys A* Algo habe ich mir schon angesehen, aber nicht gänzlich verstanden (Er beinhaltet auch Diagonales gehen). Zudem möchte ich nicht mit Kanonen auf Spatzen schießen. Es handelt sich um ein kleines Spielfeld (im Endeffekt wird es zwischen 12x12 und 16x16 Felder groß, ggf auch nicht gleichseitig), daher wird kein Algo benötigt der unnötig komplex ist um bei großen Wegen Zeit zu sparen, der aber bei kleinen Wegen unnötigen Overhead mitführt.

Das Skript anbei findet schon den Weg in akzeptabeler Geschwindigkeit. Ich bin mir aber nicht sicher, ob mein Ansatz (annähernd) optimal ist. Da zusätzlich noch Rücksicht auf Hindernisse genommen werden muss, was ich noch nicht vollständig implementiert habe möchte ich vor dem Weiterbasteln wissen, ob es villeicht einen effizienteren Ansatz zum Ziel gibt. Dann würde ich mich diesem widmen und mein bisheriges Skript als kleine Übung abtun. Das Skript sollte leicht verständlich sein, sodass Schwächen schnell erkannt werden können. Daher bitte ich um eure Meinung

Hier mein kleiner Test:

Skript

[autoit]

#include <Array.au3>
#include <GDIPlus.au3>

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

Global $__aArea[1][1], $__aAreaMap[1][1], $__aAreaUx, $__aAreaUy, $__aAreaStart[2], $__aAreaZiel[2], $__aMap = $__aArea

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

; Nur zum Testen
Global $aLabel[1][1]

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

_Test()

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

Func _Test()
_GDIPlus_Startup()
Local $ix = 25, $iy = 25, $hBtn_Neu, $aStart[2], $aZiel[2], $t, $p, $aPosTest[2], $aBlock[2], $iMsg, $iTimer, $iTime, $iVersuche
Local $hGUI = GUICreate('Test', 400, 445), $hGFX = _GDIPlus_GraphicsCreateFromHWND($hGUI), $hBRU = _GDIPlus_BrushCreateSolid()
ReDim $aLabel[$iy][$ix]
_Area_SetSize($ix, $iy)
$hBtn_Neu = GUICtrlCreateButton('Neuer Weg', 10, 410, 100, 25)
GUISetState()
$iTimer = TimerInit()
While True
$iMsg = GUIGetMsg()
If TimerDiff($iTimer) > 1500 Then
$iMsg = $hBtn_Neu
$iTimer = TimerInit()
EndIf
Switch $iMsg
Case -3
ExitLoop
Case $hBtn_Neu
_Area_Reset()
_Area_SetSize($ix, $iy)
$aStart[0] = $ix - 1
$aZiel[0] = 0
$aStart[1] = $iy - 1
$aZiel[1] = 0
_Area_SetPath($aStart, $aZiel)
ConsoleWrite('Start: [' & $__aAreaStart[0] & '|' & $__aAreaStart[1] & ']')
ConsoleWrite(' - Ziel: [' & $__aAreaZiel[0] & '|' & $__aAreaZiel[1] & ']' & @CRLF)
For $i = 0 To Int(($ix ^ 2 + $iy ^ 2) ^ 0.5 / 2) Step 1
$aBlock[0] = Random(0, $ix - 1, 1)
$aBlock[1] = Random(0, $iy - 1, 1)
If ($aBlock[0] = $__aAreaStart[0] And $aBlock[1] = $__aAreaStart[1]) Or ($aBlock[0] = $__aAreaZiel[0] And $aBlock[1] = $__aAreaZiel[1]) Then
ContinueLoop
Else
_Area_SetTitle($aBlock[0], $aBlock[1], 1)
_Area_SetTitle($aBlock[0]+1, $aBlock[1], 1)
_Area_SetTitle($aBlock[0], $aBlock[1]+1, 1)
_Area_SetTitle($aBlock[0]+1, $aBlock[1]+1, 1)
_Area_SetTitle($aBlock[0]+2, $aBlock[1], 1)
_Area_SetTitle($aBlock[0], $aBlock[1]+2, 1)
_Area_SetTitle($aBlock[0]+2, $aBlock[1]+1, 1)
_Area_SetTitle($aBlock[0]+1, $aBlock[1]+2, 1)
_Area_SetTitle($aBlock[0]+2, $aBlock[1]+2, 1)
EndIf
Next
For $i = 0 To Int(($ix ^ 2 + $iy ^ 2) ^ 0.5 / 2) Step 1
$aBlock[0] = Random(0, $ix - 1, 1)
$aBlock[1] = Random(0, $iy - 1, 1)
If ($aBlock[0] = $__aAreaStart[0] And $aBlock[1] = $__aAreaStart[1]) Or ($aBlock[0] = $__aAreaZiel[0] And $aBlock[1] = $__aAreaZiel[1]) Then
ContinueLoop
Else
_Area_SetTitle($aBlock[0], $aBlock[1], 1)
_Area_SetTitle($aBlock[0]+1, $aBlock[1], 1)
_Area_SetTitle($aBlock[0], $aBlock[1]+1, 1)
_Area_SetTitle($aBlock[0]+1, $aBlock[1]+1, 1)
EndIf
Next
For $i = 0 To Int(($ix ^ 2 + $iy ^ 2) ^ 0.5 / 2) Step 1
$aBlock[0] = Random(0, $ix - 1, 1)
$aBlock[1] = Random(0, $iy - 1, 1)
If ($aBlock[0] = $__aAreaStart[0] And $aBlock[1] = $__aAreaStart[1]) Or ($aBlock[0] = $__aAreaZiel[0] And $aBlock[1] = $__aAreaZiel[1]) Then
ContinueLoop
Else
_Area_SetTitle($aBlock[0], $aBlock[1], 1)
EndIf
Next
For $i = 0 To $ix - 1 Step 1
For $e = 0 To $iy - 1 Step 1
If $__aArea[$e][$i] Then
DllCall($ghGDIPDll, "int", "GdipSetSolidFillColor", "handle", $hBRU, "dword", 0xFF404040)
Else
If $i = $aStart[0] And $e = $aStart[1] Then
DllCall($ghGDIPDll, "int", "GdipSetSolidFillColor", "handle", $hBRU, "dword", 0xFF4040DD)
ElseIf $i = $aZiel[0] And $e = $aZiel[1] Then
DllCall($ghGDIPDll, "int", "GdipSetSolidFillColor", "handle", $hBRU, "dword", 0xFFDD4040)
Else
DllCall($ghGDIPDll, "int", "GdipSetSolidFillColor", "handle", $hBRU, "dword", 0xFFD0D0D0)
EndIf
EndIf
DllCall($ghGDIPDll, "int", "GdipFillRectangleI", "handle", $hGFX, "handle", $hBRU, "int", $i * (400 / $ix), "int", $e * (400 / $iy), "int", (400 / $ix), "int", (400 / $iy))
Next
Next
_Area_Calc()
$t = TimerInit()
$p = _Area_FindPath()
$t = TimerDiff($t)
ConsoleWrite('Pfad: ' & $p & ' (' & Round($t, 2) & 'ms)' & @CRLF)
If Int(StringLeft($p, 3)) > 0 Then
$iTime += $t
$iVersuche += 1
ToolTip('Dauer: ' & Round($iTime / $iVersuche, 2) & 'ms')
EndIf
$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
DllCall($ghGDIPDll, "int", "GdipSetSolidFillColor", "handle", $hBRU, "dword", 0xFF154015 + Int('0xFF' & Hex(Int(($i*0.75)^0.8), 2) & Hex(Int(($i*2)^0.83), 2) & Hex(Int(($i*0.75)^0.8), 2)))
DllCall($ghGDIPDll, "int", "GdipFillRectangleI", "handle", $hGFX, "handle", $hBRU, "int", $aPosTest[0] * (400 / $ix), "int", $aPosTest[1] * (400 / $iy), "int", (400 / $ix), "int", (400 / $iy))
Next
EndSwitch
WEnd
_GDIPlus_BrushDispose($hBRU)
_GDIPlus_GraphicsDispose($hGFX)
_GDIPlus_Shutdown()
EndFunc ;==>_Test

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

Func _Area_FindPath()
$__aMap = $__aArea
Return __Area_FindPathRec()
EndFunc

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

Func __Area_FindPathRec($aPos = $__aAreaStart, $aPosLast = $__aAreaStart)
Local $aList = __Area_GetRichtung($aPos, $aPosLast), $tPos[2], $sTemp, $iSum = 1*($aList[0][1] > 0) + 1*($aList[1][1] > 0) + 1*($aList[2][1] > 0) + 1*($aList[3][1] > 0)
If $iSum < 2 Then
$__aMap[$aPos[1]][$aPos[0]] += 1
If $iSum = 0 Then Return -1
EndIf
__Area_SortArray2D($aList)
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]
$aPosLast = $aPos
$sTemp = __Area_FindPathRec($tPos, $aPosLast)
If $sTemp > 0 Then Return $aList[$i][0] & $sTemp
Next
EndFunc ;==>_Area_FindPath

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

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

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

Func __Area_GetRichtung($aPos, $aPosLast)
Local $a[4][2] = [[1],[2],[3],[4]] ; LORU
If ($aPos[0] > 0) And Not $__aMap[$aPos[1]][$aPos[0] - 1] And Not ((($aPos[0] - 1) = $aPosLast[0]) And ($aPos[1] = $aPosLast[1])) Then $a[0][1] = $__aAreaMap[$aPos[1]][$aPos[0] - 1]
If ($aPos[1] > 0) And Not $__aMap[$aPos[1] - 1][$aPos[0]] And Not (($aPos[0] = $aPosLast[0]) And (($aPos[1] - 1) = $aPosLast[1])) Then $a[1][1] = $__aAreaMap[$aPos[1] - 1][$aPos[0]]
If ($aPos[0] < $__aAreaUx - 1) And Not $__aMap[$aPos[1]][$aPos[0] + 1] And Not ((($aPos[0] + 1) = $aPosLast[0]) And ($aPos[1] = $aPosLast[1])) Then $a[2][1] = $__aAreaMap[$aPos[1]][$aPos[0] + 1]
If ($aPos[1] < $__aAreaUy - 1) And Not $__aMap[$aPos[1] + 1][$aPos[0]] And Not (($aPos[0] = $aPosLast[0]) And (($aPos[1] + 1) = $aPosLast[1])) Then $a[3][1] = $__aAreaMap[$aPos[1] + 1][$aPos[0]]
Return $a
EndFunc ;==>__Area_GetRichtung

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

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
$__aAreaMap[$y][$x] = (($__aAreaZiel[0] - $x) ^ 2 + ($__aAreaZiel[1] - $y) ^ 2) ^ 0.5 + 1
Next
Next
EndFunc ;==>_Area_Calc

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

Func _Area_SetPath($aStart, $aZiel)
$__aAreaStart = $aStart
$__aAreaZiel = $aZiel
EndFunc ;==>_Area_SetPath

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

Func _Area_SetTitle($x, $y, $bBlocked)
If $x < $__aAreaUx And $y < $__aAreaUy Then $__aArea[$y][$x] = $bBlocked
EndFunc ;==>_Area_SetTitle

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

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

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

Func _Area_SetSize($x, $y)
_Area_Reset()
ReDim $__aArea[$y][$x]
$__aAreaMap = $__aArea
$__aAreaUx = $x
$__aAreaUy = $y
EndFunc ;==>_Area_SetSize

[/autoit]

Edit: Hier mal das was ich bisher habe. Nach meiner Überprüfung findet die Funktion immer einen Weg, sofern einer existiert. (aber nur selten den optimalen, was aber nicht weiter schlimm ist). Wie kann man verifizieren, dass dies tatsächlich der Fall ist ? Habe hunderte Male den Weg in einer Zufallslandschaft finden lassen, und beim Fehlschlag immer visuell festgestellt, dass kein Weg möglich war. Leider sind 100 Beispiele kein Beweis.

lg
Mars

**Andy**

Hi,
beim A*-Algo musst du einfach nur das "diagonale" Gehen weglassen^^

Letztendlich läuft es darauf hinaus, jedes Feld des Spielfelds vom Start ausgehend zu bewerten und diese Werte zu addieren. Am Ziel angekommen geht man dann rückwärts auf dem "kürzesten" Weg, d.h. immer zum Feld mit dem kleinsten Wert. Das Prinzip ist sehr einfach.
Bei einem TD mit mehreren Creeps würde ich es so machen, dass zusätzlich zum Wert des Feldes auch noch das "Gewicht" des Creeps mit addiert wird. Dann würde ein von einem Creep besetztes Feld nur im absoluten Notfall mehrfach besetzt werden, trotzdem wäre aber ein Stau vermeidbar bzw, ggf wäre ein längerer Weg einem Stau vorzuziehen.

Bei deinem Beispiel sieht der Weg länger aus als er ist, da nicht der "gerade" Weg zum Ziel genommen wird^^.
Das war auch bei meinem A* Algo so, das konnte ich aber über die Bewertung der Diagonalen einstellen.
Da bei dir nur Waagrecht und Senkrecht gegangen werden kann, solltest du das Feld, das auf der "Luftlinie" zum Ziel liegt, bei gleichem Wert vorziehen....So läuft die Figur auch "diagonal" über das Spielfeld, statt bspw. ganz nach unten und dann ganz nach rechts zu laufen. Der eigentliche Weg ist zwar genauso lang, aber es sieht einfach doof aus^^

Texos

Du hast die ganzen Fields doch in einem Array gespeichert? Wenn nicht, ab ins Array damit.(x,y)
[0]=x
[1]=y
[2]=begehbar oder nicht

Jedes Feld das eingefügt wird und das "begehbar" ist, im Array den Indexwert [2] auf True setzen, ansonsten False
Da es ja nur eine Wegstrecke gibt, kannst du dann ganz einfach immer den Wert True auslesen und ein Neues Array mit den Koords anlegen.

Hoffe habe nix übersehen

Lg

**Mars**

Wie ich weiter verfahre weiß ich schon^^
Also das mit Blockierten Wegen ist schon geplant.
Und Andy zuliebe ersetzen wir die 1-Norm durch die 2-Norm

[autoit]

(($__aAreaZiel[0] - $x) ^ 2 + ($__aAreaZiel[1] - $y) ^ 2) ^ 0.5 + 1

[/autoit]

Spoiler anzeigen

[autoit]

#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]

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

_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)

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

$hBtn_Neu = GUICtrlCreateButton('Neuer Weg', 10, 410, 100, 25)

[/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

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

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
_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)

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

$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

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

EndSwitch
WEnd

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

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

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

;~ 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)

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

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

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

If $tPos[0] = $__aAreaZiel[0] And $tPos[1] = $__aAreaZiel[1] Then Return $aList[$i][0]
$sPath = $aList[$i][0]

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

;~ Sleep(500)
;~ GUICtrlSetBkColor($aLabel[$tPos[1]][$tPos[0]], 0x40DD40)

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

;~ 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

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

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

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

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

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

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
$__aAreaMap[$y][$x] = (($__aAreaZiel[0] - $x) ^ 2 + ($__aAreaZiel[1] - $y) ^ 2) ^ 0.5 + 1
Next
Next
EndFunc ;==>_Area_Calc

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

Func _Area_SetPath($aStart, $aZiel)
$__aAreaStart = $aStart
$__aAreaZiel = $aZiel
EndFunc ;==>_Area_SetPath

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

Func _Area_SetTitle($x, $y, $bBlocked)
If $x < $__aAreaUx And $y < $__aAreaUy Then $__aArea[$y][$x] = $bBlocked
EndFunc ;==>_Area_SetTitle

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

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

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

Func _Area_SetSize($x, $y)
_Area_Reset()
ReDim $__aArea[$y][$x]
$__aAreaMap = $__aArea
$__aAreaUx = $x
$__aAreaUy = $y
EndFunc ;==>_Area_SetSize

[/autoit]

Edit:
Es ging eigentlich darum, ob es einen effizienteren Ansatz gibt. Verwendet wird: Gewichtung und anschließendes Entscheiden.

lg
Mars

**Andy**

Mars, anbei habe ich Hindernisse eingefügt, allerdings steigt dann ab und zu die Func __Area_GetRichtung() mit Rekursionsoverflow aus...

Spoiler anzeigen

[autoit]

#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]

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

_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)

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

$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

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

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

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

_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

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

$t = TimerInit()
$p = _Area_FindPath()
$t = TimerDiff($t)
ConsoleWrite('Pfad: ' & $p & ' (' & Round($t, 2) & 'ms)' & @CRLF)

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

$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

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

EndSwitch
WEnd

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

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

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

;~ 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)

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

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

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

If $tPos[0] = $__aAreaZiel[0] And $tPos[1] = $__aAreaZiel[1] Then Return $aList[$i][0]
$sPath = $aList[$i][0]

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

;~ Sleep(500)
;~ GUICtrlSetBkColor($aLabel[$tPos[1]][$tPos[0]], 0x40DD40)

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

;~ 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

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

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

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

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

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

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

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

Func _Area_SetPath($aStart, $aZiel)
$__aAreaStart = $aStart
$__aAreaZiel = $aZiel
EndFunc ;==>_Area_SetPath

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

Func _Area_SetTitle($x, $y, $bBlocked)
If $x < $__aAreaUx And $y < $__aAreaUy Then $__aArea[$y][$x] = $bBlocked
EndFunc ;==>_Area_SetTitle

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

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

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

Func _Area_SetSize($x, $y)
_Area_Reset()
ReDim $__aArea[$y][$x]
$__aAreaMap = $__aArea
$__aAreaUx = $x
$__aAreaUy = $y
EndFunc ;==>_Area_SetSize

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

//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.

**Mars**

Hmm... iwie läuft das nicht Absturzfrei. Umwege werden automatisch nicht benutzt (in deiner Version).

Hab hier mal den Prototyp. Der findet (nicht immer, aber immer öfter :D) den richtigen Weg mit Hindernissen.
Allerdings wird nicht immer der kürzeste Weg benutzt, sondern der erste der gefunden wird (nicht weiter schlimm, so ist das TD wenigstens etwas abwechselungsreicher^^)
Ab und an frisst er sich noch fest, da muss ich noch basteln.
Weiterhin wird noch eine Optimierung nachgeschaltet, da er an Hindernissen öfters mal unnötige Umwege geht.
Einfach mal drüberschauen, obs so genehm ist.
Mich würde dann auch ein vergleich zum A+ Algo interessieren, kann man den da iwie einfach einbauen ? (ohne Diagonalen)
PS: Das ist übrigens der effizienteste Weg zum Ziel
[Blockierte Grafik: http://i.imgur.com/1nQ2c2m.jpg]

Spoiler anzeigen

[autoit]

#include <Array.au3>

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

Global $__aArea[1][1], $__aAreaMap[1][1], $__aAreaUx, $__aAreaUy, $__aAreaStart[2], $__aAreaZiel[2], $__aMap = $__aArea

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

; Nur zum Testen
Global $aLabel[1][1]

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

_Test()

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

Func _Test()
Local $ix = 10, $iy = 10, $hBtn_Neu, $aStart[2], $aZiel[2], $t, $p, $aPosTest[2], $aBlock[2]
Local $hGUI = GUICreate('Test', 400, 445)
ReDim $aLabel[$iy][$ix]
_Area_SetSize($ix, $iy)

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

$hBtn_Neu = GUICtrlCreateButton('Neuer Weg', 10, 410, 100, 25)

[/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

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

GUISetState()

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

While True
Switch GUIGetMsg()
Case -3
Exit
Case $hBtn_Neu
_Area_Reset()
_Area_SetSize($ix, $iy)
$aStart[0] = $ix - 1
$aZiel[0] = 0
$aStart[1] = $iy - 1
$aZiel[1] = 0
;~ Do
;~ $aStart[0] = Random(0, $ix - 1, 1)
;~ $aZiel[0] = Random(0, $ix - 1, 1)
;~ $aStart[1] = Random(0, $iy - 1, 1)
;~ $aZiel[1] = Random(0, $iy - 1, 1)
;~ Until (Abs($aStart[0] - $aZiel[0]) + Abs($aStart[1] - $aZiel[1])) > (($ix ^ 2 + $iy ^ 2) ^ 0.5 / 2)
_Area_SetPath($aStart, $aZiel)
ConsoleWrite('Start: [' & $__aAreaStart[0] & '|' & $__aAreaStart[1] & ']')
ConsoleWrite(' - Ziel: [' & $__aAreaZiel[0] & '|' & $__aAreaZiel[1] & ']' & @CRLF)
For $i = 0 To Int(($ix ^ 2 + $iy ^ 2) ^ 0.5 * 1.5) Step 1
$aBlock[0] = Random(0, $ix - 1, 1)
$aBlock[1] = Random(0, $iy - 1, 1)
If ($aBlock[0] = $__aAreaStart[0] And $aBlock[1] = $__aAreaStart[1]) Or ($aBlock[0] = $__aAreaZiel[0] And $aBlock[1] = $__aAreaZiel[1]) Then
;~ ConsoleWrite($aBlock[0] & '|' & $aBlock[1] & @CRLF)
ContinueLoop
Else
_Area_SetTitle($aBlock[0], $aBlock[1], 1)
EndIf
Next
For $i = 0 To $ix - 1 Step 1
For $e = 0 To $iy - 1 Step 1
If $__aArea[$e][$i] Then
GUICtrlSetBkColor($aLabel[$e][$i], 0x404040)
Else
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
EndIf
Next
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)
;~ Sleep(1000)

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

$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

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

EndSwitch
WEnd

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

EndFunc ;==>_Test

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

Func _Area_FindPath()
$__aMap = $__aArea
Return __Area_FindPathRec()
EndFunc

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

Func __Area_FindPathRec($aPos = $__aAreaStart, $aPosLast = $__aAreaStart)
If $aPos[0] = $__aAreaZiel[0] And $aPos[1] = $__aAreaZiel[1] Then Return
Local $sPath = ''
Local $aList = __Area_GetRichtung($aPos, $aPosLast), $tPos[2], $sTemp
__Area_SortArray2D($aList)
;~ If $aList[0][1] = 1 Then Return

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

;~ 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] & ': ' & Round($aList[$i][1], 1) & @CRLF)
;~ Next
;~ ConsoleWrite(@CRLF)

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

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

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

If $tPos[0] = $__aAreaZiel[0] And $tPos[1] = $__aAreaZiel[1] Then Return $aList[$i][0]
$sPath = $aList[$i][0]
$aPosLast = $aPos

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

;~ Sleep(100)
;~ ConsoleWrite
;~ If Not $__aMap[$tPos[1]][$tPos[0]] Then GUICtrlSetBkColor($aLabel[$tPos[1]][$tPos[0]], 0x408D8D + _012() * 0x3030)

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

;~ ConsoleWrite('Map: ' & $__aMap[$aPos[1]][$aPos[0]] & @CRLF)

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

$sTemp = __Area_FindPathRec($tPos, $aPosLast)
;~ ConsoleWrite($sTemp & @CRLF)
If $sTemp > 0 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

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

Func _012()
Local Static $012 = 0
$012 += 1
If $012 = 3 Then $012 = 0
Return $012
EndFunc ;==>_012

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

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

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

Func __Area_GetRichtung($aPos, $aPosLast)
Local $a[4][2] = [[1],[2],[3],[4]] ; LORU
If ($aPos[0] > 0) And Not $__aMap[$aPos[1]][$aPos[0] - 1] And Not ((($aPos[0] - 1) = $aPosLast[0]) And ($aPos[1] = $aPosLast[1])) Then $a[0][1] = $__aAreaMap[$aPos[1]][$aPos[0] - 1]
If ($aPos[1] > 0) And Not $__aMap[$aPos[1] - 1][$aPos[0]] And Not (($aPos[0] = $aPosLast[0]) And (($aPos[1] - 1) = $aPosLast[1])) Then $a[1][1] = $__aAreaMap[$aPos[1] - 1][$aPos[0]]
If ($aPos[0] < $__aAreaUx - 1) And Not $__aMap[$aPos[1]][$aPos[0] + 1] And Not ((($aPos[0] + 1) = $aPosLast[0]) And ($aPos[1] = $aPosLast[1])) Then $a[2][1] = $__aAreaMap[$aPos[1]][$aPos[0] + 1]
If ($aPos[1] < $__aAreaUy - 1) And Not $__aMap[$aPos[1] + 1][$aPos[0]] And Not (($aPos[0] = $aPosLast[0]) And (($aPos[1] + 1) = $aPosLast[1])) Then $a[3][1] = $__aAreaMap[$aPos[1] + 1][$aPos[0]]
If 1*($a[0][1] <> '') + 1*($a[1][1] <> '') + 1*($a[2][1] <> '') + 1*($a[3][1] <> '') <= 1 Then $__aMap[$aPos[1]][$aPos[0]] += 1
Return $a
EndFunc ;==>__Area_GetRichtung

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

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
$__aAreaMap[$y][$x] = (($__aAreaZiel[0] - $x) ^ 2 + ($__aAreaZiel[1] - $y) ^ 2) ^ 0.5 + 1
Next
Next
EndFunc ;==>_Area_Calc

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

Func _Area_SetPath($aStart, $aZiel)
$__aAreaStart = $aStart
$__aAreaZiel = $aZiel
EndFunc ;==>_Area_SetPath

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

Func _Area_SetTitle($x, $y, $bBlocked)
If $x < $__aAreaUx And $y < $__aAreaUy Then $__aArea[$y][$x] = $bBlocked
EndFunc ;==>_Area_SetTitle

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

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

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

Func _Area_SetSize($x, $y)
_Area_Reset()
ReDim $__aArea[$y][$x]
$__aAreaMap = $__aArea
$__aAreaUx = $x
$__aAreaUy = $y
EndFunc ;==>_Area_SetSize

[/autoit]

Normales Wegfinden dauert bei mir im Schnitt 1-3ms. Ob überhaupt ein Weg existiert merkt die Mühle nach 0-20ms (je nachdem ob die Blockade nah am Start oder nah am Ziel ist)
lg
Mars

**Andy**

Hi,
der "Fehler" liegt bei dir im System.
Du berechnest einfach den "Abstand" aller Felder zum Start. Das führt dann dazu, dass (s. Bild oben links kurz nach dem Start) das Feld mit dem Wert 3.2 zweimal vorkommt, obwohl der Weg zum 2. Feld mit Wert 3.2 wesentlich länger ist, da man um das geblockte Feld 2.4 herumlaufen muss.

Zitat von Mars

Mich würde dann auch ein vergleich zum A+ Algo interessieren, kann man den da iwie einfach einbauen ? (ohne Diagonalen)

Anbei mein A*-Script, es hat lediglich eine Zeile ergänzt werden müssen, um nur "gerade" zu laufen^^ (Zeile 226 auskommentieren um auch schräge Wege zu gehen)
// EDIT Die Hindernisse müssen in diesem Fall an den Ecken geschlossen sein
// wer mag, kann in Zeile 204 nach dem GuiDtrlSetData() noch ein sleep(100) einfügen, dann kann man nachvollziehen, welchen Weg der Algorithmus läuft

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
;~ If ($yy = $y - 1 And ($xx = $x - 1 Or $xx = $x + 1)) Or ($yy = $y + 1 And ($xx = $x - 1 Or $xx = $x + 1)) Then continueloop;diagonal
$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

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

$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
;**********************FÜR DIAGONALEN WEG AUSKOMMENTIEREN*********
;~ If ($yy = $y - 1 And ($xx = $x - 1 Or $xx = $x + 1)) Or ($yy = $y + 1 And ($xx = $x - 1 Or $xx = $x + 1)) Then ContinueLoop;diagonal
;*****************************************************************
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]

Es werden auf dem Hinweg die "diagonalen" Felder berechnet, allerdings werden auf dem Rückweg nur die geraden Felder zum Laufen herangezogen.
Wenn ich Lust und Laune habe erstelle ich eine "schnelle" Version unter Verwendung einer Struct^^...worauf das dann hinausläuft sollte den üblichen Verdächtigen bekannt sein

//EDIT Habe in meinem Script den "inner Loop" verifiziert. Mit AutoIt dauert die Wegfindung je nach Labyrinthgröße bei 1000 überprüften Feldern ca. 1 Sekunde, also über den dicken Daumen 1-2Millisekunden pro überprüftem Feld mit der Funktion suche_Nachbar(). Mal schauen, inwieweit man das noch optimieren kann. Da die 8 Felder um den Mittelpunkt untersucht werden müssen, bieten sich 2 SSE-Register an.
Btw. wenn man eine universelle A*-Funktion erstellen würde, müsste man nur eine komplette Beschreibung des Labyrinths (als Bitmap?) mit Festlegung von Start und Ziel und den Hindernissen erstellen und diese Bitmap dann incl. kürzestem Weg zurückgeben. Eine Bitmap bietet sich an, da in deren Header schon die Daten des Labyrinths enthalten sind, ausserdem ist sie mit jedem gängigen Programm erstellbar!

**Mars**

Ich hab schon n guten Plan wie man einen Algo bauen könnte, der gleichzeitig alle kürzesten Wege findet.
Vom Start und Ziel aus jeweils immer ein Feld weitergehen und demnach die Gewichtung vornehmen.
Anschließend die beiden Arrays (Structs) addieren. Die kürzesten Wege haben dann immer die gleiche Nummer. Dann kann man zusätzlich noch Abzweigungen und Wahrscheinlichkeiten einbauen
Mal schauen ob ich das heute Abend noch hinbekomme, scheint mir eigentlich recht simpel zu sein. Die Effizienz ist dabei wahrscheinlich nicht so berauschend, aber da das Verfahren sehr einfach ist kann ich das ja auch mal in ASM probieren

lg
Mars