TIGSource Forums

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:)


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?  :gentleman:

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


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.

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.

+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:


or you could wrap it up as


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


then I shall cry real tears :)

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  :giggle:

I'd use a map, something like:


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!(?)


Come on man, what? Seriously, what?

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

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.

Citation needed? Try this:

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.

Not true.


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.

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. :gentleman:

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.

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.

You're right, we suck.

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.

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.


Yes, precisely. Thanks. :)


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.


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:


It keeps it pretty simple.

Of course. Duh.  :facepalm:

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

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.

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.

Please don't take my recent attacks of sarcasm too seriously. And you're right, it's me who should apologize. I didn't even contribute anything helpful to this thread. :gentleman:

Couldn't you just have a static ID int variable, increment on room initialisation and use that as the unique ID?

It's simple, fairly elegant, and every ID is different..

Sorry, missed the pseudocode bit!

If your topology isn't arbitrary - e.g. your rooms lie in a 2D grid, and connections are only N/S/E/W, then you have more options. For example storing the rooms in a 2D array and having per-room flags to say which directions are exits. Then getting the next room is defined by the direction and the grid. But I'm guessing this isn't the case from the OP?

If your topology *is* arbitrary, interconnected rooms with arbitrary topology form a graph. The rooms are the nodes, and the connections are edges. There's lots of computer science research about representing graphs, might be worth looking at.

For something I was working on recently, where I was modifying things on the fly, I stored the nodes and edges in two arrays, and the nodes didn't know about the edges. It meant a fair bit of trawling the edge array to find relevant connections, but it wasn't really the performance problem I was expecting it to be. I think for most uses this is overkill though, and the solution where the room contains the connections as per your pseudocode is easier.


If you want to generate unique IDs, I think you'd be much better off doing:


then you know you'll never get a collision until the generator wraps around, and you don't need to mess around detecting collisions. If you have a large generator (32-bit and up) you can pretty much ignore the wrap around. It doesn't matter that they're random or not, isn't the uniqueness the point?

[edit: Radnom just said the same thing in fewer words!]

Will

Nonsense.

Simply fill an array with numbers or IDs and then shuffle it with this:


Then you can iterate through a randomised list. Random numbers. Never the same number twice.

That's the most annoying piece of code I've seen in a while  :-[. Unhelpful comment, poorly named, deliberately uses an obscure way of writing for the sake of a few lines, twice. Impressive.

But also, I don't think that really helps the problem at hand. That would never give the same number twice, up until you ask for too many number's at which point it fails. I don't see what it's gaining you over auto incrementing.

Hey, it was a refreshing break from Java vs. C++!

 :gentleman:

And I didn't even write the original. That was in javascript (hence the one line of unreadable code).

I was addressing the comment about getting unique random numbers. I wasn't decrying the object id method.

I actually have radnom's method of a static incrementing counter already implemented on all my map objects as a debugging tool. It's very useful.