Public Group

This topic is 4696 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ive been trieng to learn game programming with win32 and opengl but ive decided to go back to the basics. Now what I plan to do is to make a textbased murder mystery game with only c++. The game will consist of a big maze of rooms that you can go through one at a time. Im sure I'll have many many question along the way. Anyways the first question is should I use linked list to navigate through the rooms? I dont know much about linked list but I know it could handle going in one or two directions but can it go in 4 directions? mabey if I used 2 linked list together? I know I could use arrays but I think this is the perfect project to learn about linked list.

##### Share on other sites
What you want here is a graph, not a list.

A list is a linear data structure, meaning that it can, at best, hold items sorted in some order. Graphs, on the other hand, can be seen as "unordered multi-dimensionnal linked list". For rooms, I'd probably do something like this:

      Room1 Room2 Room3 Room4 Room5Room1   1     0     1     1     0Room2   0     1     0     0     1Room3   0     0     1     1     0Room4   1     0     1     1     0Room5   0     1     0     0     1

Where one represent a way to go from a room to another, and 0 no passage. Also note that in my example above, there's a way to go from room 1 to 3, but no way to get from room 3 to 1. This suggests a unidirectionnal passage in some way. Should all passage be bidirectionnal, the matrix will be symmetrical.

##### Share on other sites
Quote:
 Original post by cowsarenotevilYou can use a "linked list" to do whatever you want. Unlike arrays or std::strings or whatever other structures you use, linked lists aren't built in to c++ in any way. So you can give it as much flexibility as you want. The only question is whether it would still be considered a "linked list" by most people.

std::list

##### Share on other sites
Quote:
 Original post by jfclavettestd::list

My goodness. I totally forgot about its existance. Its amazing how much you forget when you take a year's break from programming.

##### Share on other sites
std::list is not an effective structure for representing what seems to be a tile-based map with each node allowing up to 4 exits

##### Share on other sites
Quote:
 Original post by jfclavetteWhat you want here is a graph, not a list.A list is a linear data structure, meaning that it can, at best, hold items sorted in some order. Graphs, on the other hand, can be seen as "unordered multi-dimensionnal linked list". For rooms, I'd probably do something like this: Room1 Room2 Room3 Room4 Room5Room1 1 0 1 1 0Room2 0 1 0 0 1Room3 0 0 1 1 0Room4 1 0 1 1 0Room5 0 1 0 0 1  Where one represent a way to go from a room to another, and 0 no passage. Also note that in my example above, there's a way to go from room 1 to 3, but no way to get from room 3 to 1. This suggests a unidirectionnal passage in some way. Should all passage be bidirectionnal, the matrix will be symmetrical.

This is also what I'd do, but there are a couple of things to note. First, there's no explicit limit on how many portals a room has, and so rather than being limited to four directions, you can go from any room into any other room if you so desired. Also it's important to note that there are many different ways of representing or implimenting such a graph(group of nodes with links between them). In this case, jfclavette is basically simply using an array to represent the potential connection between each node and every other node, and whether a connection actually exists in each case. While it does have the potential for some superfluous data, though (does each room need to be able to connect to itself? Do we really need unidirectional passages?) it's a very good and quite simple way of representing the graph.

##### Share on other sites
I wouldn't do that.. if I was making a 2d map I'd make something like
//Number of items.int num_of_items = 2;char **item_name, *item_use;//Create our array of item uses.item_use = new char[num_of_items];item_use[0] = 1;item_use[1] = 3;//Create our array of item names.item_name = new char[num_of_items];item_name[0] = new char[2];item_name[0] = "A";item_name[1] = new char[2];item_name[1] = "B";//Setup enemy lookup.int num_of_enemies = 2;char **enemy_name, *enemy_hp;//Create our array of (maximum) enemy hp.enemy_hp = new char[num_of_enemies];enemy_hp[0] = 20;enemy_hp[1] = 127;//Create our array of enemy names.enemy_name = new char[num_of_enemies];enemy_name[0] = new char[2];enemy_name[0] = "C";enemy_name[1] = new char[2];enemy_name[1] = "D";//A enemy node.struct enemy{int enemy_id;int current_hp;}//A item node.struct item{int item_id;int uses;}//A room node.struct room{char *description;enemy *enemy_list;item *item_list;bool allow_north;bool allow_south;bool allow_west;bool allow_east;}//Map dimensions.int map_width = 10;int map_height = 10;//Create our map with a array.room *roomlist = new room[map_width * map_height];//Set our user position.int userX = 2, userY = 5;//Show the coordinate, as well as the description.cout << "Room " << userX << ", " << userY << endl << roomlist[(userY * map_width) + userX].description;//Make sure to deallocate..delete[] item_use, item_name, enemy_hp, enemy_name, roomlist;
Proper data modelling techniques can help you from writing needlessly sophisticated data models like a quad-linked list. Linked lists are better for when you need to remove or add something. (You change the links in a linked-list, but you don't have to reallocate an array like you would with a array.)

My example is crude.. but you could technically add in your own using objects. (alot better) I'd have something like...
User-> X, Y, Name, Item_List, ItemUse_List, HP, ExperienceToLv?
Enemy-> Name, HP, Drops_Item? ExpGain?
Item-> Name, Uses, Type? (event item? healing? does nothing?)
Rooms-> Description, DirectionsAllowed, SpecialEvents?

##### Share on other sites
Quote:
 Original post by EmperiorRuneI wouldn't do that.. if I was making a 2d map I'd make something like*** Source Snippet Removed ***Proper data modelling techniques can help you from writing needlessly sophisticated data models like a quad-linked list. Linked lists are better for when you need to remove or add something. (You change the links in a linked-list, but you don't have to reallocate an array like you would with a array.)My example is crude.. but you could technically add in your own using objects. (alot better) I'd have something like...User-> X, Y, Name, Item_List, ItemUse_List, HP, ExperienceToLv?Enemy-> Name, HP, Drops_Item? ExpGain?Item-> Name, Uses, Type? (event item? healing? does nothing?)Rooms-> Description, DirectionsAllowed, SpecialEvents?

Of course, this is a fine solution in by itself, altough, really, you should be using a 2D array if you're going to model it as a 4-neighbours-with-borders level.

However, I think the graph approach is much more flexible while incurring laughable speed penalties. What if you want to add teleporters ? What if you want a passage to collapse ? What if you want a wrap-around level ? Those are all trivialy implemented without changing the graph's code at all, while some would really be a nightmare with your setup. To be faire, always having square rooms with four passages is kind of boring. As soon as you steer away from it, your approach will REALLY get in your way. It's true that your way is easier to implement, but in this case, I think that the effort invested in mine will pay in the long run.

To each his own [smile]

##### Share on other sites
Quote:
 Original post by jfclavetteOf course, this is a fine solution in by itself, altough, really, you should be using a 2D array if you're going to model it as a 4-neighbours-with-borders level.However, I think the graph approach is much more flexible while incurring laughable speed penalties. What if you want to add teleporters ? What if you want a passage to collapse ? What if you want a wrap-around level ? Those are all trivialy implemented without changing the graph's code at all, while some would really be a nightmare with your setup. To be faire, always having square rooms with four passages is kind of boring. As soon as you steer away from it, your approach will REALLY get in your way. It's true that your way is easier to implement, but in this case, I think that the effort invested in mine will pay in the long run.To each his own [smile]
I agree, it won't make a huge difference with a small text map with a console application. But if he thought that was the only way to do a map, I'd be a little concerned. (I know when I was starting with 2D maps I thought map[x][y] was the only way to go.)

1. 1
2. 2
Rutin
23
3. 3
4. 4
frob
16
5. 5

• 9
• 33
• 13
• 12
• 10
• ### Forum Statistics

• Total Topics
632579
• Total Posts
3007171

×