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
  • 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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

830 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