Sign in to follow this  
crazykid48x

linked list question

Recommended Posts

crazykid48x    100
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 this post


Link to post
Share on other sites
jfclavette    1058
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 Room5
Room1 1 0 1 1 0
Room2 0 1 0 0 1
Room3 0 0 1 1 0
Room4 1 0 1 1 0
Room5 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 this post


Link to post
Share on other sites
jfclavette    1058
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

Share this post


Link to post
Share on other sites
Morpheus011    309
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 :)

Share this post


Link to post
Share on other sites
cowsarenotevil    3003
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 Room5
Room1 1 0 1 1 0
Room2 0 1 0 0 1
Room3 0 0 1 1 0
Room4 1 0 1 1 0
Room5 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 this post


Link to post
Share on other sites
EmperiorRune    138
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 this post


Link to post
Share on other sites
jfclavette    1058
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]

Share this post


Link to post
Share on other sites
EmperiorRune    138
Quote:
Original post by jfclavette
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]
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.)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this