next »

[jotapeh]

I wanted to ask this question since it seems like something that has been tackled in many, many games in the past. Given any number of 'rooms' per se (made up pseudocode here:)

Code:

class Room {
   int roomId;
   string roomName;
   array roomContents;
   // etc etc..

   SomeStruct roomConnections;
}

A 'zone' or whatever you wish to call it is composed of several interconnected rooms. Now when a player walks off an edge, or out of an exit, obviously we want them to go to another room (if it is connected!)

So the sticky bit I've been noodling around in my head is how to implement these interconnections. Immediately I thought of a sort of linked list structure, with each room containing pointers to other rooms. Serializing this data in and out isn't a huge deal, obviously I can store the IDs to other rooms within the data structure for each room, etc..

The real issue is that it requires the zone class to set up and manage all the connections between rooms for each room. In addition, should the name or ID of a room change (eg., in an editor mode,) the zone class has to potentially reshuffle every room and make certain connections on either side are still valid and updated correctly.

Because of that last bit, I feel like maybe I'm tackling this the wrong way - there might be a design pattern that exists that is more elegant than what I'm doing right now.. certainly it would work, but it doesn't feel robust or clean.

Penny for your thoughts? 

[Sos]

Haha! That is what C++ is actually NOT good for.

Code:

struct ROOM {
   int roomId;
   string roomName;
   array roomContents;
   // etc etc..

   Room* roomConnections[MAX_CONNECTIONS];
}

So, you load the rooms but keep them as pointers

ROOM * rooms[MAX_ROOMS];

And have one pointer that points to current room

ROOM *current_room;

current_room = room[STARTING_ROOM];

Now if you want to exit the room, just do

current_room=current_room->roomConnections[chosen_exit];

That's all there is to it.

[salade]

Using ID's is actually a good idea, but they have to be unique, and can't change. IDvalues are should handled behind the scenes, the user should only be able to change the name associated with the ID. The ID should also help you specify your room, i.e. an id could be the room's position in some datastructure.

The benefit to a system like this is that you can save your whole map in terms of there id value, so when you load them you already have a way to quickly get pointers and such for each element.

[Will Vale]

+1 to both answers. The first for setting it up right, and the second for making it relocatable (so your on-disc and in-memory formats are the same). If you ID your rooms using an index counting from zero (or maybe from 1 so you can use zero as "no room") you can use pretty much the same code as Sos's example. The only wrinkle is that you need need access to the global room list to do the lookup:

Code:

current_room = &map->rooms[current_room->roomConnections[chosen_exit]];

or you could wrap it up as

Code:

current_room = map->get_room( current_room->roomConnections[chosen_exit] );

which is a bit tidier.

You can handle the reshuffles in the editor by just adding rooms, not removing them, so the old room stays in the array (marked as dead somehow) and no IDs need to change. Then when you come to save your changes, you throw out the dead rooms and fix up the IDs just once as you run over the rooms array. Easy, since the room connections are right there in the rooms.

Footnote: If anyone suggests something like

Code:

std::vector<boost::shared_ptr<Room> > roomConnections;

then I shall cry real tears

[salade]

You can handle the reshuffles in the editor by just adding rooms, not removing them, so the old room stays in the array (marked as dead somehow) and no IDs need to change. Then when you come to save your changes, you throw out the dead rooms and fix up the IDs just once as you run over the rooms array. Easy, since the room connections are right there in the rooms.

Just thought I would share an approach to this. IDs for deleted rooms get pushed onto a stack, and if a new room is created when that stack isn't empty it assumes an ID from the stack, rather than having to create a new one.

Hope that was useful/interesting!

Oh, and boost's shared pointers would be really good for this type of thing 

[Crimsontide]

I'd use a map, something like:

Code:

struct ROOM {
   int id;
   string roomName;
   // ect....
   std::vector<int> adjacentRooms;
   };

std::map<int,ROOM> roomMap;

Course if the room's aren't lightweight, u might wanna store pointers instead of the actual rooms...

[shrimp]

Course if the room's aren't lightweight, u might wanna store pointers instead of the actual rooms...

You have to use pointers instead of actual rooms or else you'll just have lots of copies of the rooms!(?)

Haha! That is what C++ is actually NOT good for.

Come on man, what? Seriously, what?

[skyy]

Allocate rooms once and pointers would be my suggestion to handle this. No reason to allocate them more than once and no reason to steer away from lovely pointers :3

[st33d]

It seems like what you really want is like a more complicated version of a pointer.

So go with that. Create an object that points to a room. Then your room pointer can be activated and deactivated without any shuffling - but it will remember its connection and can even change it depending on circumstances. And you will also be able to do other things like locking that pointer.

The pointer, is a door. A door is a lot more complicated than simply a pointer to another room, so let it be that. You would then have a linked list of doors.

[Sos]

Haha! That is what C++ is actually NOT good for.

Come on man, what? Seriously, what?

Citation needed? Try this:

http://ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip


Seriously, this 1999 game (pentium 3 was introduced this year) works smoothly (~100fps) on Any Pentium MMX 233Mhz with a voodoo card.

You either want to access a pointer, which will compile into several lines of assembly code, or some STL crap which will take several library calls and make your room-issue slow down the entire thing.

You do not need IDs for the room, unless you want to recognise them explicitly (e.g. room 32 is 'home'). Pointers, not smart shared of what the hell ever pointers, just plain ol' C pointers ARE unique and sufficient for this task. Period.

[Crimsontide]

Course if the room's aren't lightweight, u might wanna store pointers instead of the actual rooms...

You have to use pointers instead of actual rooms or else you'll just have lots of copies of the rooms!(?)

Haha! That is what C++ is actually NOT good for.

Come on man, what? Seriously, what?

Not true.

Code:

struct ROOM {
   int id;
   string roomName;
   // ect....
   std::vector<int> adjacentRooms;
   ROOM& GetAdjacentRoom ( /* stuff here about room selected, perhaps edge that the room was exited at... */ );
   };

std::map<int,ROOM> roomMap;

ROOM& ROOM::GetAdjacentRoom ( /* stuff here */ ) {
   int id = /* calculate id from stuff */;
   return roomMap[id];
   }

Either way whether u explicitly use new/delete or use a map, they're going on the heap.  But why would I not want to use pointers?  Well simply because:

std::map<int,ROOM> roomMap;

is easier to work with than:

std::map<int,boost::someSmartPointer<ROOM> > roomMap;

Like I said, I'd only do that if the ROOMs were lightweight and there were a lot of em.

[jotapeh]

Guys, I mentioned the phrase 'made up pseudocode' in the OP because I was asking for a language agnostic design pattern. Perhaps I should have been more clear... but can we please stop with the C vs C++? I am actually working in AS3, but I posed the question in a C++-ish format because the language should not matter for the general design pattern.

Anyway, I appreciate the insight so far. It's not terribly different from what I'm currently doing, I feel like I'm not too far off. I think I will stick to assigning rooms unique IDs because although pointers are unique they are not meaningful when serialized into a level file.

I do like the idea of keeping a stack of deleted room IDs. On the other hand I might be able to keep the list sorted by ID, and simply iterate through to find a 'hole' in the IDs. On the other hand it is unlikely that I will exceed UINT_VALUE_MAX of rooms, so that might even just be silly overkill

Well I am going to sketch this out one last time and decide on an implementation, more comments are always welcome. I'll post more detail when I figure out what I am going ahead with and if anyone feels like picking that apart I am always open to criticism.

[Crimsontide]

One thing to consider, is to generate random ids.  That way you don't need to keep a list or sort anything.  Use a hash table for lookups, and when you need a new room, simply create and go.  Even with a 32 bit id, unless there'll be hundreds of thousands, the chances of a collision are pretty much nil.

[Sos]

Guys, I mentioned the phrase 'made up pseudocode' in the OP because I was asking for a language agnostic design pattern. Perhaps I should have been more clear... but can we please stop with the C vs C++? I am actually working in AS3, but I posed the question in a C++-ish format because the language should not matter for the general design pattern.

You're right, we suck.

[shrimp]

The point about C++ (and the pseudocode given, and AS3) is it has classes. As class is is construct for Object oriented programming. This is a problem phrased in and best solved with object oriented programming. STL is irrelevant.

When I said "pointers" I guess I just meant "pointers or references".
If you are working AS3 you don't have pointers anyway.

[jotapeh]

You're right, we suck.

Please don't take offense... I'm not taking a jab at anyone's ability. I just don't see the which language debate being particularly productive or relevant (in this case). As I said, I do appreciate the input regardless of which programming language it is presented in.

The point about C++ (and the pseudocode given, and AS3) is it has classes. As class is is construct for Object oriented programming. This is a problem phrased in and best solved with object oriented programming. STL is irrelevant.

Yes, precisely. Thanks.

When I said "pointers" I guess I just meant "pointers or references".
If you are working AS3 you don't have pointers anyway.

I agree, I use the term "pointer" in the same generic fashion. You are correct in that AS3 does not strictly allow for the declaration of variables as pointers, however all variables are passed by reference (with some exceptions, notably int, string, etc..)

It is also meaningful in AS3 to say (Object1 == Object2) insofar as that if Object1 is Object2, they will have the same memory location and that comparison will return true, at least as far as my tests have gone. Perhaps there is some nuance or underworking I do not fully understand here, but on the surface that appears to be the case.

One thing to consider, is to generate random ids.  That way you don't need to keep a list or sort anything.  Use a hash table for lookups, and when you need a new room, simply create and go.  Even with a 32 bit id, unless there'll be hundreds of thousands, the chances of a collision are pretty much nil.

Certainly something I will keep in mind, though I would definitely include a check against all existing IDs (even if the chances are quite slim, I can't simply trust the RNG to never pick the same number twice.) I do like the slight level of data obfuscation this could create in some cases.

[Crimsontide]

Certainly something I will keep in mind, though I would definitely include a check against all existing IDs (even if the chances are quite slim, I can't simply trust the RNG to never pick the same number twice.) I do like the slight level of data obfuscation this could create in some cases.

Generally its a pretty easy thing to do.  When you construct a room and generate the id, just do a quick lookup, if there's a collision generate another.  Rather than worry about sorted lists and deleted ids your entire id construction/management code ends up looking something like:

Code:

int id = GenerateRandomId();
while (HashLookUp(id) != 0) id = GenerateRandomId();

It keeps it pretty simple.

[jotapeh]

Certainly something I will keep in mind, though I would definitely include a check against all existing IDs (even if the chances are quite slim, I can't simply trust the RNG to never pick the same number twice.) I do like the slight level of data obfuscation this could create in some cases.

Generally its a pretty easy thing to do.  When you construct a room and generate the id, just do a quick lookup, if there's a collision generate another.  Rather than worry about sorted lists and deleted ids your entire id construction/management code ends up looking something like:

Code:

int id = GenerateRandomId();
while (HashLookUp(id) != 0) id = GenerateRandomId();

It keeps it pretty simple.

Of course. Duh. 

Thanks. Not really thinking there for a minute, haha.

[shrimp]

I always go with sequential IDs to aid debugging (i.e. "3" - that'll be the 3rd room instantiated). You can always switch to hashed IDs in future.

For speed and conciseness you might want to consider references in the connection structure, but id's are still useful, and essential for serialisation of course.

[BorisTheBrave]

Calling your integer index into an array the id is nice because it's simple. But sometimes I like to go for the more robust approach of using strings to uniquely identify objects in level files (and using pointers in memory, not a big map). It's much better for debugging, imho, as you can give human readable names, and it frees up the "ordering" of you rooms to mean something else, like sort order, or load order.