Jump to content
  • Advertisement
Sign in to follow this  
coderWalker

Accessing tiles in a tilemap

This topic is 2554 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am having a hard time understanding how to access tiles in a 3d tile-map.

I have the tile map split into sections. Each section is 16x16x16 tiles.

In the game there is a 3d ptr array (section) that is 11x11x11;
Each of these positions contains a pointer to one of the sections.

So it's like this:

TileMap
-Sections
-Tiles

At the bottom I have some code I am currently using.

This routine to find the targeted tile is called hundreds to thousands of times per frame.
Meaning I think this code is a major slowdown in my game.

There has to be a faster way to access tiles in the map.
Has anyone tried implementing something like this?
Any ideas?

I know there has to be a faster-way.
I had an idea the other day, but have forgotten it.
Something with %16 ? Then using the Offset?

Is the current method the best possible or ridiculously slow?

Thanks
CoderWalker


/*
ChunkOffset is the amount of sections away from the center section the players on 5x5x5.
tmpChunk is the Section that the target tile is in.
tmpPoint is the position the tile is in that section.
*/

//Get full offset in blocks not chunks
x-=(xChunkOffset*16);
y-=(yChunkOffset*16);
z-=(zChunkOffset*16);
//Round to closest Block
tmpPoint.z=align(z);
tmpPoint.y=align(y);
tmpPoint.x=align(x);
//Get X Chunk
tmpOffset.x=0;
while (tmpPoint.x>=16)
{
tmpPoint.x-=16;
tmpOffset.x+=1;
}
while (tmpPoint.x<0)
{
tmpPoint.x+=16;
tmpOffset.x-=1;
}
//Get Y Chunk
tmpOffset.y=0;
while (tmpPoint.y>=16)
{
tmpPoint.y-=16;
tmpOffset.y+=1;
}
while (tmpPoint.y<0)
{
tmpPoint.y+=16;
tmpOffset.y-=1;
}
//Get Z Chunk
tmpOffset.z=0;
while (tmpPoint.z>=16)
{
tmpPoint.z-=16;
tmpOffset.z+=1;
}
while (tmpPoint.z<0)
{
tmpPoint.z+=16;
tmpOffset.z-=1;
}
//Apply the Offsets
tmpOffset.x+=HALFCLIPDIST;
tmpOffset.y+=HALFCLIPDIST;
tmpOffset.z+=HALFCLIPDIST;

Share this post


Link to post
Share on other sites
Advertisement
Note: I may be misunderstanding what you are saying. It sounds like you want to get an element (a tile) out of a 3 dimensional array, and your X,Y,Z relative to the center of the array (That is, the position 0,0,0 is in the center of the array in every dimension).


This is easy enough to do, once you realize that even though you are pretending it's a 3D array, the computer's memory isn't 3D, nor is it 2D, it's only 1D, and so your 3D array is actually only a 1D array. So let's treat it like one. smile.gif

Let's simplify this first, by doing it one dimension at a time. If you have a tile array, called oneDimensionalArray, and you want to get the tile 'x' out of it, you do it like this:
oneDimensionalArray[ x ]
Easy!

For two dimensions, we need to also take into account the width of the array, because the array is not stored like this:
pic0x.png


It's actually stored like this: (spaces between rows added for easier reading - in actual memory, there are no gaps between the rows)
pic1jx.png


So to access the two dimensional array, all we really need to do is still use the same method as before ( oneDimensionalArray[ x ] ), but offset it by the width of the array multiplied by the row we want to access.
twoDimensionalArray[ (y * width) + x ]

For example, to access the third row (y = 2 since it starts at 0), and the 3rd column, we get twoDimensionalArray[ (1 * width) + 2 ], which gets us:
pic2o.png


[hr]

So let's move on to the third dimension.
For the first dimension when we use 'X', think of this as X times the size of the cell, which in your case, each cell is 1, so we just exclude that multiplication.

First dimension, to get the cell: X times size of Cell
Second dimension, to get the row: Y times size of Row
Third dimension, to get the layer: Z times size of Layer

So we have:
threeDimensionalArray[ (z * width * height) + (y * width) + x ]

Or to simplify through additional variables:
threeDimensionalArray[ (Layer * LayerSize) + (Row * RowSize) + (Cell * CellSize)]

Where the variables are:
Layer = Z, Row = Y, and Cell = X
LayerSize = Width * Height
RowSize = Width
CellSize = 1

And since we can omit the cell size (since X times 1 is still X):
threeDimensionalArray[ (Layer * LayerSize) + (Row * RowSize) + Cell]

This scales up to however many dimensions you want, whether it be three dimensions or three hundred.

[hr]

Since you start at the center of the array, you can just resolve the actual position before getting the index of the array:

Tile &GetTile(int x, int y, int z)
{
//Convert the position from the center of the map to the upperleft corner, like it's stored in memory.
int realX = (MapWidth / 2) + x;
int realY = (MapHeight / 2) + x;
int realZ = (MapDepth / 2) + x;

int tileIndex = (realZ * MapWidth * MapHeight) + (realY * MapWidth) + realX;
return map[ tileIndex ];
}


[hr]

Note: For the formulas I showed you to work, DO NOT have C++ create a Three-Dimensional array. Have C++ create a One-Dimensional array, and treat it like a 3D one. Because C++ might think the data is being stored one way (for example, row first and then column) and you might think it's being stored another way (for example,. column first and then row).

Don't do this:
MyArray = new Tile[Depth] [Height] [Width];

Do this:
MyArray = new Tile[ (Width * Height * Depth) ];

[hr]

Ofcourse, when you are looping over the entire array you don't want to waste time with the function call overhead, for every iteration of the loop, so for actual looping, you do it all in one run:

//The outer loops go: z, y, x, instead of x, y, z, because I prefer the game to loop over
//the tiles in the same order that I mentally think of the tiles. If you take a moment
//and think about the difference between the inner loop being 'x', you'll see what I mean.
for(int z = 0; z < MapDepth; z++)
{
for(int y = 0; y < MapHeight; y++)
{
for(int x = 0; x < MapWidth; x++)
{
int tileIndex = (z * MapWidth * MapHeight) + (y * MapWidth) + x;

Tile &tile = map[ tileIndex ];

tile.Draw(...);
}
}
}


This can even be further optimized by avoiding the resolving of the index of the array on every loop (all the multiplications), by doing pointer arithmetic. But we don't need to do that, because now I'll tell you an even cooler secret: Remember that our array is actually just a 1-dimensional array pretending to be a 3-dimensional array? Well, for hard loops, we can just treat it like a one-dimensional array. Observe:

int TotalSize = (MapDepth * MapHeight * MapWidth);

for(int index = 0; index < TotalSize; index++)
{
Tile &tile = map[ index ];

tile.Draw(...);
}


Because after all, it is just an array, wink.gif

Share this post


Link to post
Share on other sites
Servant of the Lord, thanks for all the information! That explains alot and helps alot to speed things up with the individual array access.

However the main concern is how to access the elements when thier spead across multiple arrays.

I must split the map and use pointers because it would take to long to shift an array that contains (16^3*25^3) tiles.

I'll try to explain better, lets work with just a 2d tile map this time.

Refer to the image attached.
[attachment=2402:grid.png]

Each of the Black squares is a section of the map.
Each of the Orange squares is a tile in the map.

Basically the map is split into sections.
I have pointers to each of the sections and 16x16 arrays inside of each of them.

What would be the easist way to access each of the tiles in the arrays.
I need to access them to change them, instead of just read them.

Right now I am using offsets from the center of the map to move to other positions,
however this can be dropped if Absolute positions would be faster than absolute positions.

Share this post


Link to post
Share on other sites
You can use relative or absolute positions, it doesn't matter what - just use whichever is easier for you. Just convert it to absolute positions when you need to access the tiles.

Your problem is the same as what I mentioned above, with one minor difference: You have (logically) two separate 3D arrays: The [color="#1c2837"]SectionArray that holds pointers to each section, and each section has a TileArray that holds pointers to each Tile. It's the same concept, just apply it twice.

To draw every tile, or whatever you are doing, go like this: (for when you need to loop over every section or tile - much faster)
int TotalMapSize = (NumSectionsDeep * NumSectionsHigh * NumSectionsWide);

int TotalSectionSize = (NumTilesDeep * NumTilesHigh * NumTilesWide);

for(int section = 0; section < TotalMapSize; section++)
{
Section *section = SectionArray[ section ];

//WARNING: I'm assuming that your 'section' is not NULL, or your program will crash.

for(int tile = 0; tile < TotalSectionSize; tile++)
{
Tile *tile = section->TileArray[ tile ];

tile.Draw(...);
}
}


Or like this: (For getting a single section or tile when you need it, much more precise)
Section *GetSection(int x, int y, int z)
{
//WARNING: I'm assuming that your 'x', 'y', and 'z' are not out of bounds, or your program will crash.
//They should be between negative '(NumSectionsWide / 2)' and positive '(NumSectionsWide / 2)'.

int realX = (NumSectionsWide / 2) + x;
int realY = (NumSectionsHigh / 2) + y;
int realZ = (NumSectionsDeep / 2) + z;

int tileIndex = (realZ * NumSectionsWide * NumSectionsHigh) + (realY * NumSectionsWide) + realX;
return SectionArray[ tileIndex ];
}

Tile &GetTileFromSection(Section *section, int x, int y, int z)
{
int realX = (NumTilesWide / 2) + x;
int realY = (NumTilesHigh / 2) + y;
int realZ = (NumTilesDeep / 2) + z;

int tileIndex = (realZ * NumTilesWide * NumTilesHigh) + (realY * NumTilesWide) + realX;
return section->TileArray[ tileIndex ];
}

Share this post


Link to post
Share on other sites
The only problem is I still have to use the slow code above to figure out which Chunk and what Tile.
Wait, does your code do that?

Basically I want a get tile function that basically returns a pointer to that specific tile.
ex:
tile* get_tile(int x, int y, int z);

call to:
get_tile(40,20,15)

would return:
Section[2][1][0]->tile[8][4][15];

just how to calculate these positions?

Also, even just calculating a tile position takes a lot of math.
Would there be a faster-way of doing this? ( I mean anything faster, even totally diffrent)

*just using 3d arrays in the example to simplify the pseudo code.


This is the code I'm trying to replace:

/*
ChunkOffset is the amount of sections away from the center section the players on 5x5x5.
tmpChunk is the Section that the target tile is in.
tmpPoint is the position the tile is in that section.
*/

//Get full offset in blocks not chunks
x-=(xChunkOffset*16);
y-=(yChunkOffset*16);
z-=(zChunkOffset*16);
//Round to closest Block
tmpPoint.z=align(z);
tmpPoint.y=align(y);
tmpPoint.x=align(x);
//Get X Chunk
tmpOffset.x=0;
while (tmpPoint.x>=16)
{
tmpPoint.x-=16;
tmpOffset.x+=1;
}
while (tmpPoint.x<0)
{
tmpPoint.x+=16;
tmpOffset.x-=1;
}
//Get Y Chunk
tmpOffset.y=0;
while (tmpPoint.y>=16)
{
tmpPoint.y-=16;
tmpOffset.y+=1;
}
while (tmpPoint.y<0)
{
tmpPoint.y+=16;
tmpOffset.y-=1;
}
//Get Z Chunk
tmpOffset.z=0;
while (tmpPoint.z>=16)
{
tmpPoint.z-=16;
tmpOffset.z+=1;
}
while (tmpPoint.z<0)
{
tmpPoint.z+=16;
tmpOffset.z-=1;
}
//Apply the Offsets
tmpOffset.x+=HALFCLIPDIST;
tmpOffset.y+=HALFCLIPDIST;
tmpOffset.z+=HALFCLIPDIST;

Share this post


Link to post
Share on other sites

The only problem is I still have to use the slow code above to figure out which Chunk and what Tile.
Wait, does your code do that?

No it doesn't, but it's easy for you to adapt, if you put in the effort. smile.gif

Basically I want a get tile function that basically returns a pointer to that specific tile.
ex:
tile* get_tile(int x, int y, int z);[/quote]

If you're calling 'get_tile()' many times in a for() loop, you need to be accessing the array directly instead of calling 'get_tile()'. If you're calling 'get_tile()' for every tile in the map or even just one section, you're doing it wrong, and it will go ridiculously slow.

Section[2][1][0]->tile[8][4][15];[/quote]
Don't use the myArray[x][y][z] format of array access. Treat it as a single array, like I've explained above. It's easier to work with.

just how to calculate these positions?[/quote]

int sectionX = (originalX / 16);
int sectionY = (originalY / 16);
int sectionZ = (originalZ / 16);

int tileX = (originalX % 16);
int tileY = (originalY % 16);
int tileZ = (originalZ % 16);

Do you understand how modulus works? If not, now's a good time to learn!
Don't just copy and use my code, but learn how it works. smile.gif

If the above code is still too slow for you, then it's because you are calling get_tile() too many times, and you need to access the array directly and properly as I've explained in previous posts. If you still don't understand (after making an honest and actual attempt to figure it out based on the information I already posted), then you need to post how you are planning on using the code, and not just what you expect the code to do.

Share this post


Link to post
Share on other sites
I totally understand how this works.

However when I replaced the following with the new version the game starts thowing errors.
Showing a tile is a certain one when it's not, etc.

The question is why?
I thought they would return the same results?


//Get X Chunk
tmpOffset.x=0;
while (tmpPoint.x>=16)
{
tmpPoint.x-=16;
tmpOffset.x+=1;
}
while (tmpPoint.x<0)
{
tmpPoint.x+=16;
tmpOffset.x-=1;
}
//Get Y Chunk
tmpOffset.y=0;
while (tmpPoint.y>=16)
{
tmpPoint.y-=16;
tmpOffset.y+=1;
}
while (tmpPoint.y<0)
{
tmpPoint.y+=16;
tmpOffset.y-=1;
}
//Get Z Chunk
tmpOffset.z=0;
while (tmpPoint.z>=16)
{
tmpPoint.z-=16;
tmpOffset.z+=1;
}
while (tmpPoint.z<0)
{
tmpPoint.z+=16;
tmpOffset.z-=1;
}




int sectionX = (originalX / 16);
int sectionY = (originalY / 16);
int sectionZ = (originalZ / 16);

int tileX = (originalX % 16);
int tileY = (originalY % 16);
int tileZ = (originalZ % 16);

Share this post


Link to post
Share on other sites

I totally understand how this works:

int sectionX = (originalX / 16);
int sectionY = (originalY / 16);
int sectionZ = (originalZ / 16);

int tileX = (originalX % 16);
int tileY = (originalY % 16);
int tileZ = (originalZ % 16);


However I implemented this and it's giving incorrect answers?
Is something in this math incorrect?


Well, have you debugged it to find out under what circumstances it gives incorrect answers?
What have you done to problem-solve this problem? mellow.gif

Which numbers give you the wrong results, and what results are you expecting?

Two hints: The modulus and divide operators aren't broken. Neither is your compiler.
This means either I made a mistake in the math (which is possible) or you made a mistake implementing it (also possible), or there's some circumstance that we're overlooking or not thinking through (like what happens when 'originalX' is 0).

So the question is, what are you doing to isolate the problem? Programming is not about knowing the right information to type in to the computer, programming is about problem-solving when that information wasn't as right as originally thought.

Since I'm not the one trying to run your program, I can't answer the question "Is something in this math incorrect?". You have to tell me that. wink.gif

Share this post


Link to post
Share on other sites

Since I'm not the one trying to run your program, I can't answer the question "Is something in this math incorrect?". You have to tell me that. wink.gif


Man thanks again for all that info, also the inspiration.

I honestly could not see the problem earlier.
So i decided to run a test and compare all the variables because there seemed to be no correlation , however there is.

Remember the [color="#0000FF"]first number the chunk Offset is where the chunk is relative to the center chunk so can be negative or positive.
Then the [color="#0000FF"]second number is the position in the array in that chunk so has to be from 0 to 15.
Below why I am getting the wrong answers becomes very apparent.
*Scroll down to see it

Its shown with The Relative Chunk , pos in the array with the new and old methods numbers.

Now a huge decision,
Rewrite the entire engine... again to make everything reletive to chunk 0,0 removeing negatives.
or Find a way to get the correct results here, without adding more computing time.

The only Perfect solution I see is,
**EDIT: This routine is not always Correct!!! -16, -32 are wrong now
After performing the routine:

if (x<0)
{
Chunk-=1;
Tile+=16;
if (y<0)
{
Chunk-=1;
Tile+=16;
if (z<0)
{
Chunk-=1;
Tile+=16;

however this would slow it down and I don't want to turn to this.

Analysis Results:


world0->setPos Analysis:
----------------------------------
number Old New
X: -32 SAME
X: -31 -2 , 1 -1 , -15
X: -30 -2 , 2 -1 , -14
X: -29 -2 , 3 -1 , -13
X: -28 -2 , 4 -1 , -12
X: -27 -2 , 5 -1 , -11
X: -26 -2 , 6 -1 , -10
X: -25 -2 , 7 -1 , -9
X: -24 -2 , 8 -1 , -8
X: -23 -2 , 9 -1 , -7
X: -22 -2 , 10 -1 , -6
X: -21 -2 , 11 -1 , -5
X: -20 -2 , 12 -1 , -4
X: -19 -2 , 13 -1 , -3
X: -18 -2 , 14 -1 , -2
X: -17 -2 , 15 -1 , -1
X: -16 SAME
X: -15 -1 , 1 0 , -15
X: -14 -1 , 2 0 , -14
X: -13 -1 , 3 0 , -13
X: -12 -1 , 4 0 , -12
X: -11 -1 , 5 0 , -11
X: -10 -1 , 6 0 , -10
X: -9 -1 , 7 0 , -9
X: -8 -1 , 8 0 , -8
X: -7 -1 , 9 0 , -7
X: -6 -1 , 10 0 , -6
X: -5 -1 , 11 0 , -5
X: -4 -1 , 12 0 , -4
X: -3 -1 , 13 0 , -3
X: -2 -1 , 14 0 , -2
X: -1 -1 , 15 0 , -1
X: 0 SAME
X: 1 SAME
X: 2 SAME
X: 3 SAME
X: 4 SAME
X: 5 SAME
X: 6 SAME
X: 7 SAME
X: 8 SAME
X: 9 SAME
X: 10 SAME
X: 11 SAME
X: 12 SAME
X: 13 SAME
X: 14 SAME
X: 15 SAME
X: 16 SAME
X: 17 SAME
X: 18 SAME
X: 19 SAME
X: 20 SAME
X: 21 SAME
X: 22 SAME
X: 23 SAME
X: 24 SAME
X: 25 SAME
X: 26 SAME
X: 27 SAME
X: 28 SAME
X: 29 SAME
X: 30 SAME
X: 31 SAME
X: 32 SAME



Again thanks for all the help and explanations! :cool:
We should build a tutorial using all this, not sure what it would be specifically about though. :lol:

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!