It is currently Mon Sep 16, 2019 2:01 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 4 posts ] 
Author Message
PostPosted: Tue Sep 10, 2019 1:15 am 
Offline
User avatar

Joined: Sat Aug 31, 2019 2:12 pm
Posts: 7
Hello again!

Let say I want to represent a 32x32 tiled map for a game with destructible tiles (read-write access).

1) Is the best way a one-dimensional char array of size 1024 or should I declare as a 2D matrix?

Code:
// 1D Array:
// + Faster access with i = ((y * len_x) + x)
// - 16bit index
char map[1024] = {...};

// 2D Matrix:
// + 8 bit indexes
// - Slower access (pointer-to-pointer?)
char map[32][32] = {
    {...},
    {...},
       .
       .
       .
};


2) Given the best possible solution, what's the leanest and fastest way to access (read) it?
I'm looking for either C or inline assembly code.

So far, the [32][32] solution seem to be the faster one, with pre-calculated indexes:
Code:
x = ...; y = ...;
v = map[y][x];


How can I improve this? :)

Many thanks in advance.


Top
 Profile  
 
PostPosted: Tue Sep 10, 2019 1:37 am 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1904
I would only use one-dimensional arrays for NES programming. This makes it clearer what's going on below.

The advantage that a two-dimensional array only has single-byte indices is not really an advantage. Because for the compiler, it's all just one long stripe of data. (No, a two-dimensional array is not a pointer to pointer.)
So, the access: array[y][x] still amounts to &(array[0]) + (y * width + x). Which means the compiler does an int-based calculation anyway.

Performance-wise, both should end up identical. (I'm not sure, though. You should test it out.)
But as I said, with a one-dimensional array, you see more directly what's going on.

For example, the index calculation y * width + x is only fast because your width is a potency of 2. That's why the compiler can convert this into a bit shift: (y * 32) == (y << 5)

If your array was 30 x 30, then the compiler really had to start doing multiplication which is slow. And in this case, a one-dimensional array potentially lets you find the slowness faster. Because accessing with array[y][x] might not clue you why the code is so slow. But in array[y * 30 + x] you see: "Oh, right, I'm using a multiplication."


But yeah, for such a big playfield, you have no choice but to use an array with an int-based index.
That's why the granularity of a single screen in my current game is only 16 x 15 items, i.e. the smallest background object, including destroyable objects, can only be 16 x 16 pixels, not 8 x 8 pixels. This way, I have an array of 240 entires for the background status and can easily use a byte index.


By the way, the playfield on the NES for a non-scrolling screen is only 32 x 30, not 32 x 32.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Fri Sep 13, 2019 11:32 pm 
Offline

Joined: Fri Sep 13, 2019 11:22 pm
Posts: 9
wonder wrote:
Hello again!

Let say I want to represent a 32x32 tiled map for a game with destructible tiles (read-write access).

1) Is the best way a one-dimensional char array of size 1024 or should I declare as a 2D matrix?

Code:
// 1D Array:
// + Faster access with i = ((y * len_x) + x)
// - 16bit index
char map[1024] = {...};

// 2D Matrix:
// + 8 bit indexes
// - Slower access (pointer-to-pointer?)
char map[32][32] = {
    {...},
    {...},
       .
       .
       .
};


2) Given the best possible solution, what's the leanest and fastest way to access (read) it?
I'm looking for either C or inline assembly code.

So far, the [32][32] solution seem to be the faster one, with pre-calculated indexes:
Code:
x = ...; y = ...;
v = map[y][x];


How can I improve this? :)

Many thanks in advance.



u8 UrArray[MAX_ARRAY_SIZE] = {
#include "ur_dat_file_whatever_its_type"
};

just so simple


Top
 Profile  
 
PostPosted: Fri Sep 13, 2019 11:48 pm 
Offline

Joined: Fri Sep 13, 2019 11:22 pm
Posts: 9
i'd rather use linear 1-D array, 'cause its more effective, and no need aligned storage in even addr.

nes is too less in-built ram to use, cant be wasted


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group