Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Nejlepší způsob pro uchování "3d" pole

Aktivity
Avatar
Josef Kuchař - Pepa489:31.5.2015 14:54

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
Tvůrce
Avatar
Odpovídá na Josef Kuchař - Pepa489
David Hynek:31.5.2015 16:36

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ý
Tvůrce
Avatar
Odpovídá na Josef Kuchař - Pepa489
Jan Vargovský:31.5.2015 16:44

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í
+2,50 Kč
Řešení problému
 
Nahoru Odpovědět
31.5.2015 16:44
Avatar
Odpovídá na Jan Vargovský
Josef Kuchař - Pepa489:31.5.2015 17:16

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ý
Tvůrce
Avatar
Jan Vargovský:31.5.2015 17:44

... 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
Tvůrce
Avatar
Odpovídá na Josef Kuchař - Pepa489
David Hynek:31.5.2015 18:08

:)ž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:31.5.2015 18:30

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ý
Tvůrce
Avatar
Odpovídá na Josef Kuchař - Pepa489
Jan Vargovský:31.5.2015 18:46

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:31.5.2015 18:52

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ý
Tvůrce
Avatar
Odpovídá na Josef Kuchař - Pepa489
Jan Vargovský:31.5.2015 19:05

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
Odpovídá na Josef Kuchař - Pepa489
Drahomír Hanák:31.5.2015 19:45

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
31.5.2015 19:45
Avatar
Odpovídá na Drahomír Hanák
Drahomír Hanák:31.5.2015 19:56

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:31.5.2015 20:00

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
Odpovídá na Drahomír Hanák
Drahomír Hanák:1.6.2015 12:00

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.6.2015 12:00
Avatar
Odpovídá na Drahomír Hanák
Tomáš Maňhal:1.6.2015 12:10

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

 
Nahoru Odpovědět
1.6.2015 12:10
Avatar
Luboš Běhounek Satik:1.6.2015 13:01

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.6.2015 13:01
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Luboš Běhounek Satik
Josef Kuchař - Pepa489:1.6.2015 15:21

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:1.6.2015 15:51

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
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Luboš Běhounek Satik
Josef Kuchař - Pepa489:1.6.2015 16:07

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
Nahoru Odpovědět
1.6.2015 16:28
https://www.facebook.com/peasantsandcastles/
Avatar
Odpovídá na Luboš Běhounek Satik
Josef Kuchař - Pepa489:1.6.2015 16:36

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:1.6.2015 17:38

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
https://www.facebook.com/peasantsandcastles/
Avatar
Luboš Běhounek Satik:1.6.2015 17:43

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
https://www.facebook.com/peasantsandcastles/
Avatar
Josef Kuchař - Pepa489:1.6.2015 18:25

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
Avatar
Odpovídá na David Hynek
Patrik Pastor:9.3.2019 22:16

muzes prosim vysvetlit podrobneji? Nerozumim proc by 8cka byla 2.2

 
Nahoru Odpovědět
9.3.2019 22:16
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 26 zpráv z 26.