Chytrý algoritmus pro renderování 2D izom. mapy?

[Crypton]

Zdravím ve spolek,

potřeboval bych poradit s jedním problémem ohledně algoritmu pro renderování isometrické mapy, která je ve tvaru diamatu (né "staggered"), protože strýček Google mi nic neporadil, a na GameDev.net mi taky nikdo neporadil...

Viz můj příspěvek:
http://www.gamedev.net/community/forums/topic.asp?topic_id=578795

Jde o to že mám algoritmus pro renderovaní té mapy napsaný, jen je až nechutně pomalý (max 15FPS), protože renderuje 9 bloků mapy najednou, a já bych potřeboval zjistit které bloky viditelné a jaké dlaždice z nich vyrenderovat.

Mapa je rozdělena na několik menších bloků (kde jeden blok má 32x32 dlaždic), které se pak načítají během hraní (v novém vlákně), no a abych pokryl celou oblast, a všechny "rohy", musím načíst ty bloky do matice 3x3 bloků, kde kamera/hráč je uprostřed, tedy v bloku m[1][1]. Mimichodem, jeden ten blok je jako malá mapa, je tak rozsáhlý že se celý nevyrenderuje na obrazovku.

Tady je ten algoritmus:

[Quiark]

Tak co mě jako prvního napadlo. Možná existuje nějaké standardní řešení, ale couž.

Potřebuješ zjistit, které dlaždice kreslit a které ne. Počítám, že jeden blok kreslíš po řádcích (viz zelené šipky na obrázku), takže pro každý takový řádek je třeba zjistit, která je první dlaždice vidět a která je poslední vidět a ostatní nekreslit.

První dlaždice ke kreslení je ta, která koliduje s horním nebo pravým okrajem obrazovky (pokud se to kreslí v pořadí co ukazují zelené šipky). To se dá zjistit tak, že provedeme výpočet kolize daného pruhu (=řádku) dlaždic s daným okrajem obrazovky. Konkrétně pro kolizi s horním okrajem použijeme spodní okraj pruhu dlaždic, pro pravý okraj obrazovky pak ten horní.

Ze vzorečku na výpočet průsečíku dvou přímek dostaneme mimo souřadnic průsečíku (které nepotřebujem) taky parametr t, neboli pozici na přímce okraje pruhu dlaždic. Tento parametr, pokud máme úsečku okraje dlaždic správně vyjádřenou, nabývá hodnot 0 až 1 a z počtu dlaždic na tom pruhu jde zjistit, do které dlaždice to spadlo.

Správně vyjádřená úsečka okraje dlaždic je, když její počátek je na jednom jejím okraji a směrový vektor má délku shodnou s délkou úsečky. Pokud nevíš, co to plácám, nastuduj si parametrické vyjádření přímky/úsečky (analytická geometrie pro střední školy).



Rekapitulace pojmů:
pruh dlaždic - to vpravo
obrazovka - to červené
horní okraj pruhu dlaždic - světle modrá úsečka na obrázku vpravo
spodní okraj pruhu dlaždic - žlutá úsečka ...

EDIT: ujasnění
_________________
Mám strach

[pet]

Máš někde nějaký přehled časů, kolik trávíš v jednotlivých metodách? Když říkáš, že renderTile to neovlivňuje, jak vypadají getTileDrawPos a isTileOffscreen?

Jinak určitě by šlo přeskočit vícero dlaždic v okamžiku kdy jsi už část kreslil a najdenou ti vyjde, že dlaždice vidět není - nebudou vidět ani ty další v této řádce.

Podobně by šlo vypočítat pozici první dlaždice a poslední dlaždice v řádce a otestovat v jaké poloze leží vůči obrazovce - což vlastně pěkně popsal Quiark.

[Crypton]

Quiark:

Přesně moje situace, díky moc podrobné za vysvětlení, doufám že jsi ty obrázky nedělal jen kvůli mě Jinak už jsem to jakž takž pochopil, spíš je problém to implementovat, takže bych se chtěl zeptat jestli nemáš nějaký snippet a nebo nevíš o nějakém open-source projektu kde se vykresluje ve tvaru diamantu. (Na matiku mi to teď fakt nepálí )

Totiž, počátek kamery je v mém případě uprostřed obrazovky, a né v pravém/levém horním rohu, jak jsem si všimnul u jiných projektů, k tomu pohyb kamery je po dlaždicích a né pixelech, takže funkce getCameraPos vrací absolutní lokaci kamery v dané mapě. Ještě bych možná měl zmínit že se s kamerou nemůžu pohybovat mimo mapu, tedy rozsah pohybu kamery je taky ve tvaru diamantu.

pet:
Testoval jsem to přes AMD CodeAnalyst, podle toho jsem zjistil že se nejvíce času tráví právě v těch cyklech. Je to totiž 9216 iterací, v každé se volá getTileDrawPos, která vlastně převede vypočítá kde se má ta dlaždice vykreslit, no a pak se funkcí isTileOffscreen zjistí zdali se má ta dlaždice vykreslit, podle toho jestli se nachází mimo obrazovku či ne.

Ať už smažu jakýkoliv řádek v tom posledním cyklu (např. renderTile), pořád je to pomalé, ale když smažu celý ten algoritmus tak FPS vyskočí na 1300+, což je asi logické, ale ten rozdíl je obrovský, na to že vykresluju zajím jen dlaždice.

Jinak díky za tipy a rady, kouknu se na to až se pořádně vyspím, jsem totiž asi hodně přepracovaný a nebo totálně blbý

[Quiark]