Solved

Adjacency Matrix implementation for game map in C++

Posted on 2009-04-01
6
1,483 Views
Last Modified: 2013-12-11
Hi,

***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:

Classes:
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:

01100
10000
10011
01000
00100

Many thanks
0
Comment
Question by:cruz1985
  • 3
  • 2
6 Comments
 
LVL 86

Accepted Solution

by:
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},

  { EAST | NORTH} , { WEST | NORTH}

};
 

// esample for a simple check
 

if (grid[1][1] & SOUTH) {
 

  // OK, can move to the south

}

Open in new window

0
 
LVL 40

Assisted Solution

by:mrjoltcola
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;
    player->moveToRoom(newRoom);
}

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.
0
 

Author Comment

by:cruz1985
ID: 24044238
mrjoltcola,

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.

jkr,

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

0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 86

Expert Comment

by:jkr
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.
0
 
LVL 86

Expert Comment

by:jkr
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.
0
 

Author Comment

by:cruz1985
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.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
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 viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

939 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now