Lekce 5 - Plechovka turbo aneb Flood fill po řádcích

V minulé lekci, Optimalizace vykreslování ve 2D hrách, jsme si ukázali optimalizaci vykreslování ve 2D hrách aneb návod jak zvýšit FPS a výkon.

V lekci o algoritmu floodfill jsme si popsali tu nejjednodušší variantu vyplňovacího algoritmu. Nyní se podíváme na jeho vylepšenou formu, která potřebuje cca tisíckrát méně paměti a navíc je rychlejší.

Rozdíl je v tom, že místo abychom danou oblast vyplňovali pixel po pixelu a do zásobníku ukládali všechny pixely okolo, kreslíme po řádcích a ukládáme si jen určité "důležité" pixely, kterých je mnohonásobně méně.

Budeme potřebovat úplně stejný zásobník jako minule: nějaké pole nebo cokoli, do kterého budeme strkat souřadnice pixelů na obrazovce (např. array[...] of record x,y:integer end) a pak je z něj stylem LIFO (poslední vložený jde ven první) zase vyndavat. Teoreticky by to vlastně LIFO zásobník být nemusel, fungovalo by to i s FIFO frontou, ale LIFO je jednodušší na naprogramování a líp se s ním pracuje.

Vlastní algoritmus pak vypadá takhle:

• Někam si uložíme barvu výchozího bodu, nazvěme si ji VB (kde tato barva končí, tam končí vyplňovaná oblast).
• Pokud je tato barva rovna barvě, jakou chceme oblast vybarvit, končíme, protože už je hotovo.
• Uložíme na zásobník souřadnice výchozího bodu.

Cyklus:

• Vyjmeme ze zásobníku jeden bod (řekněme P):

• Od tohoto bodu postupujeme doleva, dokud nenarazíme na okraj oblasti:

• Od bodu P postupujeme doprava, dokud nenarazíme na okraj oblasti:

• Celý takto nalezený řádek vybarvíme:

• Nastavíme se na bod nad bodem P (nazvěme ho třeba Q). Pokud ještě je uvnitř vybarvované oblasti, uložíme tento bod na zásobník:

• Od tohoto bodu postupujeme doprava až ke konci vybarveného řádku pod ním. Kdykoli narazíme na přechod zvenčí dovnitř vybarvované oblasti (jeden pixel má barvu jinou než VB a následující ji má rovnou VB), uložíme si jeho souřadnice na zásobník (ukládáme souřadnice toho pixelu s barvou VB):

• Od bodu Q postupujeme obdobným způsobem doleva až k levému konci vybarveného řádku:

• Nastavíme se na bod pod bodem P (třeba R). Pokud ještě je ve vybarvované oblasti, uložíme tento bod na zásobník:

• Postupujeme doprava a doleva obdobně jako před chvílí (u bodu Q):

• To celé opakujeme tak dlouho, dokud není zásobník úplně prázdný:

...

A to je vše, přátelé. P.S.: je samozřejmě úplně jedno, jestli budete testovat nejdříve levou stranu a pak pravou nebo naopak. Výše uvedené pořadí bylo zvoleno náhodně. P.P.S.: je dobré sloučit cykly pro nalezení konce aktuálního řádku a testování řádků nahoře a dole do jednoho (mají stejný index). P.P.P.S.: když se podmínka "leží pixel uvnitř oblasti a má se vybarvit?" změní z tvaru (barva=původní_bar­va_oblasti) na tvar (barva<>barva_hra­nice)and(barva<>bar­va_kterou_vybar­vujeme), změní se tak Plechovka z Paintbrushe na Floodfill z Graph.tpu - barva se přelije přes jakékoli pozadí a zastaví se jedině o zadanou barvu okraje (nebo o barvu, kterou vybarvujeme, aby nevznikla nekonečná smyčka).

Jak je na tom tento algoritmus s rychlostí? O něco lépe než dříve uvedená varianta "bod po bodu do všech stran", protože kreslí celé řádky najednou. Hlavně ale spotřebovává o několik řádů méně paměti: ukládá obvykle méně než 10 bodů na jeden řádek, zatímco předchozí algoritmus by jich potřeboval několik stovek.

Rychlost ale pořád ještě není zrovna špičková. Hlavně proto, že musíme testovat spoustu pixelů (na jednom řádku doleva, doprava a pak to samé o řádek nahoře i dole). První urychlovací zlepšovák, který mě napadl, byl použít místo Getpixelu Getimage, řádky si načíst do paměti celé a testovat je až tam (normální paměť se čte mnohem rychleji než grafická). Jenže zrychlení není moc výrazné a hlavně se tím výrazně zpomalí vyplňování malých oblastí - devadesát Getpixelů je pořád ještě rychlejší než jeden Getimage přes celou šířku obrazovky. Takže doporučuji pro začátek zůstat u Getpixelu (než někde vyštrachám nějaký ještě vypiplanější a rychlejší algoritmus (což už ale moc pravděpodobné není)).

V další lekci, Transformace souřadnic v rovině pomocí transformačních matic, si ukážeme algoritmus pro transformaci souřadnic v rovině.