- Časopis Quark - https://www.quark.sk -

Nekonečný tetris

Populárnu hru tetris vytvoril ruský herný dizajnér Alexej Leonidovič Pažitnov v roku 1984. Mal za úlohu otestovať výkonnostné možnosti nového hardvéru a rozhodol sa urobiť to práve vytvorením novej počítačovej hry.

Pokúšal sa zreplikovať stolovú hru pentomíno, v ktorej je cieľom uložiť 18 rôznych tvarov zo štvorcovej siete do vopred určených foriem. Zistil, že tvarov je príliš veľa a hra by bola komplikovaná. Chcel vytvoriť oddychovú hru, preto zredukoval počet tvarov na sedem.

Nákazlivé skladanie kociek

Cieľom hry tetris je ukladať tvary padajúce z vrchnej časti plochy tak, aby sformovali celý plný riadok, ktorý následne zmizne. Riadky nad ním sa posunú nižšie a na hracej ploche sa uvoľní miesto. Tvary aj hracia plocha majú základ na štvorcovej sieti. Tvorením riadkov hráč získava body a usiluje sa ich nahrať čo najviac ešte predtým, ako tvary dosiahnu vrchnú časť hracej plochy. Postupom času sa zrýchľuje padanie tvarov.
Existuje nespočetné množstvo verzií tetrisu. Hra sa stala veľmi populárnou pre svoju jednoduchosť a zároveň návykovosť. Presahuje generácie a kultúry, vyskúšal si ju naprogramovať hádam každý začínajúci programátor. Tetris nájdeme v starých prvých mobilných telefónoch, malých hracích konzolách do ruky, bežných stolných počítačoch alebo rôznych online verziách, v ktorých je možné súperiť s hráčmi z celého sveta.


Každé tetromíno má svoje oficiálne meno.

Oficiálna verzia hry

Vždy však zostane iba jeden originál. Ten obsahuje štandardizovaný náhodný generátor padajúcich tvarov, zobrazovanie nasledujúceho tvaru a možnosť podržania si tvaru a jeho odloženie na neskôr. Usporiadanie nekonečného algoritmu, ktorý vyprázdni plochu presne po použití 20 náhodných balíčkov.

Usporiadanie nekonečného algoritmu, ktorý vyprázdni plochu presne po použití 20 náhodných balíčkov.

Oficiálna veľkosť viditeľnej hracej plochy je 10 × 20 štvorcov. Poradie tvarov určuje náhodný generátor, ktorý má v balíčku vždy iba práve daných sedem tvarov, a vypustí ich postupne všetky v náhodnom poradí. Potom sa balíček opäť naplní a proces sa opakuje. Nie je tak možné, aby išli po sebe tri rovnaké tvary, alebo aby sa niektorý tvar veľmi dlho neobjavil. V oficiálnej verzii sa rýchlosť hry nezvyšovala a dalo sa hrať až do naplnenia hracej plochy. Všetkých sedem tvarov má dokonca svoje oficiálne mená a ako skupina tvarov sa nazývajú tetromína. Všeobecne ich však môžeme pomenovať podľa písmena, ktoré pripomínajú. Máme
teda sedem tvarov: T, Z, S, L, J, O a I.

Matematická otázka

Všetky tieto pravidlá oficiálnej verzie otvárajú otázku, či je možné hrať tetris donekonečna. Hraciu plochu si rozdeľme na tri časti: ľavé štyri stĺpce, pravé štyri stĺpce a dva stredné stĺpce. Každej z týchto častí plochy priradíme konkrétne tvary. Ľavá časť pre tvary T, Z a S, pravá časť pre tvary L, J a O a stredná časť pre tvar I. Ľavú časť začneme plniť s tvarom T ako základom, na ktorý uložíme po dva tvary Z a S chrbtom k sebe. Následne umiestnime dva tvary T oproti sebe, opakujeme tvary S a Z s vymenenými pozíciami a celok uzavrie opäť tvar T. Vznikol nám ucelený vzor obdĺžnika, ktorý sa opakuje po štyroch náhodných balíčkoch. S poradím padania tvarov pre ukladanie v správnom poradí nebude problém, pretože použijeme funkciu podržania tvaru, pokiaľ aktuálne nevyhovuje. Jeden podržaný tvar stačí pre správne fungovanie algoritmu. Pravá strana je jednoduchá. Tvary L a J uložíme oproti sebe a medzi ne umiestnime tvar O. Vzor sa opakuje už po jednom náhodnom balíčku. V strednej časti budú vedľa seba dva tvary I, vzor opakujúci sa po dvoch balíčkoch.
Po vyčerpaní ôsmich celých náhodných balíčkov takto tvary vyplnia celú plochu a riadky zmiznú. Nie však všetky, pretože nemáme dostatok tvarov I. Túto chybu vykompenzujeme dvomi doplňujúcimi algoritmami vzorov pre pravú a strednú časť. Po ich dvoch opakovaniach ich dvakrát zopakujeme aj s vymenenou pravou a ľavou stranou a výška tvarov sa doplní, hracia plocha sa úplne vyprázdni. A môžeme pokračovať donekonečna.

Text a foto Stanislav Griguš
Fakulta matematiky, fyziky a informatiky
Univerzita Komenského v Bratislave
Videá autora nájdete na YouTube kanáli To ako prečo?.

Tento článok si môžete prečítať v časopise Quark 7/2021. Ak ešte nie ste našou predplatiteľkou/naším predplatiteľom a chcete mať prístup k exkluzívnemu obsahu, objednajte si predplatné podľa vášho výberu tu.