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

Josef Kuchař - Pepa489

Tvůrce

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

David Hynek

Tvůrce

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.

Jan Vargovský

Tvůrce

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č

Nahoru Odpovědět

31.5.2015 16:44

Josef Kuchař - Pepa489

Tvůrce

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

Jan Vargovský

Tvůrce

Jan Vargovský:31.5.2015 17:44

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

Nahoru Odpovědět

31.5.2015 17:44

David Hynek

Tvůrce

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.

Josef Kuchař - Pepa489

Tvůrce

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

Jan Vargovský

Tvůrce

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

Josef Kuchař - Pepa489

Tvůrce

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

Jan Vargovský

Tvůrce

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

Drahomír Hanák

Tvůrce

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

Drahomír Hanák

Tvůrce

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

Josef Kuchař - Pepa489

Tvůrce

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

Drahomír Hanák

Tvůrce

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 d₁, d₂, ..., d_n 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 % (d₁ * d₂ * ... * d_(n-1)), (n-1)D) pro 0 < j < n
v_j(i, nD) = floor(i / (d₁ * d₂ * ... * d_(n-1))) pro j = n

Jsou dány souřadnice v₁ až v_n:
V = [v₁, v₂, ..., v_n] je n-vektor
D = [1, d₁, d₁ * d₂, ..., (d₁ * d₂ * ... * 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

Tomáš Maňhal

Člen

Tomáš Maňhal:1.6.2015 12:10

Nesnáším matematiku...oprávněně :-D :-D

Nahoru Odpovědět

1.6.2015 12:10

Luboš Běhounek Satik

Tvůrce

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/

coells

Tvůrce

coells:1.6.2015 14:51

http://en.wikipedia.org/…/Mixed_radix

Nahoru Odpovědět

1.6.2015 14:51

Josef Kuchař - Pepa489

Tvůrce

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

Luboš Běhounek Satik

Tvůrce

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/

Josef Kuchař - Pepa489

Tvůrce

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

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:1.6.2015 16:28

https://www.google.cz/?…

Nahoru Odpovědět

1.6.2015 16:28

https://www.facebook.com/peasantsandcastles/

Josef Kuchař - Pepa489

Tvůrce

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

Luboš Běhounek Satik

Tvůrce

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/

Luboš Běhounek Satik

Tvůrce

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

Nahoru Odpovědět

1.6.2015 17:43

https://www.facebook.com/peasantsandcastles/

Josef Kuchař - Pepa489

Tvůrce

Josef Kuchař - Pepa489:1.6.2015 18:25

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

Nahoru Odpovědět

1.6.2015 18:25

2x piš, jednou debuguj

Patrik Pastor

Člen

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

Nejčastěji vyhledáváné

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