linked list question
Author
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.
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:
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.
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.
Quote:Original post by cowsarenotevil
You 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
I agree with jfclavette, a graph is probably the best thing for your scenario. However if you aren't too clear on linked lists I would recommend learning about them before diving into graphs as they generally are much less complex. A linked list consists of a node (this is where your data is held) and a single pointer that points to your next node (singly linked list) or a pointer to both your next and previous nodes in the list (doubly linked list). There is also a cyclical linked list but you probably won't have much use for that. A graph is essentially the same concept but instead of only having a pointer to your next and possibly your previous nodes, you have a pointer to any nodes associted with the current node. This is the ideal data structure for a map as one room may lead into many (one node represents a room and a pointer represents a door to another room). Hope that helps :)
Quote:Original post by jfclavette
std::list
My goodness. I totally forgot about its existance. Its amazing how much you forget when you take a year's break from programming.
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
Quote:Original post by jfclavette
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.
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.
I wouldn't do that.. if I was making a 2d map I'd make something like
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?
//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;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?
Quote:Original post by EmperiorRune
I 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]
Quote:Original post by jfclavetteI 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.)
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
