Temple of The Roguelike Forums
Development => Programming => Topic started by: konijn_ on November 29, 2012, 09:45:26 PM
-
I read jice's post and found some more outrage on other forums with regards to this.
Feel free to comment, but no wars please, I just want to see how many people care and what they feel is the best.
-
I use x,y myself, but I don't get why the hell anyone would get heated over this.
-
The standard is surely x,y. With 0,0 being the top left of the screen. Right and down are the '+' directions.
x,y is the standard in math, physics, programming, etc...but generally the y axis is inverted in programming.
What's the controversy? Is there a benefit to flipping the variables? A benefit that outweighs potential confusion?
-
[y]
- is reasonably sensible when indexing a 2D array that's easier to access and write to sequentially along rows... like ttys, and tapes. This is a legacy convention.
Making (0,0) be the top left corner is very sensible when writing left-to-right, top-to-bottom text to a screen.
Plenty of programming fields use - [y] for coordinates - graphics and GUI libraries, for a start.
-
An 80x24 matrix takes more memory than a 24x80 matrix.
Why?
Because a two dimensional array is an array of arrays. each array requires 1 pointer. A 2D array requires 1 for the array of arrays and n for each array in that array. All of the other data is contiguous in memory.
map[y]
map
Obviously, a y justified matrix will take up less memory.
It's also possible that y justified matrices require less amortized time to traverse, reducing the number of calculations that you're pushing onto the processor. To maximize efficiency, it isn't unreasonable to generate dungeons that are easily traversed utilizing scan-lines and/or rect-fills. Knowing that a y-justified matrix takes less memory, it can be helpful to optimize your algorithms accordingly.
Of course- this only significant on old machines. My best first search guess.
-
That depends how you implement the 2D array. A rectangular array can be stored as a one-dimensional array of size m*n, with exactly the same memory footprint (but requiring a multiplication and an addition before dereferencing a single pointer).
And on machines less than 15 years old the minute difference in memory consumption and performance really wouldn't matter in the average roguelike.
-
I use my own map class with an overloaded () operator that takes x,y. Internally, however, the class uses y,x because that's imposed by the memory layout of pseudo-2D arrays. So when somebody writes
'map[x][y]' it looks to me like they don't have idea what the operator [] does. It's not a matter of performance, actually, it's a matter of understanding pointers. And operator evaluation order.
-
I'm using one dimensional array and y*width+x to access it.
-
I'm using one dimensional array and y*width+x to access it.
That combines the "advantages" of both of the discussed approach types. That is, your array access is both slow and unreadable. A modern compiler would probably optimize this, but it won't increase the readability.
-
konijn_: What posts are you referring to?
requerent: this depends on the programming language, I am quite sure that in C++, int[10][10] is just a block of 100 ints.
IIRC I used [x ][y] when starting programming but for some reason I have switched to [y][x ] and now I always use it. The advantage is that the contents are physically arranged in a logical order then.
-
That is, your array access is both slow and unreadable. A modern compiler would probably optimize this, but it won't increase the readability.
I'm not using that directly of course, but in a class:
unsigned char K_Bytemap::Get(int x, int y)
{
if (Is_Outside(x, y)) return 0;
return m_bytemap[y*m_width+x];
}
bool K_Bytemap::Put(int x, int y, unsigned char p)
{
if (Is_Outside(x, y)) return false;
m_bytemap[y*m_width+x]=p;
return true;
}
-
I'm not using that directly of course, but in a class:
Oh. That makes much more sense :). 1-dimensional arrays might actually be better than 2D, because they are not spread across the memory. But readability is more important for me. By the way, do you have map types other than K_Bytemap? One byte is not too much nowadays :).
-
One byte is not too much nowadays :).
It's good enough with ASCII.
-
Internally in C/C++ n dimensional arrays are identical to 1 dimensional arrays. They don't involve pointers, but are a single region of contiguous memory such that an n-dimensional array can always be indexed as a 1 dimensional array. So, n dimensional arrays consume the exact same memory as 1 dimensional arrays. The standard way C indexes arrays is y*width+x which is not slow or unreadable, but is and has been the standard way that multidimensional arrays are accessed at the low level. C has always translated map[ x][y] into map[y*w+x].
Again, there is no performance hit for this, it is the standard way that multidimensional arrays have always been accessed. If you are really crazy about performance, you can still loop over a multidimensional array with a pointer increasing the pointer with ++ for every entry to prevent the multiplication, but you'll never notice a performance increase. Multiplication is a crazy fast operation.
In terms of [ x][y] versus [y][ x], it won't affect performance on modern machines either way, but tty based displays drew the screen from left to right top to bottom making [ x][y] make more sense. I think virtually everyone uses [ x][y], and every open source program I've seen uses [ x][y]. I use [ x][y] too. As Jo said, [ x][y] is the standard in math, physics, and most importantly programming.
-
Internally in C/C++ n dimensional arrays are identical to 1 dimensional arrays. They don't involve pointers, but are a single region of contiguous memory such that an n-dimensional array can always be indexed as a 1 dimensional array. So, n dimensional arrays consume the exact same memory as 1 dimensional arrays. The standard way C indexes arrays is y*width+x which is not slow or unreadable, but is and has been the standard way that multidimensional arrays are accessed at the low level. C has always translated map[ x][y] into map[y*w+x].
Again, there is no performance hit for this, it is the standard way that multidimensional arrays have always been accessed. If you are really crazy about performance, you can still loop over a multidimensional array with a pointer increasing the pointer with ++ for every entry to prevent the multiplication, but you'll never notice a performance increase. Multiplication is a crazy fast operation.
In terms of [ x][y] versus [y][ x], it won't affect performance on modern machines either way, but tty based displays drew the screen from left to right top to bottom making [ x][y] make more sense. I think virtually everyone uses [ x][y], and every open source program I've seen uses [ x][y]. I use [ x][y] too. As Jo said, [ x][y] is the standard in math, physics, and most importantly programming.
My bad.
-
As Jo said, [ x][y] is the standard in math, physics, and most importantly programming.
I agree that (x,y) is a standard when writing coordinates. But you do not usually index arrays in maths and physics. Well, you do, when you are using matrices. But note that matrix indices are usually written as aij where i is the row number (y) and j is the column number (x).
Also, most graphical formats I know (BMP, SDL, OpenGL textures, internal VGA memory...) list the pixels row by row (row 1, row 2, row 3, ...) which corresponds to [y][ x] indexing.
I have looked at some available roguelike sources, and some of them use [y][ x], some use [ x][y] (without any clear majority).
-
Well, curses used y,x coordinates. And in linear algebra matrix elements are usually defined as aij denoting the element in the ith row and jth column. I think it's just a maths thing.
-
I just asked my niece what comes first, 'x' or 'y'. After successfully completing the ABC song (many times) it was clear that 'x' does in fact come before 'y'.
I'd consider that to be pretty much the final word on the subject.
-
I just asked my niece what comes first, 'x' or 'y'. After successfully completing the ABC song (many times) it was clear that 'x' does in fact come before 'y'.
I'd consider that to be pretty much the final word on the subject.
+1
-
I found arrays were too impersonal. I give all my tiles their own names.
Tile tilex1y1;
Tile tilex2y1;
Tile tilex7y3;
Tile amy;
Tile tilex14y30;
Tile true;
Tile false;
Tile tilex18y25;
Tile dontStandHere;
etc
Don't seem to be making much progress though for some reason
-
I found arrays were too impersonal. I give all my tiles their own names.
Tile tilex1y1;
Tile tilex2y1;
Tile tilex7y3;
Tile amy;
Tile tilex14y30;
Tile true;
Tile false;
Tile tilex18y25;
Tile dontStandHere;
etc
Don't seem to be making much progress though for some reason
This is the future of programming. All it needs for this paradigm to work is an good actor for each tile.
-
In terms of [ x][y] versus [y][ x], it won't affect performance on modern machines either way, but tty based displays drew the screen from left to right top to bottom making [ x][y] make more sense. I think virtually everyone uses [ x][y], and every open source program I've seen uses [ x][y]. I use [ x][y] too. As Jo said, [ x][y] is the standard in math, physics, and most importantly programming.
There is an enormous performance difference (can be upto 100X on tight loops) between [x ][y ] and [y ][x ] but most roguelikes aren't performance sensitive enough to notice the difference. The difference is even bigger on more modern hardware because CPU clock rates are so high that memory latency is a big issue. This is something you really need to be aware of when writing very high performance software like high end games, scientific applications and so on.
This is vital knowledge for working on the engines of AAA games for example.
In C multidimensional arrays are laid out with the rightmost array index increasing first so:
char map[X][Y] = ...
// The above is the same as a 1D array laid out as:
{ [X0,Y0], [X0,Y1], ..., [X0,YN], [X1,Y0], [X1,Y1], ..., [X1,YN] ... }
Memory is broken up into little contiguous arrays called cache-lines (normally 64 bytes these days). Only so many cache lines can be in the L1 cache, which is the fastest to access memory apart from registers. Getting a new cache-line into the cache is a lot slower than using something already in the cache. So the fastest way to access memory (all things being equal) is to access memory very close to previously accessed memory. For example:
const int DIM = 256;
char map[DIM][DIM] = {0};
// FAST LOOP
// This is 'column' major, it iterates through the Y dimension first.
for (int x=0; x < DIM; ++x) {
for (int y=0; y < DIM; ++y) {
map[x][y] = // something...
}
}
// SLOW LOOP
// This is 'row' major, it iterates through the X dimension first.
for (int y=0; y < DIM; ++y) {
for (int x=0; x < DIM; ++x) {
map[x][y] = // something...
}
}
Now the fast loop is 'column' major (top-to-bottom, left-to-right) but we have a natural assumption that we iterate in the same way we read, e.g. left-to-right, top-to-bottom. But to make that the fast way to loop you need to order you map as [y ][x ].
This is where the controversy comes from you can't have both [x ][y ] and 'left-to-right, top-to-bottom' iteration order you have to pick one if you want the best performance.
However most roguelikes don't need to care because they don't tax the hardware much at all but if you wanted to do FOV calculations on every tile for some reason you better do it the optimal way or it'll be a hell of a lot slower.