Stránka sa načítava, prosím čakajte…
© 2005 – 2024 Roman Horváth, všetky práva vyhradené. Dnes je 25. 4. 2024.
Dátum: 15. 2. 2013, pred viacerými rokmi, aktualizované: 30. 7. 2020, pred štyrmi rokmi
Najprv si ukážme jednoduché riešenie, ktoré poslúžilo aj na nakreslenie obrázka v zadaní. Rekurzívna metóda plást prijíma jeden argument určujúci „iteráciu,“ resp. stupeň rekurzie. To znamená, že rekurzia sa skončí po dosiahnutí istého stupňa rekurzie (v príklade je to hodnota 10).
Metóda plást v podstate kreslí rovnú čiaru, ktorá sa na konci rekurzívne rozvetví do súmernej vidlice. Vidlicu si môžete nechať nakresliť prepísaním hodnoty 10 na 1:
Keď sa rekurzívne kreslenie takejto vidlice zopakuje dostatočný počet ráz, vzniká plást.
~
import knižnica.*;
public class VčelíPlást extends GRobot
{
private VčelíPlást()
{
Svet.zbaľ();
skoč(0, -80);
hrúbkaČiary(1.5);
plást(0);
}
public void plást(int i)
{
if (i <= 10)
{
položPero();
dopredu(50);
doľava(60);
plást(i + 1);
doprava(60);
doprava(60);
plást(i + 1);
doľava(60);
zdvihniPero();
dozadu(50);
}
}
public static void main(String[] args)
{
new VčelíPlást();
}
}
Kreslenie plástu týmto spôsobom má jednu nevýhodu. Robot zbytočne prechádza cez niektoré hrany viacej ráz, čo je neefektívne (aj neestetické, keďže po každom prekreslení hrana mierne zhrubne a jej okraje mierne zdrsnejú).
Táto fáza zlepšovania sa zaoberá problémom viacnásobného kreslenia hrán. Použijeme grafické riešenie detekcie dvojnásobných hrán, pretože je viditeľné a ľahšie pochopiteľné.
Z uvedeného vyplýva, že potrebujeme nejakým spôsobom overiť, či sme na mieste, kam sa chystáme robot posunúť už boli, alebo nie. Môžeme (a budeme) sa riadiť farbou bodu. Na zistenie prítomnosti kresby môžeme využiť metódy farbaBodu 
(ktorá zisťuje farbu bodu na pozícii robota) a priehľadnosť (ktorá zisťuje úroveň priehľadnosti určenej farby – nula znamená úplne priehľadný bod, čiže neprítomnosť kresby).
Obohaťme metódu plást o podmienku testujúcu kresbu týmto spôsobom:
~
public void plást(int i)
{
if (i <= 10)
{
// Táto podmienka pribudla:
if (0 == farbaBodu().priehľadnosť())
{
položPero();
dopredu(50);
doľava(60);
plást(i + 1);
doprava(60);
doprava(60);
plást(i + 1);
doľava(60);
zdvihniPero();
dozadu(50);
}
}
}
Po spustení zistíme, že robot sa veľmi rýchlo „zablokuje“ a nakreslí len jednu rovnú čiarku. Je to preto, lebo robot pri posune dopredu kreslí čiaru. Čiara sa končí na tom mieste, kde sa robot zastaví a v dôsledku toho sa nedostane ďalej. (Evidentne, toto nie je vyhovujúce.) Skúsme urobiť opravu. Nech robot kreslí čiaru až pri návrate:
~
public void plást(int i)
{
if (i <= 10)
{
if (0 == farbaBodu().priehľadnosť())
{
// Zmena je tu:
zdvihniPero();
dopredu(50);
doľava(60);
plást(i + 1);
doprava(60);
doprava(60);
plást(i + 1);
doľava(60);
// a tu:
položPero();
dozadu(50);
}
}
}
Po oprave toho robot nakreslí viac, ale stále to je príliš málo (iba šesťuholník). Vždy sa predčasne zablokuje, pretože vždy sa časom dostane do situácie, keď zistí prítomnosť kresby v uzlových bodoch, kde sa šesťuholníky stretávajú a začne sa vracať. Lepšie by bolo zisťovať, či je kresba prítomná v strede hrany, nie v uzloch. Rozdeľme preto prvý posun na polovicu a v prípade, že v strede (hrany) kresbu nenájdeme, budeme postupovať ďalej, inak sa vrátime.
~
public void plást(int i)
{
if (i <= 10)
{
// Najprv sa posunieme o polovicu:
zdvihniPero();
dopredu(25);
if (0 == farbaBodu().priehľadnosť())
{
// Ak kresba nejestvuje, pokračujeme o zvyšnú polovicu:
dopredu(25);
doľava(60);
plást(i + 1);
doprava(60);
doprava(60);
plást(i + 1);
doľava(60);
položPero();
dozadu(50);
}
else
{
// Inak sa vrátime:
dozadu(25);
}
}
}
Robot teraz síce nakreslí o niečo väčšiu časť plástu, ale po čase sa aj tak zablokuje, vráti sa a niektoré čiary nakreslí aj tak viac ráz. Zdá sa, že už nemáme čím náš algoritmus vylepšiť, no opak je pravdou. Potrebujeme „záložný plán.“ Problém je totiž v tom, že by sme potrebovali zanechať stopu informujúcu o tom, že robot určeným miestom prešiel už pri pohybe dopredu, nie až pri návrate (vtedy je už neskoro, preto riešenie nefunguje).
Na to, aby bolo naše riešenie spoľahlivé, potrebujeme iné plátno, ktoré budeme používať výhradne na „poznačenie si“ toho, že robot na tomto mieste už bol (a to už v čase, keď sa pohybuje dopredu). Všetko ostatné zostáva nezmenené. Robot sa vďaka tomu dostane omnoho ďalej, nebude sa viac zbytočne blokovať a nakoniec počas návratu nakreslí všetko, čo treba.
Otázka: „Máme k dispozícii iné plátno?“
Odpoveď: „Áno, našťastie áno.“
Robot môže kresliť na dve plátna. Štandardne sme zvyknutí kresliť na predvolené plátno, ktoré sa nazýva podlahou. Je umiestnené pod robotom, čiže aj kresba na podlahe je zobrazená pod robotom. „Protiľahlé“ plátno sa nazýva strop. Jeho kresba je zobrazená nad robotom. (Čiže keby sme strop úplne zaplnili kresbou, robot by sme už viac neuvideli. Ale to je technický detail, ktorý nás teraz nezaujíma. Dôležité je, že strop jestvuje a že ho môžeme využiť!)
Strop môžeme použiť na to, aby sme si včas (t. j. pri pohybe dopredu) poznačili, že robot na určenom mieste bol. Stačí nakresliť do stredu budúcej hrany bodku (krúžok), ktorú robot pri ďalšom pohybe nájde a podľa toho bude vedieť, že na tomto mieste už bol.
~
public void plást(int i)
{
if (i <= 10)
{
zdvihniPero();
dopredu(25);
// Obrátime pero (aj pozornosť robota) na strop:
kresliNaStrop();
// Teraz metóda farbaBodu() zisťuje farbu bodu na strope:
if (0 == farbaBodu().priehľadnosť())
{
// Aj krúžok bude nakreslený na strope:
kruh(2);
// (Pero je zdvihnuté, takže čiaru robot nenakreslí.)
dopredu(25);
// Zvyšok je takmer rovnaký:
doľava(60);
plást(i + 1);
doprava(60);
doprava(60);
plást(i + 1);
doľava(60);
položPero();
// Jedine tu musíme opäť obrátiť pero – na podlahu:
kresliNaPodlahu();
dozadu(50);
}
else
{
dozadu(25);
}
}
}
Kresba plástu bude vplyvom tohto algoritmu rozmiestnená nerovnomerne. Prestane to prekážať, keď kresbu rozšírime. Musíme zvýšiť stupeň rekurzie. (Pri čísle dvadsaťšesť pokryje plást celé plátno.) Na záver môžeme (v konštruktore) použiť metódu strop.vymažGrafiku(); na vymazanie značiek, ktoré robot priebežne umiestňoval na strope. Po následnom skrytí robota zostane viditeľný iba plást. Rovnomerný a hladký.
Na záver celé riešenie optimalizujeme.
Najprv nahradíme aliasy doprava, doľava a dozadu ich pôvodnými verziami metód vpravo, vľavo a vzad.
~
public void plást(int i)
{
if (i <= 10)
{
zdvihniPero();
dopredu(25);
kresliNaStrop();
if (0 == farbaBodu().priehľadnosť())
{
kruh(2);
dopredu(25);
vľavo(60); // (zmena)
plást(i + 1);
vpravo(60); // (zmena)
vpravo(60); // (zmena)
plást(i + 1);
vľavo(60); // (zmena)
položPero();
kresliNaPodlahu();
vzad(50); // (zmena)
}
else
{
vzad(25); // (zmena)
}
}
}
Potom dôkladne skontrolujeme, v ktorej fáze vykonávania metódy plást má byť pero zdvihnuté a v ktorej položené a v tých častiach algoritmu, v ktorých má byť pero zdvihnuté nahradíme všetky výskyty volaní metód dopredu a vzad ich alternatívami skoč a odskoč :
~
public void plást(int i)
{
if (i <= 10)
{
zdvihniPero();
skoč(25); // (zmena)
kresliNaStrop();
if (0 == farbaBodu().priehľadnosť())
{
kruh(2);
skoč(25); // (zmena)
vľavo(60);
plást(i + 1);
vpravo(60);
vpravo(60);
plást(i + 1);
vľavo(60);
položPero();
kresliNaPodlahu();
vzad(25);
}
else
{
odskoč(50); // (zmena)
}
}
}
Teraz sa zbavíme všetkých volaní metód zdvihniPero a položPero (v podstate každé volanie sa tu vyskytuje len raz):
~
public void plást(int i)
{
if (i <= 10)
{
// zdvihniPero(); // (zmena – vymazanie)
skoč(25);
kresliNaStrop();
if (0 == farbaBodu().priehľadnosť())
{
kruh(2);
skoč(25);
vľavo(60);
plást(i + 1);
vpravo(60);
vpravo(60);
plást(i + 1);
vľavo(60);
// položPero(); // (zmena – vymazanie)
kresliNaPodlahu();
vzad(50);
}
else
{
odskoč(50);
}
}
}
V ďalšom kroku vykonáme dve úpravy naraz:
- Kontrola priehľadnosti farby sa ukázala byť menej vhodná (pretože nesprávne deteguje situáciu, keď robot opustí plátno), preto ju nahradíme porovnaním s inštanciou farby
žiadna. - Zlúčime dvojnásobný výskyt príkazu
vpravo(60)do jedného výskytuvpravo(120).
~
public void plást(int i)
{
if (i <= 10)
{
skoč(25);
kresliNaStrop();
if (farbaBodu(žiadna)) // (zmena)
{
kruh(2);
skoč(25);
vľavo(60);
plást(i + 1);
vpravo(120); // (zmena)
plást(i + 1);
vľavo(60);
kresliNaPodlahu();
vzad(50);
}
else
{
odskoč(50);
}
}
}
V predposlednom kroku vykonáme úpravu, ktorá bude vyžadovať aj zmenu volania metódy plást v konštruktore: prevrátime spôsob fungovania detekcie hĺbky rekurzie tak, aby metóda vyžadovala zadanie kladnej hodnoty, ktorá priamo určí hĺbku rekurzie.
Úpravy priamo v tele metódy súvisia so zmenou prvej podmienky na i > 0 a zmenou znamienka v každom rekurzívnom volaní na plást(i - 1).
~
public void plást(int i)
{
if (i > 0) // (zmena)
{
skoč(25);
kresliNaStrop();
if (farbaBodu(žiadna))
{
kruh(2);
skoč(25);
vľavo(60);
plást(i - 1); // (zmena)
vpravo(120);
plást(i - 1); // (zmena)
vľavo(60);
kresliNaPodlahu();
vzad(50);
}
else
{
odskoč(50);
}
}
}
Zmeny v konštruktore vyžadujú najmä úpravu volania metódy plást, ktorá teraz prijíma kladné číslo.
Ako sme naznačili na konci predchádzajúcej karty, vhodné je tiež vymazanie grafiky stropu po skončení kreslenia plástu (čím sa zmažú všetky krúžkové značky nakreslené na strope).
Môžeme tiež skryť robot a na začiatku konštruktora dočasne vypnúť automatické prekresľovanie, čím sa dramaticky zvýši výkon aplikácie.
Konštruktor môže po týchto úpravách vyzerať napríklad takto:
~
private VčelíPlást()
{
Svet.zbaľ();
// Vypnutie prekresľovania na zlepšenie výkonnosti aplikácie:
Svet.nekresli();
skoč(0, -80);
hrúbkaČiary(1.5);
// Dôležité z dôvodu zmeny princípu detekcie hĺbky rekurzie:
plást(60);
// Vymazanie značiek zo stropu:
strop.vymažGrafiku();
// Skrytie robota, aby na celý výsledok nepôsobil rušivým dojmom:
skry();
// Obnovenie prekresľovania:
Svet.kresli();
}
V poslednom kroku iba definujeme konštantu, ktorej hodnotu využijeme pri všetkých pohyboch vpred a vzad. Celkovo sú v algoritme tri polovičné a jeden celý posun, takže je výhodnejšie definovať konštantu s polovičnou hodnotou: polovica. Jej definícia môže vyzerať napríklad takto (umiestime ju napríklad pred konštruktor):
~
private final static double polovica = 25;
Jej použitie v metóde plást bude vyzerať takto:
~
public void plást(int i)
{
if (i > 0)
{
skoč(polovica); // (zmena)
kresliNaStrop();
if (farbaBodu(žiadna))
{
kruh(2);
skoč(polovica); // (zmena)
vľavo(60);
plást(i - 1);
vpravo(120);
plást(i - 1);
vľavo(60);
kresliNaPodlahu();
vzad(2 * polovica); // (zmena)
}
else
{
odskoč(polovica); // (zmena)
}
}
}
Úplný kód triedy VčelíPlást (s komentármi):
~
import knižnica.*;
public class VčelíPlást extends GRobot
{
// Súkromná konštanta slúžiaca na jednoduchú úpravu veľkosti hrán plástu:
private final static double polovica = 25;
private VčelíPlást()
{
// Prispôsobenie veľkosti okna podľa veľkosti plátna:
Svet.zbaľ();
// Vypnutie automatického prekresľovania na zlepšenie grafickej
// výkonnosti:
Svet.nekresli();
// Posunutie počiatku kreslenia o 80 bodov nadol:
skoč(0, -80);
// Zväčšenie hrúbky čiary:
hrúbkaČiary(1.5);
// Začiatok kreslenia plástu:
plást(60);
// Vymazanie značiek zo stropu:
strop.vymažGrafiku();
// Skrytie hlavného robota:
skry();
// Obnovenie automatického prekresľovania (ktoré zároveň prekreslí
// svet, aby sa prejavil aktuálny stav):
Svet.kresli();
}
public void plást(int i)
{
// Hĺbka rekurzie je určovaná parametrom i, ktorého hodnota má
// klesať k nule:
if (i > 0)
{
// Posunutie (skok) robot o polovicu veľkosti hrany:
skoč(polovica);
// Presmerovanie kreslenia a pozornosti robota na strop:
kresliNaStrop();
if (farbaBodu(žiadna))
{
// Nakreslenie značky (krúžku na strope) a poskočenie
// o zvyšnú polovicu veľkosti hrany:
kruh(2);
skoč(polovica);
// Pootočenie doľava o 60° a vnorenie kreslenia (rekurziou) –
// toto je kreslenie „ľavej vidlice“ plástu z aktuálnej
// pozície:
vľavo(60);
plást(i - 1);
// Pootočenie doprava o uhol 2 × 60° a vnorenie kreslenia
// (rekurziou) – toto je kreslenie „pravej vidlice“ plástu
// z aktuálnej pozície:
vpravo(120);
plást(i - 1);
// Pootočenie do východiskovej orientácie po návrate
// z rekurzií:
vľavo(60);
// Presmerovanie kreslenia na podlahu a nakreslenie hrany
// plástu na aktuálnej pozícii (cúvaním):
kresliNaPodlahu();
vzad(2 * polovica);
}
else
{
// Vycúvanie o polovicu veľkosti hrany (pretože bola nájdená
// značka signalizujúca, že „tu sme už boli“):
odskoč(polovica);
}
}
}
// Hlavná metóda, ktorá iba skonštruuje túto triedu:
public static void main(String[] args) { new VčelíPlást(); }
}
Ukážky okna aplikácie po spustení:
Priebeh kreslenia (keby sme nevypli automatické prekresľovanie).
Výsledný plást.
Plást nakreslený po zmenšení konštanty polovica na hodnotu 10 a zvýšení hĺbky rekurzie na 250.