Weblabor

Elég sűrűn előfordul egy weblapnál, hogy a sok képfájl miatt nyitott sok HTTP kapcsolat lelassítja az oldal betöltődését. Ezen sprite-okkal szoktak segíteni. Ezt úgy kell elképzelni, hogy fogunk egy nagy (jobb szó híján) vásznat, amire feltesszük az összes kis képet, amit az adott oldal be akar tölteni. Ezek után lementjük ezt a vásznat egy képfájlba, az oldal pedig egyetlen HTTP kapcsolattal ezt a fájlt szedi le, és darabolja fel ismét a megadott koordináták szerint css segítségével. A sprite készítést természetesen érdemes automatizálni. Én is ebbe kezdtem bele.

A sprite-ok készítésénél a lényegi kérdés, hogy hogyan helyezzük el egymás mellé a kis képeinket. A matematika nyelvére lefordítva ez annyit tesz, hogy vannak különböző méretű téglalapjaink, és ezeket szeretnénk elrendezni egymás mellett úgy, hogy az eredmény a lehető legközelebb legyen egy téglalaphoz. Tegyük fel, hogy mondjuk nem téglalap alakban rendezzük el a képeinket, hanem mondjuk kör alakban. Az eredmény kicsit kisarkítva, vagy inkább kerekítve valami ilyesmi lesz:



Ez egy 100x100-as kép, szóval az átmérő az 100px. Tehát a kör által a vásznon foglalt terület: d^2*pi/4, ami 7854 px^2. A teljes vászon területe viszont 10 000 px^2. Szóval rengeteg kihasználatlan terület található a sprite-ban, amiben átküldenénk a kör alakban összerendezett képeinket. Emiatt kell, hogy a képek összerendezésével kapott alakzat téglalapra hasonlítson, mert ugye minél jobban hasonlít egy téglalapra, annál kisebb rajta a kihasználatlan terület, és annál kevesebb felesleges adatot küldünk át a sprite-unkkal.

Nyilván nem rakhatunk össze minden egyes sprite-ot kézzel, mert az rengeteg időt elvinne, ezért valamilyen csomagoló algoritmust kell használnunk, ami elvégzi helyettünk a munkát.

Milyen adatokat használhat egy ilyen algoritmus?

A képek, a képcsoportok és a vászon tulajdonságai:

• szélesség: w {px}
  
• magasság: h {px}
  
• átmérő: d=sqrt(w^2+h^2) {px}
  
• képarány: r=w/h {}
  
• terület: A=w*h {px^2}
  

Vannak egyszer a téglalapok tulajdonságai, amelyeket ugye a képekre és a vászonra is meghatározhatunk. A szélesség, a magasság és az átmérő elég egyértelmű, ahogy a terület is.

A képarány, ami egy kicsi többletinformációval bír, hiszen abból meg lehet mondani a téglalap alakját. Ha r<1 (w<h), akkor álló téglalapról, ha r>1, akkor fekvő téglalapról, ha r=1, akkor pedig négyzetről van szó. További érdekesség ezzel kapcsolatban, hogyha olyan csoportokat alkotunk a képekből, amelyek szintén téglalap alakúak, akkor ezekre ugyanúgy használhatóak a fenti tulajdonságok. Így mondjuk négy egyforma nagyságú négyzetet lehet úgy kombinálni, hogy a csoport fekvő vagy álló téglalapot, de akár négyzetet is alkothat.

A csoportok és a vászon tulajdonságai

• hézag: g=A(csoport)-sum(A(képek)) {px^2}
  

A hézag a csoport területe és a benne található képek területe közötti különbség, amit százalékban is megadhatjuk a képek összterületéhez viszonyítva. A vászon pedig az a csoport, aminek a minimális hézag méretét keressük. Ezt nem biztos, hogy úgy érjük el, hogy az egyes csoportok hézagmérete a lehető legkisebb. Nagyon sokat számít az, hogy ezeket a csoportokat hogyan tudjuk összeilleszteni. Ez körülbelül ugyanaz, mint amit a tetrisznél is csináltunk.

A legegyszerűbb algoritmus

Csoportokban gondolkodó algoritmust elég nehéz leprogramozni, vannak azonban ennél jóval egyszerűbb megoldások is.

Szinte mindig onnan indulunk, hogy csoportosítjuk az építőelemeinket. Ezt megtehetjük a fenti tulajdonságok szerint.

A legegyszerűbb algoritmus az, ha egymás mellé vagy alá rakjuk a képeinket magasság vagy szélesség szerint sorba rendezve.



Ennél már kicsit bonyolultabb az, ha fogjuk a fenti ábrán látható képeket, és elkezdjük egymásra pakolni úgy, hogy fokozatosan csökkentjük a szélességet, ahogy az az alábbi ábrákon látható.











Ilyen módon fokozatosan csökken a hézag területe egészen az összes kép területének 36%-áig. Ennél jelen esetben kézzel sem tudnánk jobb eredményt kihozni.

Vannak azonban olyan helyzetek, amikor ez az algoritmus nem a legjobb eredményt adja:









Mint látható, itt a normál algoritmussal nem tudunk elérni 17% hézagnál jobb eredményt, azonban kézzel könnyedén ki lehet rakni a hézagmentes változatot.



Az olyan algoritmusok, amelyek erre képesek nyilván már bonyolultabbak. Ha érdekel titeket a téma szívesen várom az ötleteket, hogy mi alapján lehetne ilyen algoritmust fejleszteni, illetve ha találtok neten ilyen algoritmusokat, akkor azok szintén gazdagítanák ennek a leírásnak az értékét.

Amit még lehet csinálni az ötletelésen kívül, hogy kézzel kirakunk egy csomó sprite-ot, lementjük a koordinátákat, illetve a csoportok jellemzőit. Ezek után meg lehet próbálni data mininggal kinyerni az adatokból, hogy az egyes esetekben milyen tulajdonságú csoportok a leghatásosabbak, majd az ebből készült adatbázis felhasználható a sprite-ok készítésére, esetleg új algoritmusok gyártására.