How to "flatten" or "index" 3D-array in 1D array?
Solution 1
The algorithm is mostly the same. If you have a 3D array Original[HEIGHT, WIDTH, DEPTH]
then you could turn it into Flat[HEIGHT * WIDTH * DEPTH]
by
Flat[x + WIDTH * (y + DEPTH * z)] = Original[x, y, z]
As an aside, you should prefer arrays of arrays over multi-dimensional arrays in .NET. The performance differences are significant
Solution 2
Here is a solution in Java that gives you both:
- from 3D to 1D
- from 1D to 3D
Below is a graphical illustration of the path I chose to traverse the 3D matrix, the cells are numbered in their traversal order:
Conversion functions:
public int to1D( int x, int y, int z ) {
return (z * xMax * yMax) + (y * xMax) + x;
}
public int[] to3D( int idx ) {
final int z = idx / (xMax * yMax);
idx -= (z * xMax * yMax);
final int y = idx / xMax;
final int x = idx % xMax;
return new int[]{ x, y, z };
}
Solution 3
I think the above needs a little correction. Lets say you have a HEIGHT of 10, and a WIDTH of 90, single dimensional array will be 900. By the above logic, if you are at the last element on the array 9 + 89*89, obviously this is greater than 900. The correct algorithm is:
Flat[x + HEIGHT* (y + WIDTH* z)] = Original[x, y, z], assuming Original[HEIGHT,WIDTH,DEPTH]
Ironically if you the HEIGHT>WIDTH you will not experience an overflow, just complete bonkers results ;)
Solution 4
x + y*WIDTH + Z*WIDTH*DEPTH
. Visualize it as a rectangular solid: first you traverse along x
, then each y
is a "line" width
steps long, and each z
is a "plane" WIDTH*DEPTH
steps in area.
Solution 5
You're almost there. You need to multiply Z by WIDTH
and DEPTH
:
Tiles[x + y*WIDTH + Z*WIDTH*DEPTH] = elements[x][y][z]; // or elements[x,y,z]
Tom Zych
Enthusiastic amateur programmer who, despite occasionally being paid for it, cannot yet describe himself as a professional. An amateur practices until he gets it right. A professional practices until she can’t get it wrong.
Updated on July 09, 2022Comments
-
Tom Zych almost 2 years
I am trying to flatten 3D array into 1D array for "chunk" system in my game. It's a 3D-block game and basically I want the chunk system to be almost identical to Minecraft's system (however, this isn't Minecraft clone by any measure). In my previous 2D-games I have accessed the flattened array with following algorithm:
Tiles[x + y * WIDTH]
However, this obviously doesn't work with 3D since it's missing the Z-axis. I have no idea how to implement this sort of algorithm in 3D-space. Width, height and depth are all constants (and width is just as large as height).
Is it just
x + y*WIDTH + Z*DEPTH
? I am pretty bad with math and I am just beginning 3D-programming so I am pretty lost :|PS. The reason for this is that I am looping and getting stuff by index from it quite a lot. I know that 1D arrays are faster than multi-dimensional arrays (for reasons I cant remember :P ). Even though this may not be necessary, I want as good performance as possible :)
-
Dominic K over 12 yearsAm I correct in saying you want a 3D array to be fit into a 1D array?
-
svick over 12 yearsWhy don't you just use 3D array?
-
Admin over 12 years@DMan Yes, that's correct.
-
-
svick over 12 yearsCould you point to some source discussing the performance differences? Also, you shouldn't base your decisions just on performance.
-
hatchet - done with SOverflow over 12 years
-
Gideon Engelberth over 12 years@svick: Some sources can be seen in the links hatchet provided. My performance note was only an aside and not the main suggestion. Jagged arrays have nearly identical syntax (original[x][y][z]), but do take more work to initialize. However, the performance benefits can become quite noticeable (2-5x speedup) depending on the usage.
-
jking almost 11 yearsI can't upvote or comment on the real correct answer, but Martin has it correct, the current selected answer is wrong. Essentially: data[x][y][z] = data[x + ymaxX + zmaxX*maxY]
-
Jonathan Lidbeck over 10 yearsIf HEIGHT corresponds to the Y dimension, it should be:
Flat[x + WIDTH * (y + HEIGHT * z)] = Original[x, y, z]
-
chilleo about 8 yearsyep current answer is wrong, should be height not depth. took me too long to figure this out as its the first time ive actually used a wrong SO answer to code something >.<
-
Kuba Chrabański over 4 yearsTested almost all other answers, only this one translates nested for-loops (x < width, y < height, z < depth) to arrays indexes from 0 to width * height * depth (ordered)
-
Jamie Nicholl-Shelley over 3 yearsCould you help me confirm what the pattern would be for 4D, or 5D etc
-
murage kibicho over 2 yearsThis is the right answer
-
hellowill89 over 2 yearsIt's unclear in this answer whether xMax means
WIDTH
orWIDTH-1