Adjacency Matrix implementation for game map in C++

Posted on 2009-04-01
Last Modified: 2013-12-11

***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
Question by:cruz1985
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
LVL 86

Accepted Solution

jkr earned 300 total points
ID: 24042823
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

LVL 40

Assisted Solution

mrjoltcola earned 200 total points
ID: 24042896
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.

Author Comment

ID: 24044238

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

[Live Webinar] The Cloud Skills Gap

As Cloud technologies come of age, business leaders grapple with the impact it has on their team's skills and the gap associated with the use of a cloud platform.

Join experts from 451 Research and Concerto Cloud Services on July 27th where we will examine fact and fiction.

LVL 86

Expert Comment

ID: 24044271
>>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.
LVL 86

Expert Comment

ID: 24044292
>>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.

Author Comment

ID: 24044838
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.

Featured Post

Percona Live Europe 2017 | Sep 25 - 27, 2017

The Percona Live Open Source Database Conference Europe 2017 is the premier event for the diverse and active European open source database community, as well as businesses that develop and use open source database software.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

627 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question