Można jeszcze bardzo wiele rzeczy poprawić i ulepszyć w poniższym kodzie – ale gdyby ktoś zastanawiał się od czego zacząć tworzenie bota do gry (np. zrobionej we Flashu, HTML5), może skorzystać z mojego podejścia i kodu.
1. Gra
Bot powstał „na szybko” do gry będącej częścią kampanii reklamowej LTE od Plusa w serwisie wykop.pl. Gra wzorowana na PacManie, w której rozgrywkę można było podzielić na dwa etapy. Pierwszy – zbieranie wykopów (najlepiej w trybie Super Plusmana), punktów LTE (zamieniających Plusmana w Super Plusmana), zjadanie „wolnych internetów” jako Super Plusman i unikanie ich jako zwykły Plusman oraz zbieranie pojawiających się co 30 sekund tabletów Lenovo Yoga – zabawa w sumie na jakieś 2 minuty jeśli chcemy zsynchronizować bycie Super Plusmanem z pojawianiem się tabletów (Super Plusman porusza się szybciej i przechodzi przez ściany, więc zwiększamy w ten sposób szansę zgarnięcia tabletu). Gra kończy się w chwili zgarnięcia ostatniego wykopu – ale jeśli gracz się z tym wstrzyma – to zaczynał się drugi etap – zbieranie tabletów co 30s (i unikanie „wolnych internetów”). Etap ten mógł trwać nawet kilka godzin (chyba po ok. 5h przestawały pojawiać się tablety), więc na nim się skupiłem.
Ekran z gry Plusman LTE
Link do gry: http://www.wykop.pl/+/pluslte/ (link nieaktualny)
2. Narzędzia
Skorzystałem z programu AutoHotkey – w którym można tworzyć różne skrypty, makra automatyzujące czynności wykonywane na komputerze. Kiedyś stworzyłem przy jego pomocy łamacz haseł do jakiegoś programu księgowego. W skrócie program/skrypt wpisywał trzy hasła ze słownika (wygenerowanego wcześniej przez HashCata w oparciu o informacje nt. zapomnianego hasła), zamykał i uruchamiał program i sprawdzał kolejne hasła (na szczęście można było tak robić w nieskończoność).
Oprócz AHK w międzyczasie przydał się również GIMP, LibreOffice Calc oraz Notepad++.
3. Bot
a) Lokalizowanie elementów na ekranie
Ponieważ to mój pierwszy bot, to zacząłem od sprawdzenia, czy AHK jest w stanie znaleźć na ekranie Plusmana i tablet.
Loop
{
ImageSearch, Px, Py, 456, 349, 859, 714, plusman.bmp
if ErrorLevel = 0
{
Result = "`nPx = " . %Px% . "`nPy = " . %Py% . "`n"
tooltip %Result%, 0, 0
}
}
Plusman różnie wygląda w różnych pozycjach, jego peleryna ciągle faluje, tło pod nim się zmienia, to wybranie jednego obrazka nie było takie proste. Dopiero przy dużym zbliżeniu w GIMPie znalazłem fragment płaszcza (5×5 pikseli), który występował cały czas. Oto on: 
Z tabletem było podobnie – dopiero odpowiedni fragment 1×5 pikseli (
) pozwalał na zlokalizowanie obrazka. Obrazek między nawiasami w poprzednim zdaniu 🙂
W międzyczasie przydał się skrypt pokazujący aktualne współrzędne kursora myszy.
Skoro działa, to jedziemy dalej.
b) Labirynt
Rozważałem dwa podejścia – albo analizować na bieżąco obraz i w ten sposób nawigować po planszy, albo trzymać planszę jako tablicę w pamięci i z jej pomocą poruszać się po labiryncie.
Wybrałem drugie rozwiązanie. Wystarczył zrzut ekranu z grą (Print Screen) + naniesiona z pomocą GIMPa siatka (Filtry -> Renderowanie -> Deseń -> Siatka…) i całość wstawiona jako tło do arkusza kalkulacyjnego (może być Calc, może być Excel). Następnie szerokość i wysokość komórek dopasowana do grubości pojedynczej ścianki labiryntu, całość wypełniona najpierw zerami, a potem pozaznaczane komórki pokrywające się ze ścianami i wypełnione jedynkami – mniej więcej jak na poniższym obrazku:
Plansza gry Plusman w Calcu
Zewnętrzne ściany do pominięcia. Czerwone komórki – tam gdzie przeoczyłem wcześniej ściany i wstawiłem 0 zamiast 1, a żółty ślad to test nawigowania po labiryncie z dalszego etapu budowy bota.
Jeszcze tylko przeliczanie pozycji na ekranie na odpowiedni wiersz i kolumnę – przetestowane poniższym „skrypcikiem” (współczynniki wpisane na stałe, dostosowane do mojego ekranu, rozdzielczości i pozycji gry w zmaksymalizowanym oknie przeglądarki).
Loop
{
ImageSearch, Px, Py, 456, 349, 859, 714, plusman.bmp
if ErrorLevel = 0
{
Result = "`nPx = " . %Px% . "`nPy = " . %Py% . "`n"
col := Abs(Round((Px - 468) / 13.76)) + 1
row := Abs(Round((Py - 355) / 13.88)) + 1
Result = %Result% `n Col,Row: %col%, %row%
tooltip %Result%, 0, 0
}
}
c) Wyznaczanie trasy
Pewnie większość programistów słyszała o algorytmie A* – słyszałem i ja 🙂
Miałem poprzerabiać gotowy kod JS na AHK, ale google podsunął gotową implementację A* dla AHK, która właściwie nie wymagała żadnych przeróbek – można było od razu odpalić tak:
PathFind(Grid, col_begin, row_begin, col_end, row_end)
gdzie Grid to odpowiednio sparsowana tablica Field (z danymi z arkusza kalkulacyjnego):
Field = ( 00000000000000100000000000000 00000000000000100000000000000 00111111111100100111111111100 00000000000000000000000000000 00000000000000000000000000000 00111100100111111100100111000 00000000100000100000100000000 00000000100000100000100000000 11111100111100100111100111111 00000100100000000000100100000 00000100100000000000100100000 00111100100110011100100111000 00000000000100000100000000000 00000000000100000100000000000 00111100100111111100100111000 00000100100000000000100100000 00000100100000000000100100000 11111100100111111100100111111 00000000000000100000000000000 00000000000000100000000000000 00111111111100100111111111100 00100000000000000000000000100 00100000000000000000000000100 00100111111100100111111100100 00000000000000100000000000000 00000000000000100000000000000 )
d) Poruszanie się
To w sumie tylko wysyłanie wirtualnych wciśnięć klawiszy strzałek i odczekanie chwilkę:
Ponieważ algorytm A* zwracał tablicę kolejnych pól, przez które trzeba przejść, to zrobiona na szybko implementacja poruszania wyglądała mniej więcej tak:
GoToXY(curX,curY, destX,destY)
{
if(curX > destX)
{
Loop 3
{
Send {left}
Sleep 70
}
}
else if(curX < destX)
{
Loop 3
{
Send {right}
Sleep 60
}
}
if(curY > destY)
{
Loop 3
{
Send {up}
Sleep 90
}
}
else if(curY < destY)
{
Loop 3
{
Send {down}
Sleep 90
}
}
}
e) Podsumowanie
W sumie algorytm działa tak, że cały czas wyszukuje na ekranie pozycji Plusmana i tabletu. Gdy znajdzie tablet, to korzystając z alg. A* (oraz tablicy z zero-jedynkową mapą poziomu) wyznacza trasę i – jeśli tylko nie jest za daleko – to właściwie na ślepo realizuje tę trasę (wysyłając do gry wciśnięcia odpowiednich klawiszy). Następnie powraca do pozycji gdzieś po środku 10 kolumny i czeka na pojawienie się kolejnego tabletu. Poniżej cały skrypt, pełen jeszcze prowizorek, zakomentowanych fragmentów, testowych śmieci, warunków pod konkretną rozgrywkę itp., bo niestety ostatecznej wersji nie mam pod ręką (pozostała na innym komputerze – na którym skrypt działał sobie po klika godzin). Większość zajmuje skopiowana implementacja A* i zero-jedynkowa mapa poziomu.
A co do skuteczności samego bota – dzięki niemu znalazłem się w pierwszej 10 rankingu graczy…
Field =
(
00000000000000100000000000000
00000000000000100000000000000
00111111111100100111111111100
00000000000000000000000000000
00000000000000000000000000000
00111100100111111100100111000
00000000100000100000100000000
00000000100000100000100000000
11111100111100100111100111111
00000100100000000000100100000
00000100100000000000100100000
00111100100110011100100111000
00000000000100000100000000000
00000000000100000100000000000
00111100100111111100100111000
00000100100000000000100100000
00000100100000000000100100000
11111100100111111100100111111
00000000000000100000000000000
00000000000000100000000000000
00111111111100100111111111100
00100000000000000000000000100
00100000000000000000000000100
00100111111100100111111100100
00000000000000100000000000000
00000000000000100000000000000
)
Grid := []
Loop, Parse, Field, `n
{
A_Index1 := A_Index
Loop, Parse, A_LoopField
Grid[A_Index,A_Index1] := A_LoopField
}
;^!c::
Loop
{
ImageSearch, PYx, PYy, 456, 349, 856, 714, yogab.bmp
if ErrorLevel = 0
{
Result1 = "1:`nPYx = " . %PYx% . "`nPYy = " . %PYy% . "`n"
colY := Abs(Round((PYx - 468) / 13.76)) + 1
rowY := Abs(Round((PYy - 355) / 13.88)) + 1
;MsgBox %Result%
;break
ResultY = Yoga: %colY%, %rowY%
}
else
{
ResultY = _
}
;ImageSearch, Px, Py, 456, 349, 856, 712, yogab.bmp
; ImageSearch, Px, Py, 456, 349, 859, 714, plusman.bmp
ImageSearch, Px, Py, 456, 349, 859, 714, plusman.bmp
if ErrorLevel = 0
{
Result = "2:`nPx = " . %Px% . "`nPy = " . %Py% . "`n"
;MsgBox %Result%
col := Abs(Round((Px - 468) / 13.76)) + 1
row := Abs(Round((Py - 355) / 13.88)) + 1
Result = %Result% `n Col,Row: %col%, %row% `n %ResultY%
tooltip %Result%, 0, 0
;break
}
if (ResultY != "_")
{
ResultPF := ""
;PFArr = PathFind(Grid,col,row,colY,rowY)
For Key, Node In PathFind(Grid,col,row,colY,rowY)
ResultPF .= Node.X . "," . Node.Y . "`n"
; MsgBox % ResultPF
maxLines:=0
loop, parse, ResultPF, `n, `r
maxLines:=a_index
dist := sqrt((col-colY)**2+(row-rowY)**2)
prevX := col
prevY := row
;if ( maxLines > 0 && maxLines < 21 && dist < 16 && colY < 22 && rowY > 5 )
if GetKeyState("capslock","T") ; whether capslock is on or off
{
tooltip ; if off, don't show tooltip at all.
}
else
{
if ( maxLines > 0 && (maxLines < 9 || dist < 9 || (maxLines < 21 && dist < 16 && colY < 25 && rowY > 5)) )
{
; msgbox Dist OK `n lines: %maxLines% `ndist: %dist% `n %ResultPF%
For Key, Node In PathFind(Grid,col,row,colY,rowY)
{
GoToXY(prevX,prevY, Node.X,Node.Y)
prevX := Node.X
prevY := Node.Y
}
Random, randY, 10, 20
For Key, Node In PathFind(Grid,colY,rowY,10,randY)
{
GoToXY(prevX,prevY, Node.X,Node.Y)
prevX := Node.X
prevY := Node.Y
}
}
else
{
; msgbox Too far `n lines: %maxLines% `ndist: %dist% `n %ResultPF%
Random, randY, 15, 20
For Key, Node In PathFind(Grid,col,row,10,randY)
{
GoToXY(prevX,prevY, Node.X,Node.Y)
prevX := Node.X
prevY := Node.Y
}
}
}
}
/*
else
{
prevX := col
prevY := row
Random, randY, 10, 20
For Key, Node In PathFind(Grid,col,row,10,randY)
{
GoToXY(prevX,prevY, Node.X,Node.Y)
prevX := Node.X
prevY := Node.Y
}
}
*/
Sleep 200
tooltip
}
PathFind(Grid,StartX,StartY,EndX,EndY)
{
If Grid[StartX,StartY] || Grid[EndX,EndY] ;start or end position is not passable
Return, [] ;could not find path
CurrentScores := [], CurrentScores[StartX,StartY] := 0 ;map of current scores
HeuristicScores := [] ;map of heuristic scores
TotalScores := [], TotalScores[StartX,StartY] := 0
OpenHeap := [Object("X",StartX,"Y",StartY)] ;heap containing open nodes
OpenMap := [], OpenMap[StartX,StartY] := 1
VisitedNodes := [] ;map of visited nodes
Parents := [] ;mapping of nodes to their parents
While, MaxIndex := ObjMaxIndex(OpenHeap) ;loop while there are entries in the open list
{
;select the node having the lowest total score
Node := OpenHeap[1], NodeX := Node.X, NodeY := Node.Y ;obtain the minimum value in the heap
OpenHeap[1] := OpenHeap[MaxIndex], OpenHeap.Remove(MaxIndex), MaxIndex -- ;move the last entry in the heap to the beginning
Index := 1, ChildIndex := 2
While, ChildIndex <= MaxIndex
{
Node1 := OpenHeap[ChildIndex], Node2 := OpenHeap[ChildIndex + 1]
If (ChildIndex < MaxIndex && TotalScores[Node1.X,Node1.Y] > TotalScores[Node2.X,Node2.Y]) ;obtain the index of the lower of the two child nodes if there are two of them
ChildIndex ++
Else
Node2 := Node1
Node1 := OpenHeap[Index]
If TotalScores[Node1.X,Node1.Y] < TotalScores[Node2.X,Node2.Y] ;stop updating if the parent is less than or equal to the child
Break
Temp1 := OpenHeap[Index], OpenHeap[Index] := OpenHeap[ChildIndex], OpenHeap[ChildIndex] := Temp1 ;swap the two elements so that the child entry is greater than the parent
Index := ChildIndex, ChildIndex <<= 1 ;move to the child entry
}
OpenMap[NodeX,NodeY] := 0 ;remove the entry from the open map
;check if the node is the goal
If (NodeX = EndX && NodeY = EndY)
{
Path := []
Loop
{
Path.Insert(1,Object("X",NodeX,"Y",NodeY))
Node := Parents[NodeX,NodeY]
If !IsObject(Node)
Break
NodeX := Node.X, NodeY := Node.Y
}
Return, Path
}
VisitedNodes[NodeX,NodeY] := 1
If NodeX > 1
ScoreNode(EndX,EndY,NodeX,NodeY,Grid,NodeX - 1,NodeY,OpenHeap,OpenMap,VisitedNodes,CurrentScores,HeuristicScores,TotalScores,Parents)
If (NodeX < ObjMaxIndex(Grid))
ScoreNode(EndX,EndY,NodeX,NodeY,Grid,NodeX + 1,NodeY,OpenHeap,OpenMap,VisitedNodes,CurrentScores,HeuristicScores,TotalScores,Parents)
If NodeY > 1
ScoreNode(EndX,EndY,NodeX,NodeY,Grid,NodeX,NodeY - 1,OpenHeap,OpenMap,VisitedNodes,CurrentScores,HeuristicScores,TotalScores,Parents)
If (NodeY < ObjMaxIndex(Grid[1]))
ScoreNode(EndX,EndY,NodeX,NodeY,Grid,NodeX,NodeY + 1,OpenHeap,OpenMap,VisitedNodes,CurrentScores,HeuristicScores,TotalScores,Parents)
}
Return, [] ;could not find a path
}
ScoreNode(EndX,EndY,NodeX,NodeY,Grid,NextNodeX,NextNodeY,OpenHeap,OpenMap,
VisitedNodes,CurrentScores,HeuristicScores,TotalScores,Parents)
{
If (Grid[NextNodeX,NextNodeY] || VisitedNodes[NextNodeX,NextNodeY]) ;next node is a wall or is in the closed list
Return
BestCurrentScore := CurrentScores[NodeX,NodeY] + 1 ;add the distance between the current node and the next to the current distance
If !OpenMap[NextNodeX,NextNodeY]
{
HeuristicScores[NextNodeX,NextNodeY] := Abs(EndX - NextNodeX) + Abs(EndY - NextNodeY) ;wip: diagonal distance: Max(Abs(EndX - NextNodeX),Abs(EndY - NextNodeY))
CurrentScores[NextNodeX,NextNodeY] := BestCurrentScore
TotalScores[NextNodeX,NextNodeY] := BestCurrentScore + HeuristicScores[NextNodeX,NextNodeY]
Parents[NextNodeX,NextNodeY] := Object("X",NodeX,"Y",NodeY)
;append the value to the end of the heap array
Index := ObjMaxIndex(OpenHeap), Index := Index ? (Index + 1) : 1
OpenHeap[Index] := Object("X",NextNodeX,"Y",NextNodeY)
OpenMap[NextNodeX,NextNodeY] := 1 ;add the entry to the open map
;rearrange the array to satisfy the minimum heap property
ParentIndex := Index >> 1, Node1 := OpenHeap[Index], Node2 := OpenHeap[ParentIndex]
While, Index > 1 && TotalScores[Node1.X,Node1.Y] < TotalScores[Node2.X,Node2.Y] ;child entry is less than its parent
{
Temp1 := OpenHeap[ParentIndex], OpenHeap[ParentIndex] := OpenHeap[Index], OpenHeap[Index] := Temp1 ;swap the two elements so that the child entry is greater than its parent
Index := ParentIndex, ParentIndex >>= 1 ;move to the parent entry
}
}
Else If (BestCurrentScore >= CurrentScores[NextNodeX,NextNodeY])
{
CurrentScores[NextNodeX,NextNodeY] := BestCurrentScore
TotalScores[NextNodeX,NextNodeY] := BestCurrentScore + HeuristicScores[NextNodeX,NextNodeY]
Parents[NextNodeX,NextNodeY] := Object("X",NodeX,"Y",NodeY)
}
}
GoToXY(curX,curY, destX,destY)
{
Random, verOrHor, 0, 1
if (verOrHor = 0)
{
if(curX > destX)
{
Loop 3
{
Send {left}
Sleep 70
}
}
else if(curX < destX)
{
Loop 3
{
Send {right}
Sleep 60
}
}
if(curY > destY)
{
Loop 3
{
Send {up}
Sleep 90
}
}
else if(curY < destY)
{
Loop 3
{
Send {down}
Sleep 90
}
}
}
else
{
if(curY > destY)
{
Loop 3
{
Send {up}
Sleep 90
}
}
else if(curY < destY)
{
Loop 3
{
Send {down}
Sleep 90
}
}
if(curX > destX)
{
Loop 3
{
Send {left}
Sleep 60
}
}
else if(curX < destX)
{
Loop 3
{
Send {right}
Sleep 60
}
}
}
}
f) Ulepszenia
Można by np. dodać omijanie „wolnych internetów” – ja skorzystałem z faktu, że przez większość gry poruszają się one w prawym górnym lub dolnym rogu, ewentualnie czasami utkną w którejś z bocznych zatoczek – i po prostu przy pomocy paru prostych warunków omijałem tamte miejsca. Można też dopracować poruszanie postacią, tak żeby lepiej adaptowało się do różnych sytuacji (np. w tej wersji, gdy obciążenie komputera nagle skoczyło, zdarzało się, że Plusman skręcał odrobinę za wcześnie, uderzał w ścianę i realizując (w ciemno) resztę wyznaczonej trasy nie docierał już do celu. Można usunąć jedno wywołanie funkcji PathFind(Grid,col,row,colY,rowY) korzystając z zapisanego wyniku pierwszego wywołania (w załączonym kodzie raz jest wywoływana dla ustalenia odległości Plusmana od tabletu (wyrażonej ilością kroków w wyniku działania alg. A*), a potem drugi raz przy ewentualnym realizowaniu trasy – bo miałem jakiś problem z zapisaniem wyniku do tablicy a nie chciałem tracić na to czasu).
4. Posłowie
Wiem, że dla tego skryptu jeszcze daleka droga do bycia porządnym botem – zamieszczam głównie dlatego, że jakoś tam działa i może komuś kiedyś się przyda. Zwłaszcza jeśli podobnie jak ja – nie tworzył nigdy bota i zaczyna od podstaw.