Thread: Linked Lists and Rooms

Hey guys,
I am working on a text game and I want to use a linked list to hold the room info.
I just wrote a little test program to get the fell for this.

Code:

#include <iostream>
#include <string>

enum {North,South,East,West};

struct room
{
    std::string name;
    room *next[4];
};

int main()
{
    char choice;
    room *start;
    room *walker;   
    
    std::cout<<"Welcome to my game"<<std::endl;
    start = new room;
    start->name = "Starting Room";
    
    for(int i = 0; i < 4; i++)
    {
        start->next[i] = NULL;
    }
    
    walker = start;
    walker->next[North] = new room;
    walker->next[North]->name = "North Room";    
    walker->next[South] = new room;
    walker->next[South]->name = "South Room";
    
    walker->next[East] = new room;
    walker->next[East]->name = "East Room";
    
    walker->next[West] = new room;
    walker->next[West]->name = "West Room";
    while(choice != 'q')
    {
        
        std::cout<<"You are in the "<<walker->name<<std::endl;
        std::cout<<"Where do you want to go?"<<std::endl;
        std::cout<<"[N]orth [S]outh [E]ast [W]est [q] for exiting"<<std::endl;
        std::cin>>choice;
        switch(choice)
        {
            case 'n':
                if(walker->next[North] != NULL)
                {                    
                    walker->next[North]->next[South] = walker;
                    walker = walker->next[North];
                    
                }
                else
                {
                    std::cout<<"You can't go there"<<std::endl;
                }
                break;        
            case 's':
                if(walker->next[South] != NULL)
                {                    
                    walker->next[South]->next[North]= walker;
                    walker = walker->next[South];
                }
                else
                {
                    std::cout<<"You can't go there"<<std::endl;
                }
                break;
            case 'e':
                if(walker->next[East] != NULL)
                {
                    walker->next[East]->next[West] = walker;
                    walker = walker->next[East];
                }
                else
                {
                    std::cout<<"You can't go there"<<std::endl;
                }
                break;
            case 'w':
                if(walker->next[West] != NULL)
                {
                    walker->next[West]->next[East] = walker;
                    walker = walker->next[West];
                }
                else
                {
                    std::cout<<"You Can't go there"<<std::endl;
                }
                break;
        }
    
    }
    return 0;
}

I know this works but would this be a proper method for this?
If not who wants to make fun of me and tell me how you would do it. Basically what I want to do is have a series of predefined rooms.

Of course that's a valid way of doing that. If you didn't have a list setup, you could still store all of the rooms, say, in just a giant array in memory. Everytime you would want to access the 'next' room, however, you'd run into problems. You might need to manually search the array to find the next room, or you may need some clever mathematical algorithm for computing the appropriate index into the array, etc. So as you see a linked list is a good way to go with this.

Read the first half of this thread.

Quzah.

Yea I was looking over that, what I wanted was like predefined "rooms" I think the pointer method is going to work the best this ugly example shows what I want.

Code:

#include <iostream>
#include <string>
#include "room.h"

int main()
{
    char direction;
    bool exit = false;
    room *town = new room;
    room *centerForest = new room;
    room *northForest = new room;
    room *southForest = new room;
    room *eastForest = new room;
    room *westForest = new room;
    room *otherTown = new room;
    room *walker;
    walker = town;
    //I know this is ugly but I will change it if this is a good method
    town->name = "Town 1";
    town->next[East] = westForest;
    centerForest->name = "Center Forest";
    centerForest->next[North] = northForest;
    centerForest->next[South] = southForest;
    centerForest->next[East] = eastForest;
    centerForest->next[West] = westForest;
    northForest->name = "North Forest";
    northForest->next[South] = centerForest;
    eastForest->next[West] = centerForest;
    eastForest->next[East] = otherTown;
    eastForest->name = "East Forest";
    westForest->name = "West Forest";
    westForest->next[West] = town;
    westForest->next[East] = centerForest;
    southForest->name = "South Forest";
    southForest->next[North] = centerForest;
    otherTown->name = "Town 2";
    otherTown->next[West] = eastForest;
    std::cout<<"Welcome To My Game"<<std::endl;
    while(!exit)
    {
        std::cout<<"Your are currently in the "<<walker->name<<std::endl;
        std::cout<<"Where do you want to go?"<<std::endl;
        std::cout<<"[n]orth [s]outh [e]ast [w]est [q]uit";
        std::cin>>direction;
        switch(direction)
        {
            case 'n':
                if(walker->next[North] != NULL)
                {                 
                    walker = walker->next[North];                    
                }
                else
                {
                    std::cout<<"You can't go there"<<std::endl;
                }
                break;        
            case 's':
                if(walker->next[South] != NULL)
                {                 
                    walker = walker->next[South];
                }
                else
                {
                    std::cout<<"You can't go there"<<std::endl;
                }
                break;
            case 'e':
                if(walker->next[East] != NULL)
                {
                    walker = walker->next[East];
                }
                else
                {
                    std::cout<<"You can't go there"<<std::endl;
                }
                break;
            case 'w':
                if(walker->next[West] != NULL)
                {
                    walker = walker->next[West];
                }
                else
                {
                    std::cout<<"You Can't go there"<<std::endl;
                }
                break;
            case 'q':
                exit = true;
                break;
        }
            
    }
    
    return 0;   
}

Yeah, that's pretty much what I was talking about there. When you save a room to file, you save the number of the room it connects to in a given direction. If you want flat files, you could just do something like so:

Code:

ROOM
<room number>
<blah blah room info>
E 0 100
E 2 101
E 4 107
ROOMEND

So you'd read your file, and you hit the line that says "ROOM", and you now know you're starting to read in a room. You then read in the number for that room. You read in the rest of the data that's fixed (meaning there is no variation to it, read further for clarity.)
Now you read the variable data. That is to say, a room may have 0 - N exits. So you can make this variable. You read a line, see it starts with E, that means you're readin in some exit data. You then read the number after it. This corresponds to the direction or exit location. Then you read the final number, this is the room number of the room this exit links to.

You read all of this into memory, as a room index. Then you go through the entire index and build actual room instances. (Or, you leave it all dynamic. When someone "enters" a room, you creat an instance of it based on their index. After they walk out, or after it hasn't been used in N time, you destroy the instance.)

You then just use the numbers you've read in to link up your rooms with the rooms you have indexed.

Or you could change it. If you don't like a number, use a name:

Code:

E NORTH 101
E SOUTH 23458
E UP 2300

Or, you use full words:

Code:

EXIT NORTH 100
EXIT WEST 2001

You could of course just save all the exits for each room:

Code:

ROOM
<number>
<stuff>
100
-1
203
-1
-1
700

Then you just go down linear through your exit list. For example, here we have:

Code:

100   <-- This would be north.
-1    <-- East
203   <-- South
-1    <-- West
-1    <-- Up
700   <-- Down

Or whatever you like.

Anyway, this lets you have predetermined rooms to your heart's delight. This is what most DIKU (and many others) muds do. Most things (DIKU) have an index which stores unchanging stuff, and this is the only thing that's saved. The actual room instances themselves don't save. Because if you flat out wrote a room instance, it would (pure binary dump) try to save pointers (memory addresses), which isn't what you want. So you have to have a number scheme or something like I've illustrated so you know how to reassemble your rooms when you start up again.

Quzah.

What exactly do you mean Bubba?

Yes. Please expand. Because I don't see how this limits anything. As I've stated, your method is incredibly slow at best. You say, rather than using a pointer to a room, just store a number to it (in memory). Then, every single time anyone goes from one room to another, search through your entire list for that new room number, and display that room.

That's horribly inefficient. Furthermore, I don't see how using a pointer directly to the room instance itself can possibly be limiting when compared to a numerical lookup. Just think about it:

A pointer to a room is a numeric lookup, with the direct benifit of not actually looking through anything. You want to access the room to the north? Great. Do it:

Code:

if( thisroom->exits[ EXIT_NORTH ] == NULL )
{
    output( "You cannot go that way." );
}
else
{
    output( "You move north." );
    thisroom = thisroom->exits[ EXIT_NORTH ];    /* Bam. We're there. */
}

Now here's your method:

Code:

if( thisroom->exits[ EXIT_NORTH ] == 0xFFFFFFFF )
{
    output( "You cannot go that way." );
}
else
{
    output( "You move north." );
    thisroom = lookup( thisroom->exits[ EXIT_NORTH ] );
}

Sure, they're about the same number of lines of code, by appearance. But what do you have to do? Well, you have to have your function lookup go fetch a pointer to the new room. Now, best case, you've got a massive array some place which contains, at the exact index of the room number itself, a room instance.

That's best case. Why? Because then it's a direct access. However, it's horribly inefficient as far as memory usage goes. Worst case, you've got a for loop and you loop through all of your rooms until you hit room number, and return it.

So there you go. Either you have a horribly inefficient use of memory, or an incredibly slow lookup, or a mixture of both.

In either case, you're eons slower than a direct pointer access. You cannot get any faster than that. It doesn't happen. Furthermore, the only "limitation" is on how much memory you can point to.

If there's some other form of limitation, by all means, point it out. Otherwise, stop talking out of your ass like you were in the mentioned thread. Because even there, you didn't show me any limitation at all. Nor did you show me any benifit of a numeric lookup when compared to a pointer.

If you're refering to this post, then you're doing what I've already mentioned in both thread. You write the room number to disk, which is only obvious, because you don't write pointers to disk. This is, as mentioned again in both threads, loaded into memory as the room index. Then room instances are loaded. Oh wait, I've already said that, on multiple occasions.

I noticed you've failed to address the issue when I mentioned it in the last thread, so I suspect you'll just dodge this post again like you've done before. As they say, put up or shut up.

Quzah.

Aaaaawwwww looks like my way of doing it wwwwwaaaaaaaaaaayyyyyyyyyyyyy off. lol

Whoa. First take a chill pill quzah.

You don't have to look up anything in my method, except maybe to find the objects that are in that room and even that can be optimized quite a bit.

The map is just an array that holds values. The values correspond to room ID numbers. The room ID numbers are really just the index of the room in the master list of rooms. So really the map is just a big array of indexes into the master list.

So if you are at 5,5 and the number there is 10 you would use the number 10 to access the room, exit info, etc. Since the room list is going to be a class of type Room then this information is all contained in the class.

You can do objects by using pointers in the room class. When the user drops an item in a room you simply do Room[ID].AddObject(ObjectToBeDropped());

I don't think I'm too far off here because a lot of editors that I've used, use this same method. A lot of the old AGI games (Kings Quest 1,2,3 etc) used this for rooms and information. They also use this same method for responding to the user about what they typed in - everything is based on ID numbers.

Modern 3D editors like Novalogic's NILE for Joint Ops also uses ID numbers but they call them SSN's. The whole engine revolves around SSNs. I suspect they either keep an STL map of SSN to object relations or it is an array with the SSN being the index into the array. Either way would be pretty simple. And I suspect there is more info than just the SSN inside of the engine.


With the pointer method it's not easy to say transport a person from one room to the next or move to an arbitrary location in the map for say a spawn point for monsters or what have you. Array index methods allow for simple placement of objects, monsters, descriptions etc.

Code:

int column=rand () % mapsizex;
int row=rand() % mapsizey;

DWORD RoomID=TheMap[column][row];

Monster.SetLocation(RoomID);

Here might be a sample setup code for monsters.

Code:

int iMonsters=rand () % somevalue;

Monster *MonsterArrray=new Monster[iMonsters];
bool bMonsterPlaced=false;


for (int i=0;i<iMonsters;i++)
{
  do
  {
    int x=rand() % mapsizex;
    int y=rand() % mapsizey;

    //Get RoomID - index value into master array of rooms
    DWORD RoomID=TheMap[x][y];

    if (!Room[ID].OccupiedByMonster())
    {
       ...Set random monster traits
       Monster[i].SetLocation(RoomID);
       bMonsterPlaced=true;
    }
  } while (bMonsterPlaced==false);

  bMonsterPlaced=false;
}

I don't use iteration to find the room. With this you directly index into the array based on the value in the map.

It's the same concept for a tile engine. You assign IDs to the tiles - preferably the ID is the index into the array of tiles. The map is simply a bunch of ID's or indexes into the array of tiles. So the render system simply iterates through the map based on scroll position, extracts the TileID or index, sets the texture based on the ID, and renders.

Here is a simple sample from my asteroids project. This is just a really simple texture manager class. It uses a vector instead of an array, but could be changed to use an array. The ID of the texture is simply it's position in the vector.

Code:

#ifndef CTEXTUREMANAGER
#define CTEXTUREMANAGER


#include <d3dx9.h>
#include <vector>
#include "CTexture.h"


class CTextureManager
{
  protected:
    
    IDirect3DDevice9 *m_pDevice;
  

  public:
    std::vector<IDirect3DTexture9 * > m_pTextures;
    CTextureManager(void) {}
    virtual ~CTextureManager(void) 
    {
      m_pTextures.clear();
    }

    void Create(IDirect3DDevice9 *Device)
    {
      m_pDevice=Device;
    }

    unsigned int Add(std::string File)
    {
      
      IDirect3DTexture9 *Texture=NULL;

      D3DXCreateTextureFromFile(m_pDevice,File.c_str(),&Texture);
      m_pTextures.push_back(Texture);
      
      return m_pTextures.size()-1;
    }

    IDirect3DTexture9 *GetTexture(unsigned int ID)
    {
      return m_pTextures[ID];
    }

};

#endif

So to set a texture just becomes this:

Code:

Device->SetTexture(TextureSystem->m_pTextures[ClassTextureID]);

I didn't mean to make anyone mad and I'm sorry if I did. I've just found that using ID numbers as indexes into arrays works quite well for a lot of games. The advantage to using an array based approach is the same as the benefits of an array over a linked list.
Essentially using pointers is making one huge linked list of rooms.
Very hard to iterate through quickly.

Sure, you can use an array if you want to never increase the number of items, rooms, etc at run time. Otherwise, STL or not, you're still in effect using a linked list to store your objects and iterate through them. A vector is for all practical purposes, a linked list. Oh, I suppose it could be in effect realloc of all the data, but that's horribly inefficient, and even if it were, you still have to iterate through things using their iterator.

So, the only possible benifit you could gain by using arrays for everything, is offset by the fact that you cannot grow it at runtime.

With the pointer method it's not easy to say transport a person from one room to the next or move to an arbitrary location in the map for say a spawn point for monsters or what have you. Array index methods allow for simple placement of objects, monsters, descriptions etc.

How on earth is this not easy?

Code:

ROOM* playerfromroom( PLAYER *p )
{
    if( p && p->in_room )
    {
        ROOM *r = p->in_room;

        if( r->players == p ) // Top of the pile?
            r->players = r->players->next_in_room;

        if( p->prev_in_room ) // Someone before us?
            p->prev_in_room->next_in_room = p->next_in_room;

        if( p->next_in_room ) // Someone after us?
            p->next_in_room->prev_in_room = p->prev_in_room;

        p->in_room = NULL;

        return r;
    }
    return NULL;
}

...

ROOM *r = playerfromroom( you );
if( r )
    playertoroom( you, r->exits[ DIR_TO_GO ] );

playertoroom would be the exact same thing, except you're inserting at the top of the linked list. Or end, whatever. Furthermore, as to looking up rooms, it's not that hard at all. Yes, you could use a huge linked list, but you could just as easily use a hash table.

Commonly in DIKUs there is a function 'getroombyindex', which when given a room number (vnum) it simply finds that number in the list and returns a pointer to it.

Code:

r = playerfromroom( you )
playertoroom( you, getroombyindex( CITY_SQUARE ) );

This is exactly what your STL would do it, except we're doing it by hand rather than hiding what it's doing. Either way, the same thing is happening. Just because you hide it in overloaded braces and such doesn't mean that's not happening.

To further the point, you have declared an array of Monsters. This is a horrible idea, because again, unless you're only ever going to have a fixed number of monsters, how do you grow this without huge memory reallocation calls?

And if you use anything other than a basic array for this, you're back to doing exactly what I am. You just hide it behind a shiny interface. The same thing is happening behind the scenes.

I suppose it really depends on what you want. If you want a small static game like the Kings Quest games, then an array will work just fine. However, if you ever want more than just one fixed number of everything, it's a terrible idea.

Quzah.

This look sexy to you quzah?

Code:

#ifndef area_h
#define area_h
#include <string>

enum {NORTH,SOUTH,EAST,WEST};
const int MAX_DIR = 4;

class area
{
    public:
        area();
        area(area *north, area *south, area *east, area *west,std::string areaName,bool town)
        {
            next[NORTH] = north;
            next[SOUTH] = south;
            next[EAST] = east;
            next[WEST] = west;
            name = areaName;
            isTown = town;
        }
    private:
        area *next[MAX_DIR];    
        std::string name;
        bool isTown;
};

#endif//area_h

You may also want a constructor to link up a room based on room number. As mentioned, you'd be saving exit numbers, not pointers, to disk. (That is to say, you'd save the room number of every room this links to, not a pointer to it.)

It depends again on how you want to have it in memory. The DIKU method is to use permenant data as an index. All instances are built off the permenant indexed version. The indexed version would have the actual number of what room it links to. The instanced version would have pointers linking rooms. The indexes are used to create new instances. (Not so much so, other than at boot time, with rooms, but mainly with items and creatures.)

For example, the index version of a sword may have its textual information, and its basic stat ranges. The instanced version would refer to that, and would have any modifications and such. (Say a player casts an enchantment on their sword. This wouldn't affect the indexed version, becaues it's in effect a read-only template to build actual instances from.)

Quzah.

You are correct in that you cannot add to the array. But this is how I code most of my levels and again it depends on your approach. My goal is that everything will be in memory after the level loads. Nothing can be added that does not already exist in memory. This saves a lot of resource issues. When the game closes, everything in memory is then of course deleted.

This would not work for a dynamic online game where things can change. However I have been noticing recently that many games do not allow you to just randomly spawn objects here and there. Most games that do allow it, have major stability problems.

I can remember in Freelancer when you would blow up several ships, the items that blew off of the ship would just float in space. If you did this long enough the whole area became cluttlered. It all worked fine until you went into a space dock or planet. At that time, the objects were to be deleted and this is where the game normally crashed. They never fixed it.

In JO, Delta Force, and Pacific Fighters you cannot just spawn aircraft/objects anywhere. Essentially you can set a spawn count, but you cannot 'create' new instances of an object if it did not initially exist in the level. CFS2 did allow dynamic creation of objects as well as Janes WW2 Fighters. CFS2 did not seem to have any issues with it, but WW2 fighters would eventually frag the memory and die. So not many engines that I've seen have done it very well and it does introduce a lot of issues when you allow dynamic creation. I haven't played the new half-life or doom3 so I don't know what they do. But if you go through a level in most games, most of them have pre-determined paths, traits, and locations for all objects. As long as you own the game, it never changes. It might be a bit random, but this is normally just choosing between two or three initial game states that the level editor provided. I think most everything is scripted down to a T and the level creator is the only entity that really makes the thing look half-intelligent.

The way I would do it in a text game is pre-create everything you will need and/or re-use existing array indexes for new monsters. When a monster is dying, you already know his index into the array so you just create a new one at that index with a new location, properties, etc.

It all depends on what you want and how you want the system to work. I essentially think Quzah and I are saying the same thing, but from different perspectives and using different methods.

Either way, both systems will work and both have their advantages and disadvantages.
Hopefully the bantering will help you figure out at least how to get a rudimentary system up and running.