Структуры данных, как пользоваться,с чем едят и какие бывают кроме распространенных деревьев и хеш мапов?

Question

[Catmengi]

Я изучаю C . И сейчас только 2 структуры данных которые я знаю и применял(массив и связанный список(круговой)). Я знаю о существование структур данных по типу деревьев и хеш мапов, но я не знаю где, как, и зачем их применять. Допустим есть условная игра с открытым миром, 3д,состоящим из блоков 128x128x128. Какую структуру данных тут применить? Единственное что мне приходит в голову это условный связанный список у которого есть 4 направления роста (x+,x-,y+,y-) но мне кажется что это костыль. Помогите разобраться со структурами данных. Где их применять и какие применяются в реальных примера, особенно в разработке игр, я знаю что C не лучший выбор для этого но мне очень нравиться его семантика.

Comments

[Модератор]

Не надо ставить как можно больше тэгов. Лучше оставить один, но конкретный, с которым проблема.
См.п.3.1 Регламента. Если нет кода, не надо ставить тэг языка.
Также обратите внимание на п.3.6

Answer 1

[mayton2019]

Для блочной игры типа Minecraft можно применять Octree https://en.wikipedia.org/wiki/Octree

Практически везде в С и других языках применяются хеш-мапы и красно-черные деревья. Они
закрывают 90% всех твоих потребностей. Вот изучи их и используй. Все прочие экзотические
структуры данных - надо обсуждать применительно к каждому случаю. Многие из них
являются просто композицией уже известных. Например LRU-лист это хеш-мапа и связный список.

Comments

[Catmengi]

условный связанный список у которого есть 4 направления роста (x+,x-,y+,y-)

Применимали такая структура данных с разряду "костылей"?

[mayton2019]

Catmengi, я не понимаю какой смысл ты вкладываешь в термин "костыль". И я не понимаю что такое "направления роста".

Покажи код.

[hint000]

Catmengi, кстати, почему 4 направления роста, а не 6 направлений? куда делись z+, z-, если мир 3d?

Какую структуру данных применять - зависит от особенностей мира. Если мир "плотный" (на каждом шагу встречаются разные объекты), то массив может быть уместен. Если мир "разреженный", то список или что-то ещё.
Вы прям сразу со сложных и неоднозначных примеров начинаете обучение. Начните с простенькой классики - сделайте Тетрис, змейку, какой-нибудь платформер, какую-нибудь карточную игру, какую-нибудь игру на доске,.. На этих примерах сможете потренироваться в структурах данных. А тогда уже и с 3d-миром вам будет понятнее.

Начинать со сложного и непонятного - верный демотиватор, разочаруетесь и забросите. Только от простого к сложному, подкрепляя практическими успехами.

Answer 2

[Saboteur]

Допустим есть условная игра с открытым миром, 3д,состоящим из блоков 128x128x128. Какую структуру данных тут применить?

Смотря как реализуешь перемещение.
Тут можно и трехмерный массив использовать и обычный список, и оптимизацию с вариативным размером блока.

Но кроме 3д мира, тебе еще надо персонажа хранить, инвентерь. А может быть несколько персонажей. Вот и думай.