Hunt the Wumpus - Room Connection

Question

So I'm writing a version of the game Hunt the Wumpus in C++. The only real difference is that I'm not worried about the cave having a dodecahedron shape.

So far I've implemented the creation of the cave and the random insertion of the hero, bat, wumpus, and pit.

// Hunt the Wumpus

#include "std_lib_facilities.h"
#include "time.h"

class Room{
    bool is_occupied;
    bool has_wumpus;
    bool has_bat;
    bool has_pit;

public:
    Room()  // default constructor
    {
        is_occupied = false;
        has_wumpus = false;
        has_bat = false;
        has_pit = false;
    }

    void random_insert(vector<Room>& v);
};

void Room::random_insert(vector<Room>& v)
{
    srand(time(NULL));
    int random_room = 0;
    bool crowded = true;

    random_room = rand() % 20;  // insert hero
    v[random_room].is_occupied = true;

    while(crowded)  // insert...THE WUMPUS!
    {
        random_room = rand() % 20;
        if(v[random_room].is_occupied) ;
        else if(!v[random_room].is_occupied)
        {
             v[random_room].has_wumpus = true;
             crowded = false;
        }
    }

    crowded = true;
    while(crowded)  // insert bat
    {
        random_room = rand() % 20;
        if(v[random_room].is_occupied || v[random_room].has_wumpus) ;
        else if(!v[random_room].is_occupied && !v[random_room].has_wumpus)
        {
             v[random_room].has_bat = true;
             crowded = false;
        }
    }

    crowded = true;
    while(crowded)  // insert pit
    {
        random_room = rand() % 20;
        if(v[random_room].is_occupied || v[random_room].has_wumpus || v[random_room].has_bat) ;
        else if(!v[random_room].is_occupied && !v[random_room].has_wumpus && !v[random_room].has_bat)
        {
             v[random_room].has_pit = true;
             crowded = false;
        }
    }
}

vector<Room> create(Room& r)
{
    vector<Room> c;
    for(int i = 0; i < 20; ++i)
        c.push_back(r);
    return c;
}

int main()
{
    Room r;
    vector<Room> cave = create(r);   // create cave
    r.random_insert(cave);    // randomly insert things

}

I've got a good idea of how I'm going to implement everything else with bats dropping the hero into random places, shooting, outputting current situation, etc.

However, I'm not sure how to deal with randomly connecting the rooms in the cave. I've considered doing some kind of random sort in the vector and then connecting the rooms to the left and right with pointers, but that is just a long hallway, not a cave. Maybe I could create some kind of coordinates system? Does anyone have any recommendations? Thanks.

Answer 1

A simple solution is to pick a room with less than 3 exits, and connect to it to a random room (watch out for double connections of course). Once there are no rooms with less than 3 exits, terminate. With only 20 or so rooms it doesn't really matter how slow your implementation is.

Edit: There's a chance that some part of the map will be "cut off" from the rest this way, or connected only by one corridor. It may help to start off with a "long hallway" and then apply the above algorithm, to be sure this can't occur.

Answer 2

You can do some pretty complicated algorithms for this. I made a random maze generator in Java that uses the Drunkard's Walk algorithm to accomplish this. Effectively, you iterate through every single grid location once, then as you create a room at that location you begin placing rooms at a random available adjacent location, and connect the two if they aren't already. Keep going until you can't make a new room adjacent to the previous location, then iterate to the next available grid space. This is a little bit complicated, but works well. The best way to understand it is to run that maze generator I linked you to, and watch the maze generation in action. You should understand it quickly.

Another solution is just to store every room in a 2D grid, corresponding to their actual locations. Then simply iterate through each grid space and randomly assign pointers to the adjacent rooms. Some will have 4 connections, some 3, 2, or 1 (have a minimum of 1). I would give each room a Room *north, Room *east, Room *south, Room *west variable group, and if any of them are nil that means there's a wall there.