CODEWITHSUNDEEP
calgorithmdata-structuresgame-boy-advance
user8222775
user8222775

Reputation:

Selecting best data structure for a 2-dimensional map that will shift the data

I need some help in the ways of implementing a faster way to do a full shift on a two-dimensional array.

My problem is I have a 2 dimensional array that has a game's map data. This game is kind of like Geometry Dash, but on the Game Boy Advance. So far, I have a map that looks something like this:

int map1[9][40] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0 },
    {0, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0 },
    {0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
};

But to read this map, I have to loop through every single element and see if it should be drawn onto the screen (x >= 0 && x <= screen_width).

Giving it some thought, I think I should use a doubly-linked list. This way, I could shift the list by moving the header node to the trailer and then just draw the first 15 nodes' (or so) data. Would this be a performance improvement over looping through every element in the 2D-array? While the looping-through isn't necessarily a game-crushing performance drawback, I do want to optimize it.

If so, how would I go about implementing this doubly-linked list to contain the same data as the 2d-array?

Upvotes: 1

Views: 530

Answers (1)

Emil Engler
Emil Engler

Reputation: 565

First using a doubly-linked list will make the performance worser. Your current approach is the fastest that comes to my mind right now. First you'll need to understand how arrays and how linked lists work under the hood. For arrays I would highly suggest you to watch this 5 minute video because explaining this in text would take too long. After you understood how arrays work you'll need to compare it with a linked list. When accessing an element in the array, all what the computer does it just to increment a memory address by the index times the size of the array type and then de reference that address. When accessing or better say looping through a linked list, you'll do much more. First you will de reference the item, then you process the data, then you look if the next item is NULL, then you jump to the next item, de reference that one and so on.

To put it short, the thumb rule is: Only use linked lists if you don't know the length of the array.

Now to your question. If you want to implement such a 2D linked list your struct will look like this:

struct LinkedList {
    struct LinkedList* data;
    struct LinkedList* prev;
    struct LinkedList* next;

prev and next will just be pointers to the previous and next item. Where as data will be the actual data.

Here is a graphic that will hopefully explain what I mean: enter image description here

So all in all your parsing method is better than a linked list. However I think the fastest parsing would be parsing on the fly.

Upvotes: 1

Related Questions