Pathing Bot. Волновой алгоритм перемещения в ммо играх.
- Автор темы Belfigor
- Дата начала
C2H5OH
AutoIT Гуру
- Сообщения
- 1,473
- Репутация
- 333
Раз тема так читаема, выложу мой последний вариант функции нахождения пути.
Функция получает на вход двумерный массив-карту, координаты начала пути и координаты конца пути. На выходе массив направлений перемещения на каждом шаге пути - "n","ne","e",... (0-ой элемент в массиве пути не используется, шаги находятся в ячейках начиная с 1-ой). Легенда карты оставлена как у ТС, так как для моих задач поля 100х100 клеток вполне достаточно (100255 - стена, 100254 - пустая клетка, 100253 - начало пути). Для карт бОльшего размера константы должны быть изменены с учётом размера поля.
Использование переходов по диагонали содержит грабли. При необходимости перемещения по прямой (строго по вертикали или строго по горизонтали), бот вдруг идёт в обход - половину пути по одной диагонали, половину пути по другой диагонали. В приложенной функции приоритет отдаётся недиагональным перемещениям. То есть если из данной клетки можно пойти по горизонтали и по диагонали, то будет выбран переход по горизонтали.
Код:
Func FindWay($GeoMap,$x_start, $y_start,$x_finish, $y_finish)
Local $temp
Local $y_Max = UBound($GeoMap,2)-1, $x_Max = UBound($GeoMap,1)-1
Local $Nk = ($xMax+1)*($yMax+1)-1
Local $start = 0, $Ni = 0
Local $aWay[1]=[0]
$GeoMap[$x_start][$y_start] = 100253
$GeoMap[$x_finish][$y_finish] = 0
While $Ni < $Nk
For $y = 0 To $y_Max
For $x = 0 To $x_Max
If $GeoMap[$x][$y] = $Ni Then
For $i = -1 To 1
If $x+$i<0 Then ContinueLoop
If $x+$i>$x_Max Then ContinueLoop
For $j = -1 To 1
If $y+$j<0 Then ContinueLoop
If $y+$j>$y_Max Then ContinueLoop
If $GeoMap[$x+$i][$y+$j] = 100254 Then
$GeoMap[$x+$i][$y+$j] = $Ni+1
EndIf
If $GeoMap[$x+$i][$y+$j] = 100253 Then
;ToolTip("путь построен",0,0)
$x += $i
$y += $j
ExitLoop(5)
EndIf
Next
Next
EndIf
Next
Next
$Ni = $Ni+1
WEnd
If $Ni = $Nk Then
;ToolTip("путь не найден")
SetError(1)
Return $aWay
EndIf
Local $kletki[9],$kletki2[9]
Local $SuperMax = $Nk+2
While 1
For $i=0 To 8
$kletki[$i] = $SuperMax
Next
For $i = -1 To 1
If $x+$i<0 Then ContinueLoop
If $x+$i>$x_Max Then ContinueLoop
For $j = -1 To 1
If $y+$j<0 Then ContinueLoop
If $y+$j>$y_Max Then ContinueLoop
$kletki[4 + $j*3 + $i] = $GeoMap[$x+$i][$y+$j]
Next
Next
$kletki2 = $kletki
For $i=0 To 8 Step 2
$kletki2[$i] = $SuperMax
Next
$index = _ArrayMinIndex($kletki)
$index2 = _ArrayMinIndex($kletki2)
If $kletki[$index] < $kletki[$index2] Then $index2 = $index
Switch $index2
Case 0
_ArrayAdd($aWay,"nw")
$x -= 1
$y -= 1
Case 1
_ArrayAdd($aWay,"n")
$y -= 1
Case 2
_ArrayAdd($aWay,"ne")
$x += 1
$y -= 1
Case 3
_ArrayAdd($aWay,"w")
$x -= 1
Case 5
_ArrayAdd($aWay,"e")
$x += 1
Case 6
_ArrayAdd($aWay,"sw")
$x -= 1
$y += 1
Case 7
_ArrayAdd($aWay,"s")
$y += 1
Case 8
_ArrayAdd($aWay,"se")
$x += 1
$y += 1
Case Else
;ToolTip("Пришли")
ExitLoop
EndSwitch
WEnd
Return $aWay
EndFuncИспользование переходов по диагонали содержит грабли. При необходимости перемещения по прямой (строго по вертикали или строго по горизонтали), бот вдруг идёт в обход - половину пути по одной диагонали, половину пути по другой диагонали. В приложенной функции приоритет отдаётся недиагональным перемещениям. То есть если из данной клетки можно пойти по горизонтали и по диагонали, то будет выбран переход по горизонтали.
Re: Pathing Bot. Волновой алгоритм перемещения в ммо играх
Моя реализация алгоритма.
На поле 100х100 считает путь ~0.8с при прямом сравнении цветов и 5 сек. если сравнивать цвета с оттенком. (http://autoit-script.ru/index.php?topic=16930)
Моя реализация алгоритма.
На поле 100х100 считает путь ~0.8с при прямом сравнении цветов и 5 сек. если сравнивать цвета с оттенком. (http://autoit-script.ru/index.php?topic=16930)
Код:
#include <ScreenCapture.au3>
#include <GDIPlus.au3>
#include <Color.au3>
#include <Array.au3>
Global $LI_WALL = -1
Global $LI_BLANK = -2
Dim $a[2] = [0, 0]
Dim $b[2] = [99, 99]
Sleep(3000)
$Arr = Lee($a, $b, ToMatrix(0, 0, @DesktopWidth, @DesktopHeight))
_ArrayDisplay($Arr)
Func Lee($a, $b, $Arr)
Local $D = 0
Dim $Dx[8] = [1, 1, 0, -1, -1, -1, 0, 1]
Dim $Dy[8] = [0, -1, -1, -1, 0, 1, 1, 1]
$Arr[$a[1]][$a[0]] = $D
$SizeX = UBound($Arr)
$SizeY = UBound($Arr, 2)
Do
$Stop = True
For $x = 0 To $SizeX-1
For $y = 0 To $SizeY-1
If $Arr[$x][$y] == $D Then
For $i = 0 To 7
$Px = $x + $Dx[$i]
$Py = $y + $Dy[$i]
If $Px >=0 And $Py >= 0 And $Px < $SizeX And $Py < $SizeY And $Arr[$Px][$Py] == $LI_BLANK Then
$Stop = False
$Arr[$Px][$Py] = $D + 1
EndIf
Next
EndIf
Next
Next
$D += 1
Until $Stop Or $Arr[$b[1]][$b[0]] > 0
If $Arr[$b[1]][$b[0]] < 0 Then Return False
$x = $b[1]
$y = $b[0]
$D = $Arr[$x][$y]
Dim $P[$D][2]
Do
$D -= 1
$P[$D][0] = $y
$P[$D][1] = $x
For $i = 0 To 7
$Px = $x + $Dx[$i]
$Py = $y + $Dy[$i]
If $Px >=0 And $Py >= 0 And $Px < 100 And $Py < 100 And $Arr[$Px][$Py] == $D Then
$x = $Px
$y = $Py
ExitLoop
EndIf
Next
Until $D = 0
Return $P
EndFunc
Func ToMatrix($l, $t, $r, $b, $Color="000000", $Shade=0, $SizeX=100, $SizeY=100)
Local $x=0, $y=0
Dim $Arr[$SizeY][$SizeX]
$Data = GetImage($l, $t, $r, $b, $SizeX, $SizeY)
For $i=1 To StringLen($Data) Step 8
If $y == $SizeY Then
$y = 0
$x += 1
EndIf
If Shade(StringMid($Data, $i, 6), $Color, $Shade) Then
$Arr[$x][$y] = $LI_BLANK
Else
$Arr[$x][$y] = $LI_WALL
EndIf
$y += 1
Next
Return $Arr
EndFunc
Func Shade($Col1, $Col2, $Shade)
If $Col1 == $Col2 Then Return True
If $Shade==0 Then Return ($Col1==$Col2)
$Col1 = Execute("0x"&$Col1)
$Col2 = Execute("0x"&$Col2)
If Abs(_ColorGetRed($Col1)-_ColorGetRed($Col2)) < $Shade And Abs(_ColorGetGreen($Col1)-_ColorGetGreen($Col2)) < $Shade And Abs(_ColorGetBlue($Col1)-_ColorGetBlue($Col2)) < $Shade Then Return True
Return False
EndFunc
Func GetImage($l, $t, $r, $b, $ResW=0, $ResH=0)
Local $Width = $r-$l, $Height = $b-$t
_GDIPlus_Startup()
$hHBmp = _ScreenCapture_Capture('', $l, $t, $r, $b, False)
$hBitmap = _GDIPlus_BitmapCreateFromHBITMAP($hHBmp)
If $ResW <> 0 Then
$hBitmap = _GDIPlus_ImageResize($hBitmap, $ResW, $ResH)
$Width = $ResW
$Height = $ResH
EndIf
$Data = Hex(DllStructGetData(DllStructCreate('byte[' & ($Width * $Height * 4) & ']', DllStructGetData(_GDIPlus_BitmapLockBits($hBitmap, 0, 0, $Width, $Height, $GDIP_ILMREAD, $GDIP_PXF32ARGB), 'Scan0')), 1), 6)
_GDIPlus_BitmapDispose($hBitmap)
_WinAPI_DeleteObject($hHBmp)
_GDIPlus_Shutdown()
Return $Data
EndFunc
_serfer_78_
Новичок
- Сообщения
- 16
- Репутация
- 0
Re: Pathing Bot. Волновой алгоритм перемещения в ммо играх
Объясните пожалуйста как привязать смещения к картинке 1000х1000 пикселей (к картинке выше по ссылке нет доступа) ни как не соображу к каким координатам прицепиться, еще и изображение не входит в редактор :-\ т.к есть ограничение на количество контролов и пока не придумал чем их можно заменить
, буду очень признателен за ответ так как уже не первый раз пытаюсь использовать этот удобный и интересный но не совсем понятный алгоритм.
Как я понял привязка идет в
Если можете расскажите подробнее по каким принципам работает формула?
C2H5OH сказал(а):
Объясните пожалуйста как привязать смещения к картинке 1000х1000 пикселей (к картинке выше по ссылке нет доступа) ни как не соображу к каким координатам прицепиться, еще и изображение не входит в редактор :-\ т.к есть ограничение на количество контролов и пока не придумал чем их можно заменить
, буду очень признателен за ответ так как уже не первый раз пытаюсь использовать этот удобный и интересный но не совсем понятный алгоритм.Как я понял привязка идет в
Код:
$color = '0x' & Hex(_GDIPlus_BitmapGetPixel($hBitmap, 33+$x*8, 55+$y*8),6)Если можете расскажите подробнее по каким принципам работает формула?
Автор
- Сообщения
- 3,608
- Репутация
- 941
Re: Pathing Bot. Волновой алгоритм перемещения в ммо играх
Видимо там просто идёт масштабирование. Есть у тебя карта любого размера. Ты просто уменьшаешь её масштаб до такого, чтобы он нормально обрабатывался алгоритмом и при этом 1 клетка сжатой карты не выражала слишком большую площадь на карте в игре.
Видимо там просто идёт масштабирование. Есть у тебя карта любого размера. Ты просто уменьшаешь её масштаб до такого, чтобы он нормально обрабатывался алгоритмом и при этом 1 клетка сжатой карты не выражала слишком большую площадь на карте в игре.
_serfer_78_
Новичок
- Сообщения
- 16
- Репутация
- 0
Re: Pathing Bot. Волновой алгоритм перемещения в ммо играх
А что.... это мысль)) благодарю.Belfigor сказал(а):
