Solved

Adjacency Matrix implementation for game map in C++

Posted on 2009-04-01
6
1,485 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
U.S. Department of Agriculture and Acronis Access

With the new era of mobile computing, smartphones and tablets, wireless communications and cloud services, the USDA sought to take advantage of a mobilized workforce and the blurring lines between personal and corporate computing resources.

 
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

ScreenConnect 6.0 Free Trial

Check out the updates in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI that improves session organization and overall user experience. See the enhancements for yourself!

Question has a verified solution.

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

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
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 viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

809 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