4                  Drugi primer: Slagalica

Slagalica predstavlja sliku podeljenu na m*n pravougaonika, koji se izmešaju tako da slika ne može da se prepozna. Cilj igrača jeste da sliku ponovo složi pomeranjem njenih delova. Delovi se nalaze u ravni, a postoji jedno polje viška (van slike, recimo levo iznad) koje obezbeđuje kretanje pravougaonika prema “rupi”, pri čemu se rupa pomera omogućavajući na taj način pomeranje drugih delova.

Druga varijanta sadrži delove sa upisanim brojevima koji se takođe izmešaju i zadatak postaje slaganje delova u redosledu po svojim brojnim oznakama. Varijacija ovoga je obeležavanje delova sa rednim brojem vrste i kolone u kojima delovi na kraju treba da se nađu.

Slika prikazuje izgled slagalice formata 3*3 pre slaganja (levo) i nakon slaganja (desno). Postoji interaktivna verzija slagalice gde igrač pomera delove slagalice kliktanjem na njih – u ovom slučaju je posao prepušten Flashu i ActionScriptu. Korisnik može da utiče na broj vrsti i kolona, odnosno dimenziju slagalice, da zada komandu za generisanje početnog problema klikom na dugme deli i nakon generisanja da zada komandu za traženje optimalnog rešenja (najmanji broj poteza) na dugme reši. Po nalaženju rešenja delovi se pomeraju kroz generisanu animaciju, brojač poteza beleži pomeranja delova, a kraj svega je po završetku animacije – svi delovi se nalaze na svojoj ciljnoj poziciji a vrednost brojača poteza je broj poteza u minimalnom rešenju.

Za realizaciju ovako predstavljenog problema potrebno je obezbediti generisanje početnog problema na osnovu zadatih dimenzija, pogodnu strukturu i algoritam za traženje rešenja i odgovarajuću grafičku reprezentaciju rešenja.

4.1          Generisanje početnog problema

Kako postoji m*n delova, pravi se niz brojeva odgovarajuće dimenzije koji se potom izmeša.

Ovde je myNumber jednak baš m*n, tako da se nakon for petlje dobija niz brojeva od nule do myNumber - 1. Sada se niz myArray izmeša na neki dopustiv način. U tu svrhu dodeljuje mu se metod scramble:

Za validnost mešanja odgovorna je promenjiva odd, jer rešivost zavisi od parnosti permutacije elemenata niza. Ideja je da se slučajno vade elementi niza i stavljaju na kraj, pri čemu se vodi računa o tome da se bira od preostalih elemenata niza. Prvo se na kraj prebacuje vodeći element, jer se njemu odgovarajući deo nalazi pored rupe i pomeranjem tog dela se uopšte omogućava kretanje ostalih delova. Potom se kroz for petlju obezbeđuje mešanje ostalih elemenata niza i na kraju, kada preostanu samo dva neizmešana, u zavisnosti od vrednosti odd, određuje se u kom redosledu će oni biti postavljeni na kraj niza. Preostaje samo pozivanje metoda:

Ovakav niz spreman je za generisanje odgovarajuće strukture za početni problem.

4.2          Struktura

Prirodna struktura po opisu problema je matrica odgovarajućeg formata koja sadrži elemente, recimo objekte, koji vode računa o potrebnim informacijama. Matrica je promenljiva matrix kojoj su pridružena dva metoda za pretragu nad njenim elementima: search i newSearch.

4.2.1     Element matrice

Element matrice je objekat kreiran konstruktorom kome se prosleđuju tri parametra: vrsta i kolona elementa u matrici, i inicijalni movieClip objekat (deo slagalice). Konstruktor povezuje prosleđeni movieClip objekat pod nazivom mov, postavlja njegovu početnu vizuelnu poziciju, izračunava, na osnovu prosleđene vrste i kolone, poziciju u nizu, te vrednost elementa niza na nađenoj poziciji dodeljuje mov kao vrednost osobine value i na osnovu ove vrednosti izračunava ciljnu vrstu i kolonu, vrednosti osobina row i column objekta mov i konačno postavlja vrednost tekstualnog polja u objekta mov, koja predstavlja ciljnu vrstu i kolonu. Konstruktor takođe uvodi i osobinu tree koju postavlja na null, o čemu će biti više napomena dalje u tekstu.

4.2.2     Stablo pretraživanja

Prilikom pretraživanja se u stvari nad elementima matrice vrši zamena mov objekata čime se simulira kretanje elemenata slagalice u cilju traženja rešenja. Tako se u stvari menja sadržaj matrice i dolazi se do novih stanja matrice. Stanja matrice mogu se reprezentovati vrednostima value mov objekata, po redosledu kako se oni javljaju u elementima matrice. Ove vrednosti mogu se poređati u niz. Na ovaj način, niz myArray odslikava početno stanje matrice. Broj mogućih pozicija u igri je velik, iznosi (myNumber! / 2), tako da pogodna struktura za izvođenje pretraživanja mora biti u najmanju ruku binarno stablo. Čvorovi stabla imaju jedinstveni identifikator čvora, a zbog potrebe poređenja se niz myArray na početku prevodi u string promenljivu IDnode, koja predstavlja vrednost tekućeg čvora tokom pretraživanja. Svaki element matrice ima osobinu tree, što predstavlja drvo svih posećenih čvorova kod kojih se rupa nalazi na poziciji tog elementa matrice. Na ovaj način urađena je distribucija svih čvorova po elementima matrice. Čvorovi, pored svog identifikatora i pokazivača na elemente levog i desnog podstabla, poseduju još nekoliko osobina od kojih su najvažnije, za čvorove koji se nađu na putu konačnog rešenja, smer (direction) kretanja rupe ka stanju koje predstavlja čvor i pokazivač na sledeći čvor puta (next). Po uspešnom završetku pretrage tako je moguće odrediti putanju rupe koja početno stanje prevodi u krajnje.

4.3          Algoritam pretraživanja

Sama pretraga funkcioniše po algoritmu backtrackinga. Inicijalno se pretpostavlja da rešenje mora biti kraće od neke predefinisane vrednosti, uzima se da je to vrednost dužine rešenja i pri nalaženju svakog kraćeg rešenja se ova vrednost postavlja na dužinu nađenog rešenja. Promenljivoj matrix pridruženi su metodi search i newSearch. Parametri ovih metoda su vrsta i kolona tekućeg elementa matrice, broj poteza i smer pretrage. Metod search traži čvor nad stablom elementa matrice, vodi računa o određenim odsecanjima (tekući broj poteza ne može biti veći od vrednosti nađenog rešenja, posećeni čvor koji nije na putu rešenja nije od interesa, posećeni čvor koji se poseti u potezu većem od prethodne posete nije na najboljem putu...), detektuje prvo rešenje, ažurira čvorove pri nalaženju kraćih rešenja, upućuje na dalju pretragu (traži naredni čvor) u dozvoljenim smerovima (dozvoljen smer je mogući smer, onaj smer koji neće izaći van dimenzija matrice) pozivom metoda newSearch i, u pogodnom trenutku, vraća čvor ili null u slučaju neuspele pretrage. Metod newSeach se bavi administrativnim stvarima, poput pripreme nove vrednosti promenljive IDnode, zamene mov objekata elemenata matrice. Po obradi svih pripremnih radnji inicira novu pretragu (poziva search), nakon čega restaurira prethodno stanje i vraća rezultat.

Deo koda metoda search:

Promenljiva myNode predstavlja nađeni čvor koji odslikava poziciju pretrage. Kada se program nađe u ovom delu koda to znači da su preskočena sva odsecanja i da postoji potreba za daljom pretragom. Zato se povećava vrednost parametra moveNum koji će se prosleđivati metodu newSearch, jer se radi o narednom potezu (ovo se radi samo jednom). Pretpostavlja se da se čvor ne nalazi na putu rešenja, a ako se nađe da jeste, to će biti zabeleženo. Uslov kaže da se pretraga na gore može izvoditi samo u slučaju da se ne nalazimo u najgornjoj vrsti matrice (nulta vrsta). Sledeći uslov ispituje uspešnost pretrage na gore i, ako je ispunjen, zaključuje se da se čvor nalazi na putanji i da je nađen njegov sledeći čvor. Slično se ispituje i za ostale smerove, desno, dole i levo, koje vraćaju čvor samo ako je pronađen kraći put. Na kraju:

Ako je čvor na putu, postavlja mu se odgovarajući smer ulaza i vraća se čvor, inače je pretraga neuspešna i vraća se null.

4.4          Animacija

Kada rešenje postoji, koristi se najveća prednost Flasha – animacija. Na ovom mestu od pomoći je slika vremenske ose simbola elementa slagalice:

Vide se tri lejera. Gornji lejer sadrži labele objekta, srednji kod, a na donjem lejeru nalazi se objekat koji se animira. Po instanciranju objekta automatski kreće da se odvija njegova vremenska komponenta. Kako inicijalno nije potrebna nikakva animacija, u lejeru code ubacuje se instrukcija stop (); koja prekida dalje kretanje vremenske ose. Takvo stanje zadržava se sve do nalaženja rešenja i do prozivanja objekta da izvrši neku animaciju. Poziv mu se upućuje instrukcijom gotoAndPlay koja kao parametar ima naziv labele frejma od koje treba da nastavi sa odvijanjem animacije.

Ukoliko, na primer, element slagalice treba da se kreće gore, dobija instrukciju gotoAndPlay (“up”). Pomera se na početni frejm labele up, gde se u lejeru object nalazi objekat na svojoj startnoj poziciji (crna tačka u lejeru označava ključni frejm). Poslednji frejm grupe up takođe sadrži ključni frejm u lejeru object, gde se nalazi objekat pomeren nagore za visinu objekta. Strelica u lejeru object između ključnih frejmova označava animaciju, zadatak Flashu da distribuira promene stanja objekta po frejmovima između dva ključna frejma. Malo slovo “a” u lejeru code predstavlja ključni frejm sa kodom u ActionScriptu. To je sledeći kod:

Prva linija koda privremeno “gasi” objekat, druga ga pomera za jednu visinu (80) nadole (zato što je animacijom za toliko otišao gore) i treće pomera objekatat na labelu base, koja “pali” objekat (setProperty (this, _visible, true);) i nakon pauze od nekoliko frejmova:

Daje se instrukcija programu da može da nastavi sa animacijom i zaustavlja svoju animaciju. Funkcija animate prati tok rešenja i daje direktive za izvođenje animacije:

Na početku animacije solution je prvi čvor rešenja. Niz actions sadrži funkcije koje vode računa o tome koji element slagalice treba da se pozove na animaciju, vodeći računa o smeru. Uočena funkcija pridružuje se objektu hole kao metod action, koji se odmah i poziva i na taj način inicira se animacija potrebnog elementa matrice. Objekat hole svojim metodom action, odnosno funkcijama iz niza actions, vodi računa o poziciji rupe, zadaje komande mov elementima za za kretanje u određenom smeru i vrši razmenu mov elemenata u okviru matrice pri pomeranju.

4.5          Perfomanse

Algoritam backtrackinga je izuzetno nezahvalan u interaktivnim sistemima, povećanjem dimenzije problema višestruko se uvećava broj operacija algoritma. Kod slagalice, pri testiranju programa, uočava se da je dobijanje rešenja na slagalici formata 2*2 gotovo trenutno, slično je i sa formatima 2*3 i 3*2, dok format 3*3 na novijim računarima daje odziv u roku od nekoliko desetina sekundi do minuta, što se može proceniti kao dovoljno za demonstraciju, ali nedovoljno za interaktivnu primenu. Dozvoljen format 4*4 stoga nije ni testiran.

Ovakvi rezultati daju ideju za testiranje brzine Flasha i ActionScripta. Funkcija getTimer vraća broj milisekundi proteklih od startovanja programa i može se iskoristiti za merenje vremena nalaženja rešenja na sledeći način:

Po izvršenju ovog dela koda promenljiva time sadržava broj milisekundi proteklih prilikom nalaženja rešenja. Za samo testiranje je napravljen novi program.

4.5.1     Program za testiranje

Program sadrži niz od pet predefinisanih ulaznih stringova koji odgovaraju različitim početnim problemima. Selekcijom određenog testa i pritiskom na dugme “do the job” program startuje sa izvršavanjem, kreira se struktura i izvršava algoritam pretrage, nakon kojeg se u desnom delu prikazuju rezultati testa: redni broj testa, ulazni niz, dužina nađenog rešenja, rešenje (kao niz smerova koji bi se redom dodeljivali elementima pri animaciji, 0 je gore, 1 desno, 2 dole i 3 levo) i izmereno vreme pretraživanja. Sam algoritam je uprošten, odnosno traži se samo prvo rešenje, ne i optimalno.

4.5.2     Merenje i rezultati merenja

Testiranje je obavljeno korišćenjem opisanog programa za testiranje, na PC platformi sa procesorom AMD Duron na 700 MHz i 256 MB RAM memorije, sa operativnom sistemom Microsoft Windows XP Professional, Version 2002.

Vršeno je tri tipa testova: testiranje tzv. projektorskih izvršnih fajlova (Flash kreira izvršni fajl tako što upakuje plejer i aplikaciju, tako da se projektor može izvršavati i na sistemima gde nisu instalirani Flash ni Flash plejer), testiranje .swf fajlova iz samostalnih aplikacija Flash plejera, i testiranje u okruženju web browsera.

Takođe je sam program za testiranje rađen u tri verzije: kompilacijom iz Flasha 5 (Test Slagalica Flash 5), iz Flasha MX (Test Slagalica Flash MX), i iz Flasha MX sa opcijom podrške za plejer Flasha 5 (Test Slagalica Flash MX as Flash 5).

Jedno testiranje sastoji se od po pet merenja svakog testa. Jedna tabela za primer:

Pet kolona sa brojevima predstavlja rezultate (broj milisekundi proteklih pri traženju rešenja) pet merenja testova (po vrstama). Poslednja kolona sadrži prosečnu vrednost svih merenja jednog testa. Tokom svih testova uočeno je da se odstupanje vrednosti pojedinačnih merenja od proseka kreće do granice od 1-2% (u većini testova su ova odstupanja i manja). Slika desno prikazuje relativni odnos prosečnih vremena po testovima. Pokazalo se da je ovaj odnos konstantan pri svim testiranjima, tako da je za dalju analizu dovoljno da se koristi samo suma proseka svih testova (gornje levo polje u tabeli).

Sledeća tabela sadrži sume proseka svih testova (druga kolona tabele).

U tabeli se koriste sledeće oznake za browsere:

·        MS IE – Microsoft Internet Explorer 6.0.2600.0000.xpclient.010817-1148

·        Opera – Opera 5.01 build 840

Oba browsera imaju plug-in za Flash Player 6.

Isti podaci pregledniji su na grafikonu dole:

Rezultati govore, pre svega, u korist novog plejera, oko 9 (!) puta bolje vreme u odnosu na stari plejer (oznaka 1 je izvršni fajl sa ugrađenim plejerom Flasha 5, 4 je .swf Flasha 5 iz njegovog plejera, i oznaka 5 .swf iz Flasha MX za Player 5 iz Playera 5). Takođe, vrednosti merenja verzije iz Flasha 5 (1, 4, 6, 9, i 12) i Flasha MX za Player 5 (3, 5, 8, 11 i 14) se gotovo poklapaju, dok verzija iz Flasha MX za Player 6 (2, 7, 10 i 13) daje vrednosti slabije za oko 5%. Vrednosti postignute u projektorima (1-3) bliske su vrenostima postignutim u samostalnim plejerima (4-8),  a merenja u Internet Exploreru (9-11) daju rezultate slabije za oko 2%, u Operi (12-14) za oko 25% slabije rezultate u odnosu na samostalni plejer.