Végtelen térkép generálás bármely irányba 2017. október 1., vasárnap - 23:03


Ahogy visszanéztem gyorsan, ez az első tényleg programozással kapcsolatos bejegyzésem. Amikor a blogot kezdtem, úgy voltam vele, hogy itt mindenféle elmélet és megoldás lesz ezen belül. És gondoltam, hogy azért előtte lesz pár bejegyzés, de hogy 51 bejegyzést írjak előtte (több, mint 1 éven át), amiből csak pár darab hajazott a programozásra.. :D (A node.js szenvedésem is csak hasonló volt, de ott a telepítésen volt a hangsúly, nem a használatán.)

Bevezető off.
Szóval:

Ahogy a cím is mutatja - a napokban elkezdtem a szabadidőmben (amikor épp nincs semmi fontos egyéb) egy Minecrafthoz hasonló, de 2D játékot csinálni. Mindezt természetesen multiplayer formába öntve, hiszen mit ér az alkotás, ha nem láthatja senki az eredményt? Mariocraft a kódneve, mert egyébként - jobb híján - Mario a főkarakter, egyelőre.
( Meg hát egy hálózaton játszható játék külön fényévekkel jobb, a legtöbb esetben. )


(Jobbra a kicsit újabb, árnyékos verzió látható.)

És ha már ilyen Minecraft-Terraria típusú játékba kezdtem, eszembe jutott egy olyan téma, amiről szívesen hallanám mások véleményét, megoldási módjait, hátha tanulhatok és/vagy van jobb, mint amit én ismerek. A Facebookos Amatőr játékfejlesztők csoportban feltettem a kérdésem, ami egy elég jó kis közösség - és pár aktív tagja között igazán nagy koponyák vannak, akik nagyon régóta űzik az ipart.


Kaptam is jó néhány választ, néhány még új információ is volt – tehát megérte a kérdést feltenni. Tanulhattam kicsit.

Összefoglalva: a kérdés, téma lényege az, hogy a legtöbb egyszerű játékban elég az, ha a játéktér térképe egy kétdimenziós tömb (főleg a csempéből felépülő játékoknál - erről van egy nagyon jó tutorial itt. Leír mindent, hogy miért jó ez, miért hasznos.).

Ez annyit tesz, hogy csak "egyirányúan" bővíthető a tér. A számítógépen a leggyakoribb módszer a 2D játékoknál (top-down view "felülnézetes", sidescroller "platform, mászkálós"), hogy a nullpont a bal felső sarok. Onnan indul ki a térkép összerakása, és tart egészen a jobb alsóig.
Ez pont kézenfekvő, hiszen a térképet tömbben szokás tárolni, a tömbök indexelése 0-tól indul, és tart N-ig. A tömb dinamikus is lehet, tehát nem lehetetlen, hogy akár játék közben IS nőhessen a pálya mérete. De csak (az előbbit alapul véve) jobbra, és lefelé.

És mi van, ha én egy Minecrafthoz hasonló játékot akarok, de oldalnézetből? Vagy valami katonás, akármilyen játékot felülnézetből? És mondjuk hasonló, generált térképpel, hogy az az érzésem legyen, hogy bármerre mehetek?

Erre több megoldás is van.

Volt, aki azt mondta pl. (Oli volt, csekkoljátok az oldalát, rengeteg jó játékot csinált már! Java és HTML5 főként. Az én kedvencem pl. a JAVA minigolf játéka.),
hogy ez megoldható azzal, ha a tömb elejére szúrunk be új elemeket (ha a mínusz irányokba haladunk), és/vagy csúsztatjuk a tömb elemeit (inkább ezt írta, csak nekem elsőre beszúrás ugrott be, de az sem butaság, amennyiben feljegyezzük, hogy mennyivel lett csúsztatva a pálya, és ezt minden koordinátájához hozzáadjuk. Akkor ránézésre nem mozdul semmi sehova, de mégis nő a pálya mérete.) Ha csak csúsztatunk az elemeken, és ami kicsúszik, az elvész, akkor nem jó az ötlet egy dinamikus pályával rendelkező játékhoz, de egyébként igen.

Volt, aki hasonló, indexeléses módszert írt, seed alapon generálással (így simán csak ugyanazt generálja a játék az adott helyen, ha visszatérünk oda). Ez akkor nem jó, ha változtatható a pálya. Mint jelen esetben.

Kaptam egy Circular buffer nevű módszert, amit még nem olvastam el részletesen, de ez is új infó nekem, ennek egy változatát már használtam, anélkül, hogy tudtam volna róla, meg arról, hogy mi ez.

Még páran írtak, egy elég jó kis beszélgetés lett belőle.

Az én módszerem annyi, hogy adott egy (Minecraft megnevezéssel) chunk, egy darabka, egy részlet a pálya egészéből. Ez magába foglal N*N további kis játékelemet, "csempét" (tile-t). A Minecraftban ez 16x16x16 méretet jelent (mert 3D), de a mérete mindegy. Lényegében ezen chunkoknak is van egy koordinátája, ami ugyanúgy 0, 1, 2, stb., de egy ilyen koordinátán N*N elem található. Úgy is mondhatjuk, hogy az 1/N-ed része a pályának egy chunk.
Bár a pályát, a chunkok tartalmát tömbökben tárolom én is, de magukat a tömböket objektumok értékeként. A tulajdonság pedig egy string, egy szöveg, ami tartalmazza a chunk koordinátákat is.
Mivel ez egy szöveg, ez mehet negatív egész számba is, hiszen az is szöveg. Hivatkozásképp van használva, kicsit úgy, mint egy asszociatív tömb. Így nem is lassít semmit (érzékelhetően), annak ellenére, hogy string.

Ez kicsit zagyva lehet, de épp ezért gyorsan megírtam működőben is, hogy tesztelhető, látható legyen, mire gondolok. Így nem elég, hogy "negatív indexbe", mármint koordinátára is mehetünk a játékon belül, de ez generálható a végtelenségig, mert ugyanúgy dinamikus, és még a tömböket sem kell birizgálni, ha újabb tér tárul fel, így nincs plusz processzorhasználat sem.

Ide kattintva megnézhető a kis tesztem.
Az irányítás is egyszerű: a kurzorbillentyűk a vörös téglalapot mozgatják. A WASD pedig az egész nézetet, amit csak látunk.

A vörös téglalap mutatja a játékos képernyőjét; ha ez egy játék lenne, azt a területet látná be a játékos. Ahogy látható, mindig előre betöltődik annyi, amennyi szükséges, a chunkokból. A kirajzolás persze nem így történne, hiszen ez nem túl takarékos, de a bemutató célja nem is az volt.
A két kék vonal szimbolizálja a nullpontot, az X és Y tengelyt, amitől "jobbra" és "lefelé" szokás a pályát építeni alapesetben - de itt ugye átléphető minden irányba, bármekkora távolságra.



Egyébként a barátommal beszélgettem, miközben beugrott egy sokkal egyszerűbb módszer is, ami ugyanezt eredményezi.


Ez pedig annyi, hogy négy térkép tömb van, ami tárolja a pályát. Általában egy van, de ha vesszük a két tengelyt, akkor az 4 részre osztja a pályát, és pont az a gond a tömbbel, hogy nincs negatív index.
De ha van egy topright, bottomright, bottomleft és topleft tömböm, amik a négy teret szimbolizálják, akkor már más a helyzet. A bottomright-ot használjuk ugyanúgy, mint alapból szokás. Az összes többi pedig a tükörkép. Mielőtt dolgoznánk a tömbünkben, előtte egy vizsgálat eldönti, hogy melyik tömbben dolgozunk a 4 közül. Ha negatív az X, akkor értelemszerűen left lesz, különben right. Ha az Y negatív, akkor pedig top lesz, különben bottom. És már csak annyi az extra, hogy a tömbhöz használt index-számot, ami egyébként koordináta (valószínűleg), annak az abszolút értékét használjuk, bármelyik tömbben is dolgozunk. Így a mínuszból plusz lesz, és egy sokkal egyszerűbb módszert kapunk a 4 irányba való generáláshoz, szintén végtelenségig (hiszen dinamikus ugyanúgy lehet mind).

De ezt most nem valósítom meg, el lehet képzelni. :)

Ezért szép a programozás, végtelen megoldás van ugyanarra a "problémára", még ha némelyik nem is a legjobb.