V předchozím článku jsem nakousl vývoj bota, který bude umět vykonávat nějaké činnosti nad hrou, která je založena na Flash prostředí. Jedinný způsob jak dokážu přečíst obsah hrací plochy je přečtení obsahu okna, celý bot je založený na principu bitmap, v kterých dokáže hledat.
Z principu lze hledat menší bitmapu v té větší. Těm menším, hledaným, budu říkat fragmenty a té větší budu říkat screen shot. Scren shot není přesné označení, ale vystihuje o co tu jde. Fragment by měl být co nejmenších rozměrů, aby aplikace neztratila svůj možný potenciál tím, že bude neustále přehazovat tuny dat tam a zpět. Fragment ale musí být na druhou stranu dostatečně veliký, aby zajistil unikátnost. K čemu malé fragmenty, které jsou nespolehlivé, každý fragment musí unikátně reprezentovat bitmapu, kterou hledám.
Výsledný obrázek hry, jak jí hráč vidí na svém monitoru, je kompozice desítek, možná i stovek menších bitmap. Jsou vrstveny přes sebe. Navíc mají průhledná pozadí, takže jedna může překrývat druhou. Vyhlazování okrajů pomocí alpha kanálu bitmap způsobuje, že binární vzorek původní bitmapy nemusí být nalezen ve screen shotu. No a co teď s tím, když binární aritmetika fragment nebude schopna najít. Jako na obrázku se stromy, jeden strom na několika pozicích.
Co kdyby hledací algorytmus dokázal definovat váhu, na základě které by dokázal říct, co si o shodě myslí. Ideálně, na kolik procent se porovnávané pixely shodují. Tím by algorytmus pokryl odchylky v sytosti barev, kontrastu i jasu najednou. A pokud bude tolerance dostatečně veliká, má tento nápad šanci fungovat.
A pokud se a algorytmu přidá možnost definovat jednu konkrátní barvu jako průhlednou, získám možnost definovat hluchá místa fragmentu, která se ve screen shotu nebudou porovnávat, ale přeskakovat. Tato možnost algorytmu umožní hledat i jiné než obdélníkové tvary.
Dost bylo teorie, pojďme se podívat na zdrojový kód metody, která má výše popsané vlastnosti a hledá fragment ve screen shotu:
// Spocita podobnost pixelu, pracuje s procenty
// Vraci procentni podobnost. 100 = maximalni shoda, pixel ma stehnou barvu.
// 0 = totalni rozil asi jako cerna a bila.
function TExtendedBitmap.GetPixelSimilarity(AlpPixelLeft, AlpPixelRight: PRGBTriple): Integer;
var
XPercentR, XPercentG, XPercentB: Integer;
// Prevodni funkce z bajtu na procenta.
function ByteToPercent(const AByte: Byte): Byte;
begin
Result := Round(GOnePercentOfByte * AByte);
end;
begin
try
// Formalni kontrolam pokud projde, pokracuju.
if ((AlpPixelLeft <> nil) and (AlpPixelRight <> nil)) then
begin
// Spocitam procentni podobnost kazde slozky barvy (RGB)
XPercentR := abs(ByteToPercent(AlpPixelLeft^.rgbtRed) - ByteToPercent(AlpPixelRight^.rgbtRed));
XPercentG := abs(ByteToPercent(AlpPixelLeft^.rgbtGreen) - ByteToPercent(AlpPixelRight^.rgbtGreen));
XPercentB := abs(ByteToPercent(AlpPixelLeft^.rgbtBlue) - ByteToPercent(AlpPixelRight^.rgbtBlue));
// Prumerem se dozvim kompletni podobnost barvy pixelu.
Result := 100 - ((XPercentR + XPercentG + XPercentB) div 3);
end
else
// Formalni kontrola neprosla, vracim totalni rozdil.
Result := 0;
except
on E: Exception do
begin
// Pri chybe reaguji tak ,ze vratim totalni rozdil.
// Spravne to neni, mechanizmus by mel pracovat bez vyjimek.
Result := 0;
end;
end;
end;
// Hleda bitmapu
// Parametr: ALookingFor - Co hledam
// Parametr: ARectArea - Kde to hledam hledam (vyrez)
// Parametr: OUT AOutRect - Kde sem to nasel
// Parametr: AAcceptableSimilarity - jakou podobnost akcptuji. 100 = presna shoda
// Parametr: AStartX - Pocatek X vramci vyrezu
// Parametr: AStartY - Pocatek Y vramci vyrezu
// Vrati true, pokud najde, jinak false.
function TExtendedBitmap.LookingFor(ALookingFor: TExtendedBitmap; ARectArea: TRect; var AOutRect: TRect; const AAcceptableSimilarity: Byte = 90; const AStartX: Integer = 0; AStartY: Integer = 0): Boolean;
var
x, y, XFragmentWidth, XFragmentHeight, XStartX, XStartY: Integer;
XAcceptableSimilarity: Byte;
// Metoda ma za ukol prexist hodnotu zdrojove bitmapy a z fragmentu a porovnat je.
// Bere ale v uvahu, ze fragment muze obsahoat specialni barvu, ktera definuje pruhlednost.
function ReadPixelSimilarity(APoint: TPoint): Integer;
var
XlpPIX1, XlpPIX2: PRGBTriple;
begin
// Ctu barvu pizelu fragmentu.
XlpPIX2 := ALookingFor.PPixels[APoint.X, APoint.Y];
// Je-li pixel rude barvy, automaticky odpovidam, ze shoda je 100%
if (XlpPIX2^.rgbtRed = $FF) and (XlpPIX2^.rgbtGreen = $00) and (XlpPIX2^.rgbtBlue = $00) then
// Totalni shoda, fragment ma pruhlednou barvu.
Result := 100
else
begin
// Musim precist pixel zdrojove bitmapy.
XlpPIX1 := PPixels[x + APoint.X, y + APoint.Y];
// Porovnam 2 pixely a vysledek vratim.
Result := GetPixelSimilarity(XlpPIX1, XlpPIX2);
end;
end;
// Metoda porovnava 2 pixely proti sobe a vraci vahu podobnosti v procenteh.
// Jako vstup je souradnice, odkud se pixely ctou.
// Souradnice APoint jsou absolutni vzhledem k fragmentu.
// Vzhledem ke zdrojove bitmape je souradnice relativni.
// Vrati true, pokud si jsou pixely podobne, podle procentni vahy XAcceptableSimilarity.
function IsPixelSimilar(APoint: TPoint): Boolean;
var
XSimilarity: Integer; // Procentni podobnost.
begin
// Ziskam procentni podobnost.
XSimilarity := ReadPixelSimilarity(APoint);
// Vyhodnotim podobnost.
// Pokud je podobnost pixelu vetsi jak AAcceptableSimilarity%, pak pixel akceptuji.
Result := (XSimilarity > XAcceptableSimilarity);
end;
// Metoda mapuje fragment na konkertni souradnice zdrojove bitmapy.
function ReadSubSet(): Boolean;
var
x1, y1: Integer;
begin
Result := True;
// Projdu vsechny radky fragmentu
for y1:=0 to XFragmentHeight-1 do
// Projdu vsechny sloupce fragmentu
for x1:=0 to XFragmentWidth-1 do
begin
// Porovnam pixely fragmentu a zdroje.
Result := Result and (IsPixelSimilar(Point(x1, y1)));
// Pokud najdu prvni pixel, ktery je mimo toleranci podobnosti, koncim.
if not (Result) then
// KOnec, tento pixel je ve fragmentu jiny nez ve zdroji.
Exit;
end;
end;
// Metoda ma za ukol vzit rohove pizely framentu a jeho dtredovy pixel a provnat je
// s pixely ve zdrojove bitmape.
function FastMatch(): Boolean;
var
XPoint: TPoint;
begin
// Kontrola na levy horni roh.
XPoint := Point(0, 0);
Result := IsPixelSimilar(XPoint);
if not (Result) then
Exit;
// Kontrola na pravy horni roh.
XPoint := Point((XFragmentWidth-1), 0);
Result := IsPixelSimilar(XPoint);
if not (Result) then
Exit;
// Kontrola na pravy dolni roh.
XPoint := Point((XFragmentWidth-1), (XFragmentHeight-1));
Result := IsPixelSimilar(XPoint);
if not (Result) then
Exit;
// Kontrola na levy dolni roh.
XPoint := Point(0, (XFragmentHeight-1));
Result := IsPixelSimilar(XPoint);
if not (Result) then
Exit;
// Kontrola na pixel uprostred.
XPoint := Point((XFragmentWidth-1) div 2, (XFragmentHeight-1) div 2);
Result := IsPixelSimilar(XPoint);
if not (Result) then
Exit;
end;
begin
// Kontrola parametru AAcceptableSimilarity.
if (AAcceptableSimilarity > 100) then
XAcceptableSimilarity := 100
else
XAcceptableSimilarity := AAcceptableSimilarity;
// Kontrola Parametru AStartX
XFragmentWidth := ALookingFor.Width;
if (ARectArea.Right < 0) then
ARectArea.Right := Width - XFragmentWidth;
// Kontrola Parametru AStartY
XFragmentHeight := ALookingFor.Height;
if (ARectArea.Bottom < 0) then
ARectArea.Bottom := Height - XFragmentHeight;
// Kontrola hranicnich hodnot pro X.
if (ARectArea.Right > Width - XFragmentWidth) then
ARectArea.Right := Width - XFragmentWidth;
// Kontrola hranicnich hodnot pro Y.
if (ARectArea.Bottom > Height - XFragmentHeight) then
ARectArea.Bottom := Height - XFragmentHeight;
// Kontrola hranicnich hodnot pro Y.
if (ARectArea.Top < 0) then
ARectArea.Top := 0;
if (AStartY < ARectArea.Top) then
XStartY := ARectArea.Top
else
if (AStartY > ARectArea.Bottom) then
XStartY := ARectArea.Bottom
else
XStartY := AStartY;
// Kontrola hranicnich hodnot pro X.
if (ARectArea.Left < 0) then
ARectArea.Left := 0;
if (AStartX < ARectArea.Left) then
XStartX := ARectArea.Left
else
if (AStartX > ARectArea.Right) then
XStartX := ARectArea.Right
else
XStartX := AStartX;
//
// START
Result := False;
// Projdu vsechny radky vyrezu
for y:=XStartY to ARectArea.Bottom do
begin
// Projdu vsechny sloupce vyrezu
for x:=XStartX to ARectArea.Right do
// Test na shodu 5 pixelu
if (FastMatch()) then
// Pokud se shoduji, projedu zbytek fragmentu.
if (ReadSubSet) then
begin
// Fragment nalezen.
Result := True;
// Vyplnim vystupni vyrez, kde byl fragment v bitmape nalezen.
AOutRect.Left := x;
AOutRect.Top := y;
AOutRect.Right := x + XFragmentWidth;
AOutRect.Bottom := y + XFragmentHeight;
// KOnec metody.
Exit;
end;
// Na dalsim radku jiz pojedu od leve hranice vyrezu.
XStartX := ARectArea.Left;
end;
end;
Nyní si můžeme tělo metody společně projít a okomentovat ho.
Metoda je členem objektu TExtenedBitmap, je to můj následník VCL třídy TBitmap, později poskytnu otevřený kompletní zdroj této třídy. Takže instanci objektu, nad kterým metodu LookigFor zavoláme je screen shot a bitmapa, kterou hledáme reprezentovaná parametrem ALookingFor je fragment.
Teď víme, co v čem hledáme.
Předně si všiměte, že samotný kód metody začíná až téměř dole za komentářem //START. Před tímto komentářem se zpracovávají vstupní parametry rozměru zabalené do rekordu TRect, kde se definuje oblast screen shotu, ve které se bude hledat. To je dobré pro optimalizace. Je zbytečné prohledávat úplně celou bitmapu, když vím, že stačí prohledat jen část. Ve své podstatě je metoda primitivní. Začne lineárním způsobem procházet screen shot řádek po řádku a nad každým pixelem volá funkci FastMatch(), která na aktuální prohledávané souřadnice namapuje fragment a porovná jen vybrané pixely. Vybranými pixely jsou levý horní roh fragmentu, pravý horní roh, pravý dolní roh, levý dolní roh a prostředek fragmentu. Pokud těchto 5 pixelů odpovídá svou podobností, je zavolána metoda ReadSubset(), která porovná opět lineárním způsobem všechny pixely fragmentu se screen shotem. Jakmile narazí na první neshodu, funkce končí a metoda pokračuje dalším pixelem screnshotu.
Takto se pracuje stále dokola, dokud není buď nalezena shoda fragmentu a nebo dokud se neprojde celý screen shot.
Porovnávání pixelu na shodu dělá funkce IsPixelSimilar, která používá další funkci ReadPixelSimilarity. V podstatě funkce ReadPixelSimilarity má za úkol zajistit přečtení barev pixelů screen shotu a fragmentu, což může udělat dvěma způsoby. Následně se zavolá poslední funkce v řetězu a tou je již samostatně stojící metoda objektu s názvem GetPixelSimilarity. Jako vstupní parametry dostane 2 struktury s RGB složkami, které proti sobě porovná. Tím, že váhu kanálu R, G a B sčítá, zajišťuje sloučení barevné sytosti, konstrastu i jasu na jednu hromadu. Návratová hodnota této funkce je procento shody. Čím větší procento, tím shodnější pixely jsou.
Procento váhy je u metody LookingFor vyjádřeno vstupním parametrem AAcceptableSimilarity s výchozí hodnotou 90.
Tak, to je přibližně vše co se dá k algorytmu říci. Pokud se ve zdrojovém kódu vyznáte, snadno pochopíte, jak to celé pracuje do detailu.
Také vám jistě neuniklo, že metoda používá property PPixels, která standardně u objektu TBitmap není. Implementace je podobná jako property Pixels, s tím rozdílem, že používá k přístupu k paměti bitmapy ScanLines, čímž se práce s pixely značně akceleruje. Aby práce se ScanLines byly pro mne přijemější, zabalil jsem je do sady funkcí, které jsou velice rychlé.
Zde je zdroj implementující TExtendedBitmap. Zdroj můžet použít libolně avšak jen tehdy, že akceptujete, že nenesu žádnou zodpovědnost za škody, které může chybná implementace anebo chybné použití způsobit.
Zdrojový kód UExtendedBitmap.zip je ke stažení zde.
|
Zdrojové kódy projektu jsou na tomto odkazu. |
