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

map example

  • 1
    \$\begingroup\$ You mention entities and gameObjects. What is the relationship between the two? I ask because they are typically synonymous, and it might be confusing. \$\endgroup\$
    – Eric
    Apr 23, 2012 at 14:37
  • \$\begingroup\$ @eric a game object is the generic thing that exists in the world (common definition) that has position, orientation, and dimensions, or the information to generate a physics collision if needed, and will serve as the ABB of all thing in the game world. while a entity extends/inherits from gameObject, and is allowed to more, and have collisions resolved on them (be moved as a result of the collision). I can understand that they are similar, but I am talking about 2 different things myself \$\endgroup\$
    – gardian06
    Apr 23, 2012 at 16:01
  • \$\begingroup\$ Why is removing items from a list a 'chore' and why does it leave a 'memory black-hole'? \$\endgroup\$
    – Samaursa
    Apr 29, 2012 at 15:49
  • \$\begingroup\$ @samaursa I made the statement of not done right, and I have never really gotten the hang of removing from a singlyLinkedList (doubly is ok), but I have since changed implementations to use boost::ptr_vectors though I have little experience making things like graphs, or adjacency lists which I think I need for holding the level itself \$\endgroup\$
    – gardian06
    Apr 29, 2012 at 16:47

1 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.


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.

  • \$\begingroup\$ Re: "I keep bouncing back, and forth" and @Coyote's last paragraph: gamedev.stackexchange.com/questions/tagged/component-based Game-objects could have a physics component and/or/nor a graphics component. All physics components would be referenced by the physics engine and used for collision detection, whereas all graphics components are referenced by the graphics engine and used for visibility testing and rendering. \$\endgroup\$
    – Eric
    Apr 23, 2012 at 14:44
  • \$\begingroup\$ I like the ideas here though on your component based system is this an approach I am uncertain what you are specifically talking about. I wanted to have each room almost be responsible for itself in terms of graphics, and then have graphics engine be oblivious to what room was is to be given. One of our design goals is dynamic procedural generation so the rules for each room have to be concrete. The reasons for pointers was that unique objects like the player for example could move between rooms \$\endgroup\$
    – gardian06
    Apr 23, 2012 at 16:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .