game data structures

Question

I am working on a game that will be a 3D-shooter (camera trailing player), and want to impose some architecture on the game being that a level is composed of rooms where each room can hold entities(the player, enemies, pickups, projectiles), AInodes, walls/floor, and doors(more on these in a little)

my first concern/iteration is to get a single room functional, and then link rooms together in a later iteration(this is so that rooms to render are dynamically chosen to accelerate render times on larger level). my direct question for this iteration is what would be an optimal data structure for holding my entities for the room? keeping in mind that whatever structure I use needs to be searchable, removable(single/group of items), sortable(this can be given up if needed), growable, and possibly be able to take pointers to the gameObjects. this structure would probably also be used for my doors. my initial thought was to use linked list though removing items from linked lists can be a chore, and if not done right can just create a memory black-hole.

I keep bouncing back, and forth on putting walls/floor into the same structure as the entities as it would be mostly efficient for collision detection (i think), but I know it can cause a graphics nightmare (more things being rendered means longer it takes), so maybe keeping walls separate, and create a separate list of walls to be rendered vs collisions.

the next part would be linking the rooms together by doors(see picture bellow where the joint between each room is a door) where my first though was adjacency list. I understand that the std::graph has an adjacency list that it uses though I don't feel that it would work in my situation as just rooms 05, and 11/15 don't work within a std::graph so would it be worth while to build a custom adjacency list (might need to see an implementation as I keep getting lost on connecting adjacent things that should be connected)

• S: start
• F: finish

• : room number

map example

Answer 1

Usually I separate the rendering from the game structure. I have mechanisms where game entities can attach graphics to the graphic engines. This way the graphics can be optimized independently.

Relationships

Then when it comes to relationships between entities, there are many ways to implement them. You can have a general purpose relationship mechanism with an ends list, a communications system dedicated to related entities, or very specific hardcoded relationships.

How you implement your relationships will depend on the architecture of your engine. But you need to establish the relationship between the rooms and if using the doors is simpler you can for each room add a list of doors/gates...

Each gate can hold 2 pointers to the rooms they link to. When it comes to pointers and lists it's up to you to organize the construction and destruction of your objects. It's not a big problem if you think about and implement the destruction while you write the construction process.

Rooms composition

You don't have to put each floor tile as a different entity. You can load your level as one entity with graphics managed separately by the graphics engine. Your levels can create additional entities like traps, mechanisms, gates, objects with collision, etc... This way you don't have to bloat your main engine with floors tiles and other passive elements. You can have only one physics component per room for example (composed of floors and walls).

Composition is the solution

Your current system seems to store everything in the entities. A component based system can bring more work when you start but you will benefit from the composition as you progress. Additionally a component based system will allow you to implement quickly and simply the relational structure you want to have.