Adjacency Matrix implementation for game map in C++


***please note, i have typed a fairly long explanation, but it would probably only take someone a few minutes to answer my question***

I am building a text adventure game in c++ ("move north", "unlock door", that type of game).

At the moment i am concentrating on just building a simple game engine consisting of just being able to move from one location (room) to another.

I have already achieved this first part, and this is roughly how it works:

locationClass - contains locationID, description and all exits and where they lead to (i.e. "int north = 2", would mean that an exit is available north and it leads to location 2).

MapClass - this acts as a container class for all locationClass objects.

playerClass - contains currentLocation which would be the locationID of the relevant locationClass object.

1. The current location is displayed on screen. Lets assume the player types the command "north".
2. The current locationID is retrieved from the player class
3. The locationClass object that matches this ID is checked to see if has an available exit north.
4. lets assume that it does, and that "int north = 2".
5. the players currentLocation is updated to 2, and the new locations description is displayed.

That's pretty much it. The problem is i need to use a different system of how to move the player around and check what exits are available from what locations. What i need is the game working like above but with an adjacency matrix as a "map" for my game.

Everytime the player types a command, the adjacency matrix would need to be checked to see if the move is possible. This is what i need someone to help me with.

Can someone explain the steps required for this process? For this example it would be fine to stick to 5 locations in the map. So the matrix could look like this, for example:


Many thanks
Who is Participating?

Improve company productivity with a Business Account.Sign Up

jkrConnect With a Mentor Commented:
You could do that in a pretty simple way by using a bitmask for every location, e.g.
// possible moves
#define NORTH 0x01
#define WEST  0x02
#define SOUTH 0x04
#define EAST  0x08
// example for a 2x2 grid where you can move in between all four cells
// but not over the boundaries
typedef unsigned char BYTE; // might already be available though
BYTE grid[2][2] = {
  { EAST | SOUTH} , { WEST | SOUTH},
// esample for a simple check
if (grid[1][1] & SOUTH) {
  // OK, can move to the south

Open in new window

mrjoltcolaConnect With a Mentor Commented:
If you are implementing this for a real game, I'll tell you how I did it in my MUD codebase years ago called MUD++, you can still find it out on the net if you poke around.

Before you choose your approach, consider something. Do you want your world to be spatially accurate / consistent. By that, I mean, do you want your rooms / locations to properly layout, so that there are no "worm holes" and/or exits that do not make sense, (like going north, then having south not point back to where you came). That may drive your approach.

But anyway, here is an approach.

class Room represents a room or location
class Exit represents a "door" or "exit"

Each Room will contain an array of 6 Exit objects. The Exit class will have a Room pointer, as well as other information about the "door" or exit. (Locked, pickable lock, name of the door, hidden descriptions)

Each Room also has a linked list of Objects, so multiple things, players, etc. can be in a room. If your hierarchy inherits Players and Items from the same base class, then one list is all you need, but in my games, I used separate lists.

Each Room has an array of Exits. Simplest case is 6 slot array U/D/N/E/S/W

class Exit {
   Room * room;
   string description;
   int flags; // hidden, locked, etc.

class Room {
   int id;
   Exit *exits[MAX_DIRECTION];
   list<Object> objects;
   list<Player> players;

class Player {
   Room * inRoom;

So you can have distinct room IDs, and store them in an overall container, but for performance, you should link the rooms with pointers, so you don't have to use the container for look and retrieval everytime a player moves. Each time the player moves, set inRoom to the current room pointer. Then moving NORTH essentially becomes

if(inRoom->hasExit(DIR_NORTH)) {
    Room * newRoom = inRoom->exits[DIR_NORTH]->room;

Of course its more involved than that if the game is multi-player, but I hope you get the idea. The reason it is good to link the rooms is because some algorithms you may write work much better if they can traverse the world directly as a tree or graph, rather than looking up the room by ID. If you wanted to implement a "look" feature where the player can say "look EAST", then you can do "while(room->exits[DIR_EAST] != NULL) room = room->exits[DIR_EAST]->room;"

You really want to be able to traverse the world as an in-memory graph datastructure with pointers. Now, I may have gone overboard, maybe you just want something simple. In that case, a simple array works great, and jkr gives you a start above.
cruz1985Author Commented:

thanks for your post. Makes good sense and i can see how it would work. I should have mentioned, though, that i'm building this for a class assignment which requires the map to be a 2d adjacency matrix, so for now, i will stick with that approach.


i'm not familiar with bitmasks so did a quick google search. A few of the sites i come across mentioned not to use them as they are not portable and differ on different machines/compilers. If this is true, i don't think i could go down this route as i would probably lose marks for it. Is there a different way to do it?

The way i was looking at it was to create a 2d array of bool, such that the array indices represent the locations (rooms) and a true/false value indicates a connection or lack thereof. The task would then be to somehow map each edge (connection) as being north, south, etc.

Going back to your code, i'm not sure exactly whats going on here:

// possible moves
#define NORTH 0x01
#define WEST  0x02
#define SOUTH 0x04
#define EAST  0x08

Open in new window

The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

>>A few of the sites i come across mentioned not to use them as they are not
>>portable and differ on different machines/compilers

Um, no, that's absolutely not true - bit flags are one of the most commonly things in programming. They bsically mean that you associate one particular bit in a byte with a specific meaning and check whether it is set or not by one cheap (as in "performance") bitwise AND operation. That is even more than portable.
>>Going back to your code, i'm not sure exactly whats going on here

That's the "associate one particular bit in a byte with a specific meaning" part. E.g. bit 0 (0x01) is associated with the attribute NORTH (or named that symbol, because it is easier to handle).

That way, you only need one byte per cell and not a whole array. Also, initializing the matrix becomes a lot easier.
cruz1985Author Commented:
Ok jkr, seems like it is what i need. thanks for your help.

Thinking about it a bit further, i can't see my lecturer minding if i implement it the way mrjoltcola has suggested. Could be seen as taking the assignment to the next level.

Both solutions are good for me. Thanks guys.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.