Poll

Which do you use / prefer ?

map
  • [y]
4 (44.4%)
map[y]
2 (22.2%)
Other
1 (11.1%)
Could not care less
2 (22.2%)

Total Members Voted: 8

Voting closed: December 06, 2012, 09:45:26 PM

Author Topic: map[x][y] or map[y][x]  (Read 11578 times)

konijn_

  • Newcomer
  • Posts: 29
  • Karma: +0/-0
    • View Profile
    • Email
map[x][y] or map[y][x]
« 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.

Darren Grey

  • Rogueliker
  • ***
  • Posts: 2027
  • Karma: +0/-0
  • It is pitch black. You are likely to eat someone.
    • View Profile
    • Games of Grey
Re: map[x][y] or map[y][x]
« Reply #1 on: November 30, 2012, 12:10:22 AM »
I use x,y myself, but I don't get why the hell anyone would get heated over this.

guest509

  • Guest
Re: map[x][y] or map[y][x]
« Reply #2 on: November 30, 2012, 12:41:20 AM »
  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?

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: map[x][y] or map[y][x]
« Reply #3 on: November 30, 2012, 01:26:07 AM »
[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.

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: map[x][y] or map[y][x]
« Reply #4 on: November 30, 2012, 01:49:28 AM »
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]
  • = y+1 pointers.

map
  • [y] = x+1 pointers.


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.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: map[x][y] or map[y][x]
« Reply #5 on: November 30, 2012, 04:44:38 AM »
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.

TheCreator

  • Rogueliker
  • ***
  • Posts: 370
  • Karma: +0/-0
    • View Profile
    • Fame
    • Email
Re: map[x][y] or map[y][x]
« Reply #6 on: November 30, 2012, 06:27:56 AM »
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
Code: [Select]
'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.
« Last Edit: November 30, 2012, 06:35:09 AM by UglyTroll »
Fame (Untitled) - my game. Everything is a roguelike.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: map[x][y] or map[y][x]
« Reply #7 on: November 30, 2012, 06:53:57 AM »
I'm  using one dimensional array and y*width+x to access it.

TheCreator

  • Rogueliker
  • ***
  • Posts: 370
  • Karma: +0/-0
    • View Profile
    • Fame
    • Email
Re: map[x][y] or map[y][x]
« Reply #8 on: November 30, 2012, 07:08:20 AM »
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.
Fame (Untitled) - my game. Everything is a roguelike.

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: map[x][y] or map[y][x]
« Reply #9 on: November 30, 2012, 07:41:42 AM »
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.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: map[x][y] or map[y][x]
« Reply #10 on: November 30, 2012, 08:56:10 AM »
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:

Code: [Select]
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;
}

TheCreator

  • Rogueliker
  • ***
  • Posts: 370
  • Karma: +0/-0
    • View Profile
    • Fame
    • Email
Re: map[x][y] or map[y][x]
« Reply #11 on: November 30, 2012, 09:11:57 AM »
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 :).
Fame (Untitled) - my game. Everything is a roguelike.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: map[x][y] or map[y][x]
« Reply #12 on: November 30, 2012, 11:12:28 AM »
One byte is not too much nowadays :).

It's good enough with ASCII.

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: map[x][y] or map[y][x]
« Reply #13 on: November 30, 2012, 02:32:36 PM »
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.
« Last Edit: November 30, 2012, 02:38:36 PM by Elig »

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: map[x][y] or map[y][x]
« Reply #14 on: November 30, 2012, 04:02:06 PM »
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.