Avatar
Josef Kuchař (Pepa489):

Ahoj,
Pokouším se o tvorbu hry a potřebuji uchovat trojrozměrné pole, zatím používám pro vytvoření prázdného pole asi nejjednoduší metodu:

function createMapArray()
{
        map = new Array(MAP_X);
        for (var i = 0; i < MAP_X; i++)
        {
        map[i] = new Array(MAP_Y);
    }

        for (var i = 0; i < MAP_X; i++)
        {
        for (var j = 0; j < MAP_Y; j++)
        {
                map[i][j] = new Array(MAP_Z);
                }
        }
}

Ale v hodně 2d hrách když se ukládá mapa používají autoři jednorozměrné pole pro uložení x,y tak, že index vydělí x a spočítají souřadnice, takže mě napadlou jestli není lepší pro uložení 3d pole tohle:

function createMapArray()
{
        map = new Array(16);
        for (var i = 0; i < 4; i++)
        {
        map[i] = new Array(MAP_Y);
    }
}

Co mám použít? Nebo existuje lepší řešení?

Odpovědět 31.5.2015 14:54
2x piš, jednou debuguj
Avatar
David Hynek
Redaktor
Avatar
Odpovídá na Josef Kuchař (Pepa489)
David Hynek:

pole[1][1][1] a takhle ti to nejde?

Nahoru Odpovědět 31.5.2015 16:36
Čím víc vím, tím víc věcí nevím.
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Josef Kuchař (Pepa489)
Jan Vargovský:

Všude v herním průmyslu se ukládá n-dimenzionální prostor do 1D, indexuješ pomocí matematiky a 1d pole. Důvod je takový, že hledání v souvislém bloku paměti + výpočet indexu je jednodušší než hledání n-krát.

Akceptované řešení
+20 Zkušeností
+1 bodů
Řešení problému
 
Nahoru Odpovědět  +2 31.5.2015 16:44
Avatar
Odpovídá na Jan Vargovský
Josef Kuchař (Pepa489):

Díky, ale u trojdimenzionálního pole si převod z/do 1D nedokážu pořádně představit, mohl by jsi mi klidně nejavasciptově ukázat jak takové 2x2x2 pole může být zapsané v 1D? Díky

Nahoru Odpovědět 31.5.2015 17:16
2x piš, jednou debuguj
Avatar
Jan Vargovský
Redaktor
Avatar
Jan Vargovský:

... Já si refreshnul stránku a zmizlo to :D umíš reprezentovat 2D v 1D?

 
Nahoru Odpovědět 31.5.2015 17:44
Avatar
David Hynek
Redaktor
Avatar
Odpovídá na Josef Kuchař (Pepa489)
David Hynek:

:)že by 1,2,3,4,5,6,7,8 kde 1, je souřadnice 0,0 a 8 pak 2,2

Nahoru Odpovědět 31.5.2015 18:08
Čím víc vím, tím víc věcí nevím.
Avatar
Odpovídá na Jan Vargovský
Josef Kuchař (Pepa489):

Už jsem přišel na to jak to reprezentovat, ale jak získat z 1D pole souřadnice x y z a naopak?

Nahoru Odpovědět 31.5.2015 18:30
2x piš, jednou debuguj
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Josef Kuchař (Pepa489)
Jan Vargovský:

Jednoduše to přesně nezjistíš. To ale nezjistíš ať máš to pole reprezentováno jakkoliv.

 
Nahoru Odpovědět 31.5.2015 18:46
Avatar
Odpovídá na Jan Vargovský
Josef Kuchař (Pepa489):

Proč to nemůžu zjistit, v prvním případě při tomto zápisu to nemusím nijak převádět: map[x][y][z] je hodně špatné, když to budu mít tak jak jsem to měl původně?

Nahoru Odpovědět 31.5.2015 18:52
2x piš, jednou debuguj
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Josef Kuchař (Pepa489)
Jan Vargovský:

Ty si uchováváš x,y,z, jen pro get/set to prostě dáš do fce a ona ti zajistí ten převod a vrátí/nastaví potřebnou věc. Já myslel, že se ptáš jak zjistit index z hodnoty na tom prvku.

Ohledně toho co použít. Je to úplně jedno, pracuj s tím, s čím se ti líp pracuje. Až budeš dělat optimalizace, tak využiješ určitě 1D pole.

Editováno 31.5.2015 19:08
 
Nahoru Odpovědět 31.5.2015 19:05
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na Josef Kuchař (Pepa489)
Drahomír Hanák:

Pokud máš ve 3D kvádr o délce W, tloušťce D, výšce H, kde W, D, H jsou celá čísla, pak ho můžeš rozdělit na stejně velké krychle o velikosti 1 tak, že pro krychli i na souřadnicích [x, y, z] platí i = x + y * W + z * WD

Pokud máš index i a znáš W, D, pak můžeš vypočítat souřadnice [x, y, z]. WD je počet prvků na jedné úrovni z => j = i % WD je index ve 2D poli na úrovni z (ta je pro index j stejná), takže x = j % W, y = floor(j / W) a pak jen dopočítáš z = floor(i / WD). Nakonec dosadíš j za i a vyjde ti:

x = (i % (WD)) % W
y = floor / W)
z = floor(i / WD)

(Kde floor je funkce, která zaokrouhlí číslo dolů)

Jinak nevidím problém v použití trojrozměrného pole. Dokud nezaznamenáš významný pokles výkonu, nemá podle mě smysl řešit něco jiného.

Editováno 31.5.2015 19:46
 
Nahoru Odpovědět  +2 31.5.2015 19:45
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na Drahomír Hanák
Drahomír Hanák:

Všiml jsem si, že se nějak špatně interpretoval ten výraz pro y. Je to y = floor ( (i % WD) / W )

 
Nahoru Odpovědět 31.5.2015 19:56
Avatar
Odpovídá na Drahomír Hanák
Josef Kuchař (Pepa489):

Díky moc vám oboum, zatím použiji 3d pole a poté to převedu do 1d a zjistím jestli to pro mě má nějaký smysl :)

Nahoru Odpovědět 31.5.2015 20:00
2x piš, jednou debuguj
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na Drahomír Hanák
Drahomír Hanák:

Nedalo mi to a musel jsem se to pokusit zobecnit pro n-rozměrný prostor. Objekt o rozměrech d1, d2, ..., dn jde rozdělit na podobjekty o velikosti 1 tak, že pro objekt na indexu i lze vypočítat souřadnice v_j pro všechna j v přirozených číslech v intervalu <1, n> rekurentním vzorcem:

v_j(i, nD) = v_j(i % (d1 * d2 * ... * d_(n-1)), (n-1)D) pro 0 < j < n
v_j(i, nD) = floor(i / (d1 * d2 * ... * d_(n-1))) pro j = n

Jsou dány souřadnice v1 až vn:
V = [v1, v2, ..., vn] je n-vektor
D = [1, d1, d1 * d2, ..., (d1 * d2 * ... * d_(n-1))] je n-vektor,
pak index(V, D) = dot(V, D) (skalární součin V, D)

 
Nahoru Odpovědět  +1 1.6.2015 12:00
Avatar
tomasmanhal
Člen
Avatar
Odpovídá na Drahomír Hanák
tomasmanhal:

Nesnáším matematiku...o­právněně :-D :-D

Nahoru Odpovědět 1.6.2015 12:10
Kdyby nám dodali k životu zdrojový kód, vše by bylo jednodušší...
Avatar
Luboš Běhounek (Satik):

Tenhle způsob ukládání prostoru je rychlý, ale pokud ho budeš zvětšovat nebo posílat po síti / ukládat na disk, brzo narazíš na limit paměti.

Řešením může být třeba Octree, pokud ten prostor není příliš členitý v celém svém objemu.

Nahoru Odpovědět  +1 1.6.2015 13:01
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Josef Kuchař (Pepa489):

Takže když to uložím jako 1D pole, bude soubor větší, než kdybych ho ukládal jako 3d pole?

Nahoru Odpovědět 1.6.2015 15:21
2x piš, jednou debuguj
Avatar
Odpovídá na Josef Kuchař (Pepa489)
Luboš Běhounek (Satik):

Ne.
Ale ve 3D roste množství dat pro uložení 3D pole se třetí mocninou - i prázdné pole o hraně 1000 jednotek při velikosti prvku 1 bajt už bude velké 1000 x 1000 x 1000 bajtů, tedy cca jeden GB.
Octree naproti tomu bude zabírat místo podle členitosti mapy - pokud je většina mapy jen volný prostor, tak ten volný prostor octree dokáže uložit jako jeden velký blok a nemusíš ukládat stav všech těch volných jednotek (krychlí) uvnitř toho volného prostoru.

Editováno 1.6.2015 15:51
Nahoru Odpovědět 1.6.2015 15:51
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Josef Kuchař (Pepa489):

Ale jak to mám v javascriptu implementovat (klidně zjednodušeně)?

Nahoru Odpovědět 1.6.2015 16:07
2x piš, jednou debuguj
Avatar
Odpovídá na Luboš Běhounek (Satik)
Josef Kuchař (Pepa489):

To už jsem hledal, nemohl bys napsat něco konkrétního?

Nahoru Odpovědět 1.6.2015 16:36
2x piš, jednou debuguj
Avatar
Luboš Běhounek (Satik):

Koukni se na quadtree - to je 2D verze toho algoritmu, tam to třeba pochopíš líp - např. na wiki http://en.wikipedia.org/wiki/Quadtree

Nahoru Odpovědět 1.6.2015 17:38
:)
Avatar
Luboš Běhounek (Satik):

V podstatě jde o to, že čtverec, na kterém daný bod leží, dělíš, dokud nenajdeš dostatečně malý odpovídající čtverec.

Každý ten čtverec má odkazy na své 4 podčtverce, tam, kde jsou ukazatele nulové, tam je obsahem toho zbytku čtverce nějaká hodnota, kterou má ten čtverec u sebe.

Takhle se to blbě vysvětluje, chce to vidět ten obrázek, tam to snad pochopíš lépe :D

Nahoru Odpovědět 1.6.2015 17:43
:)
Avatar
Josef Kuchař (Pepa489):

Už to chápu, teď jen nevím jak to v javascriptu zařídit :D

Nahoru Odpovědět 1.6.2015 18:25
2x piš, jednou debuguj
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 25 zpráv z 25.