Выбор лучшей структуры данных для двухмерной карты, которая сместит данные

Мне нужна помощь в реализации более быстрого способа выполнить полную смену двумерного массива.

Моя проблема в том, что у меня есть двухмерный массив с данными карты игры. Эта игра похожа на Geometry Dash, но на Game Boy Advance. Пока у меня есть карта, которая выглядит примерно так:

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 },
};

Но чтобы прочитать эту карту, я должен пройтись по каждому элементу и посмотреть, должен ли он отображаться на экране (x ›= 0 && x‹ = screen_width).

Поразмыслив, я думаю, мне следует использовать двусвязный список. Таким образом, я мог бы сдвинуть список, переместив узел заголовка в трейлер, а затем просто нарисовать данные первых 15 узлов (или около того). Будет ли это улучшением производительности по сравнению с циклическим перебором каждого элемента в 2D-массиве? Хотя сквозное прохождение не обязательно является недостатком производительности игры, я все же хочу его оптимизировать.

Если да, то как мне реализовать этот двусвязный список, чтобы он содержал те же данные, что и 2d-массив?


c algorithm data-structures gba
person Community    schedule 15.08.2020    source источник
comment
Если все ячейки представлены одного и того же размера (количество пикселей на ячейку = константа), я не понимаю, почему вам будет лучше со списком, чем с массивом. Представьте себе прямоугольник над двумерным массивом, который отображает область карты, которую нужно визуализировать. Затем все, что вам нужно, это top,left,right,bottom индексы этого прямоугольника. И затем вы можете перебрать эти ячейки в массиве карты.   -  person BitTickler    schedule 16.08.2020
comment
Кажется, я неправильно понимаю ваш подход. Я понимаю, что вы собираетесь прочитать весь массив и с условием решить, выходить из строя или нет. Не было бы намного проще просто настроить петли так, чтобы они покрывали только ту часть, которая соответствует условию?   -  person Yunnosch    schedule 16.08.2020
comment
Ого, я даже не подумал об этом. Спасибо!   -  person    schedule 16.08.2020

Ответы (1)


arrow_upward
0
arrow_downward

Первое использование двусвязного списка ухудшит производительность. Ваш текущий подход - самый быстрый, который сейчас приходит мне в голову. Сначала вам нужно понять, как работают массивы и как связанные списки. Что касается массивов, я настоятельно рекомендую вам посмотреть это 5-минутное видео, потому что объясняющее это в тексте займет слишком много времени. После того, как вы поймете, как работают массивы, вам нужно будет сравнить его со связанным списком. При доступе к элементу в массиве все, что делает компьютер, просто увеличивает адрес памяти на размер индекса, умноженный на размер типа массива, а затем ссылается на этот адрес. При доступе или, лучше сказать, просмотре связанного списка, вы сделаете гораздо больше. Сначала вы удалите ссылку на элемент, затем обработаете данные, затем посмотрите, является ли следующий элемент NULL, затем вы перейдете к следующему элементу, сделаете ссылку на него и так далее.

Короче говоря, простое правило: используйте связанные списки, только если вы не знаете длину массива.

Теперь к твоему вопросу. Если вы хотите реализовать такой двухмерный связанный список, ваша структура будет выглядеть так:

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

prev и next будут просто указателями на предыдущий и следующий элемент. Где в качестве данных будут фактические данные.

Вот рисунок, который, надеюсь, объяснит, что я имею в виду: введите описание изображения здесь

Так что в целом ваш метод анализа лучше, чем связанный список. Однако я думаю, что самый быстрый синтаксический анализ - это анализ на лету.

person Emil Engler    schedule 15.08.2020
comment
Спасибо за этот ответ. Видео было действительно полезно! - person ; 16.08.2020
comment
@TheBean Не благодари меня, спасибо создателю видео :-) - person Emil Engler; 16.08.2020