Hi AIDev,

That's what I thought, and it made sense for 2 dimensional [x][y], the same as I would read a map, which is it's purpose.

It just seemed to be a lot of various opinions.

The performance difference is non existant. If you know the dimensions of your 2d array beforehand, use a 2d array.

Tile myArray[100][100];

If you are dynamically allocating your 2d array, because the dimensions may change , the 1d array allocation is the only way you are going to dynamically allocate what amounts to a 2d array(and keep a contiguous memory profile for your tile map).

Tile myArray[100 * 100];
or
Tile *myArray = new Tile[100 * 100];

With this method however the way you index it will be different than indexing a 2d array. I recommend hiding these details in a TileMap class or something similar.

That's really all there is to it. No performance difference. They both allocate the same amount of memory. How you index each will be different. If you have the foresight to expect to need dynamically sized tile maps I'd go with the 1d array method, otherwise just use the static sized 2d array.

Quote:Original post by DrEvil

Quote:Original post by crshinjin
If you want to sweep through the whole array many times probably type array[100*100] is better, but if you wish to make a lot of random access to you array the other one is more convenient.
shinjin

How do you figure?

i think he assumes

for (int i=0;i<10000;i++) {   doSomething(myArray);}

would be slightly faster than

for (int i=0;i<100;i++) {
for(int j=0;j<100;j++) {
doSomething(myArray[j]);
}


and that:

doSomething(myArray[x][y]);

is slightly faster than

myArray[y*100 + x];

You've gotten some good advice on your original question, but I've not yet seen this important aside said:

When you are using arrays, either multi-dimensional or 1-dimensional using math to access the desired elements, you want to access it in the most efficient way possible --

For something like a Tile-based map of say 256 wide by 192 tall, and assuming that you process/draw the map in a top-to-bottom, left-to-right manner (eg - how english is read) you want to define your array like this:

myArray[192][256]

rather than:

myArray[256][192]

Notice that the width of the array should come last. The reason is because the right-most dimension is the one which lies linearly in memory, accessing the next tile to the right will be the very next position in memory. This optimizes your memory access patterns by making perfect use of the CPU cache. In the "wrong" example, the next tile to the right is located 192 memory positions away! This is the exact *wrong* way to use the cache efficiently, and will result in your code having to hit main memory on nearly every access, which is probably 100 times slower than having your data good and ready in level 1 cache.


You can extend this for more dimensions if you want:
myArray[width]
myArray[height][width]
myArray[depth][height][width]
myArray[etc.][depth][height][width]

It helps to think of multi-dimensional arrays not as a grid, cube, etc. but rather as an array of arrays, or an array of arrays of arrays.


When I was a young programmer, and cache's were very small, I remember having this epiphany and literally multiplying the frame-rate of my tile-based engine by 10 times - I was probably 14 years old at the time. This is one of those things that *everyone* does wrong at first, but never does again once they learn better.

Hi ravyne2001,

Good point to mention that !!

For those that did not read all this thread, or the thread about my original project, where the question stemed from

Here's the thread:
Original Post

Basically I am using a char map :

const int tilesPerRow = 10; //no of hexaons per row (Y)
const int tilesPerCol = 10; //no of hexaons per col (X)

char map[tilesPerRow ][tilesPerCol ] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 2, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 3, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 3, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 0, 4, 4, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};

Note: WILL (at some point) be using the char map, the numbers will denote the releavent texture for the tile later.

So I will loop through the number of rows then cols

Obviously going Row by row, hence the Y loop on the outside,
then for every tile in the grid Thats (X)....
draw a tile.... simple....


for Y 0 to tilesPerRow blah blah
{
for X 0 to tilesPerCol blah blah
{
drawHexTile(size, X, Y);
}
}

Note: dont be confused by X,Y - these are 2D coords, as if you were reading a map.
This will translate to world X,Z (there is no Y elevation) - producing a flat grid on the X,Z planes.


basically drawHexTile() is drawing a hexagon from a triangle_fan.
If you read the original thread, it works great, I have an awsome hexagonal grid, pixel perfect.
But I have a few suggestions on how to declare arrays,
either
[size*size]
OR
[size][size]

I neede to know the best way to improve things.

Really the flaw in the tiling is, that A) I'm going through the whole loop and drawing hexagon, every single frame.
B) that with this method, where each tile touches the next (in fact every 3 hexagons touch each other)
Is that I am drawing each vertex 3 times, which is kind of redundant.

I need to create a Vertex Array (which is where I lack knowledge)
So I can generate ALL the vertexes before render.

The map/grid is static, and wont change. all be it, you may only see part of the map as you scroll/move etc..
The grid in theory only ever need calculating once, and hopefully avoid drawing every vertex 3 times also.

So really back to the post, I need the best or most efficient way to declare a 2D 'static' array for a grid, prior to rendering.

If you have other ideas, on my actual Vertex Array or hexagon issue, please read that thread and post in there.

As thats where it gets complex for me really.
If you are folowing this (fingers crossed)
There is a 2D grid array (10 x 10) tiles. thats (100 * x, y, z coords)
(obviously world position to place the tile)
This will vary per 'game level'.. next level 15x15, 20x20.. or what ever is desired.

So I need to store a basic tile array info (for each of the above)
then the Tile data (the triangle fan actually 8 * x,y,z points) for every hexagon
(obviously world coords for each point of the hexagon tile)

So thats 100 * tile position coords
and 8 * hexagon vertex coords

Confused yet ?? Just read the original thread, and check out the screen shots, if I still have your interest.

Here's the thread:
Original Post

Thanks Guys

[Edited by - darren_mfuk on March 1, 2007 3:42:39 PM]

Please check out the original post for those with some ideas, if you could help.

Otherwise I'll just end up jumping between 2 threads on this one.

Cheers, I just wanted an answer on the best way to declare arrays, which I think you guys have helped with.

But if you want to learn more on my vertex array issue, please check the link above

Quote:Of course there isn't any performance benefit at all. If it would give better performance then the compiler would transform it itself. Of course the reverse may be true, that if it knows it's dealing with a multidimensional array then it may utilize optimizations specific to those. I don't really know of any however, so I doubt it will be noticeable at all.

Im just being picky here, however, there is actually a difference to how they are alocated and hence if your not careful performance.
int array[100][100];
Will allocate a column major 2d array so....

for (int i = 0; i < 100; ++i){    for (int j = 0; j < 100; ++j)    {        array[j] = i + j;    }}

will traverse the memory storing the array inorder (good for the cache), however
int array[100 * 100];
will (treated as a 2d array using the most common indexing method) alocate a row major 2d array so....

for (int i = 0; i < 100; ++i){    for (int j = 0; j < 100; ++j)    {        // of course using i * 100 + j here will treat the array as column major        // avoiding this problem (or just swap the order of the loop)        array[j * 100 + i] = i + j;    }}

will trash the cache by acessing the 1st then 101st then 201'st... location in memory.

Of course row major or column major doesnt really mater as long as you traverse the array in the right order (however, in my experience most ppl for some reason or another tend to traverse the flat array in the wrong order)

Edit: mismatched tags and just thought i should mention the standard garuentess that the 2d array is column major so the compiler cant swap it around if you use it in a way where row major would be more performant.

Hi Julian90,

Thanks for your input, it seems to be the common answer really.

2D arrays seem the way to go, and much more logical, and eaier to access the correct data.

So do all these principles still apply for 3D arrays (multi-dimensional) ??