09 Jul, 2008, Impacatus wrote in the 1st comment:
Votes: 0
I'm pretty new to programming in general. These I know it may be an ambitious goal at my level, but I'm trying to code a MUD from scratch. I have a couple of questions about data that are probably not specific to any language, but if they are I'm using c++.

What's the best way to link two records to each other? Let me explain. I plan to have a system where items have a certain amount of customization availible. What this means is that each individual item has to have its own entry in the database instead of just being a number. So each of these records might have a variable to indicate where in the game world the object is. But this would mean that when a player wanted to look at their inventory, the server would have to search through every single item in the game world to find the ones located in that particular player's inventory. Like I said, I don't know much about programming, but this sounds inefficient. Is there a better way, or is this not as big of a problem as it sounds to me?

My other question is about persistance. I'm not sure if I should plan to load the entire database into RAM at the start of the boot, then update it all at once at the end, or only load data as needed and continously save any changes to the data. Are they both even possible? If so, which one is generally recommended?

I didn't know who else to ask these questions, so thanks in advance for your answers.
09 Jul, 2008, kiasyn wrote in the 2nd comment:
Votes: 0
http://en.wikipedia.org/wiki/Linked_list...

In my MUD i load the entire database (more or less) into ram at boot, then save changes as they're made.
09 Jul, 2008, Impacatus wrote in the 3rd comment:
Votes: 0
Thanks for the response. I'm trying to understand what linked lists are and how they pertain to my question, but I'm having a little trouble. If you could explain using my example, I would appreciate it.

That sounds like a good way to handle the database issue, are there any disadvantages?
09 Jul, 2008, David Haley wrote in the 4th comment:
Votes: 0
A list is an ordered sequence of not necessarily unique elements. A linked list is a list that is implemented by representing each element as a node, with a pointer to the next node in the list. Contrast with an array, which is a list implemented as a block of elements in memory, that can be accessed directly by element number. In a linked list, you must traverse the list until you find the n^th element. Linked lists have fast insertion, whereas an array's insertion performance becomes worse as the array becomes more full.

But a linked list is not actually what you described (but, see below). The problem you described was having to search an entire list to find items belonging to specific players. The typical way of solving this kind of problem is by using an associative array, also known as a map. (Some people call them "hash tables" but that is a misnomer, as a hash table is a kind of map implementation.) A map is a data structure that stores key/value pairs. For any possible key, you have exactly zero or one value in the map.

In this case, you would associate with each player a list of items in that players inventory. Now, when a player wants to see their inventory, you find that player's list in the inventory map, and display it. The real implementation of such a solution would bypass the lookup phase and store the reference to the list in the player object directly.

If you're serious about choosing data structures correctly, I would start by exploring which ones are available. The Wikipedia article on abstract data types gives an overview of what they are and what they're good for. You should understand the information on this page if you want to design a system as large as a MUD.

I would also recommend reading the handouts from an introductory programming course (e.g. this one), or better yet, taking one if you are in a position to do so.

Designing a basic MUD server is not the world's hardest problem but it is non-trivial and involves several decisions. The key is to stay focused on what you want to do. If you start running amok with features without pacing yourself, you will end up with more of nothing than a showable result. (Been there, done that. :rolleyes: )

Hopefully something in here will have been useful to you…
09 Jul, 2008, Impacatus wrote in the 5th comment:
Votes: 0
Thank you. Let me see if I understand about these maps. I would use the item index as the key, and the player index as the mapped value, right? Or is there an advantage to doing it the other way around using a multimap, or both? If I understand correctly, it's practically the same thing as iterating through the whole list, but designed to be more efficient partly because there are fewer elements on the records being searched, so the array can be iterated through faster than the database itself. Is this correct?

EDIT: Then again, I suppose a double link would eliminate the need to iterate through the list.

I will try to do more research on abstract data types. Thanks for your advice and patience.
09 Jul, 2008, David Haley wrote in the 6th comment:
Votes: 0
Impactus said:
I would use the item index as the key, and the player index as the mapped value, right? Or is there an advantage to doing it the other way around using a multimap, or both?

Well, it depends on what exactly your problem is. If what you're trying to do is only to give players an inventory list, then I would just create a linked list in each player and make that the inventory. If you need to store the objects in other lists at the same time, that's fine; you can have other lists with references (pointers) to the same objects. You just need to be careful about who "owns" the pointer so that you can delete it at the appropriate time.

I think one thing that might help is to separate the conceptual aspect of what you're doing from the implementation details. It sounds like you really want to create a master database of some sort that contains a giant list of all objects in the game. Well, ok, that makes a lot of sense conceptually (it is the most natural model in some sense), but you will hit several implementation issues. This data structure issue is one of them. So, you need to think about what you want to do in general, and then you need to think about what you really want to do in terms of very specific requirements. What exactly are you trying to achieve? If you formulate the question precisely enough, with experience the questions will guide you straight to the answers almost without effort. As with many problems, the real effort is actually in asking the right question, not in answering it.

Impactus said:
If I understand correctly, it's practically the same thing as iterating through the whole list, but designed to be more efficient partly because there are fewer elements on the records being searched, so the array can be iterated through faster than the database itself. Is this correct?

Well, I guess so. :smile: In some sense, almost any data structure is just a more intelligent version of the list-based data structure. A more useful answer to your question might be that yes, the end result is the same in terms of input and output, but choosing a better data structure can sometimes mean the difference between completing computation in this lifetime or the next. (Seriously, actually.) Imagine that, were you to look something up in the dictionary, you had to start at the first word in A, and read every single word until you found the one you wanted. Contrast with a human-driven binary search where you flip to the middle, and then go to the appropriate half until you find your word. The former would take a very long time; the latter takes seconds. It's the same thing with data structures: looping over all objects finding the ones that belong to a character will take much more time than having a very quick access to a list of that characters objects.

Impactus said:
Then again, I suppose a double link would eliminate the need to iterate through the list.

Well, sort of. Doubly-linked lists make things like deletion faster. You still have no way of accessing item number 27 without stepping to that position from either end of the list.
09 Jul, 2008, Impacatus wrote in the 7th comment:
Votes: 0
Quote
Well, it depends on what exactly your problem is. If what you're trying to do is only to give players an inventory list, then I would just create a linked list in each player and make that the inventory. If you need to store the objects in other lists at the same time, that's fine; you can have other lists with references (pointers) to the same objects. You just need to be careful about who "owns" the pointer so that you can delete it at the appropriate time.


Huh. I didn't think of that. I hadn't heard of linked lists, so I was thinking I'd have to use arrays, and it seemed over-complicated to try to create arrays in each player to accomodate objects with different properties. I still have a lot to learn, of course.

Does this solution still work if there are multiple levels? For example, if you have a list of planets, and in each planet you have a list of continents, and in each continent you have a list of countries and so on? I guess it would, but wouldn't efficiency degrade each level, since you have to search deeper and deeper into the record to find a specific element?

Quote
I think one thing that might help is to separate the conceptual aspect of what you're doing from the implementation details. It sounds like you really want to create a master database of some sort that contains a giant list of all objects in the game. Well, ok, that makes a lot of sense conceptually (it is the most natural model in some sense), but you will hit several implementation issues. This data structure issue is one of them. So, you need to think about what you want to do in general, and then you need to think about what you really want to do in terms of very specific requirements. What exactly are you trying to achieve? If you formulate the question precisely enough, with experience the questions will guide you straight to the answers almost without effort. As with many problems, the real effort is actually in asking the right question, not in answering it.

A giant master database was indeed my original plan. My thinking was that when you have objects with non-straightforward relations to each other, it would be simplest to keep them all on one list. I may have to rethink this though.

What if I did this, but also used a system of pointers and maps to better access individual elements when needed? For example, I could have each item have its own record, but put a list of pointers in each player to represent their inventory. Could this be made to be efficient? I really need to read up on data structures.

Anyways, thanks for all your help, it's been informative, and I think your advice will be very helpful.
09 Jul, 2008, David Haley wrote in the 8th comment:
Votes: 0
Impactus said:
Huh. I didn't think of that. I hadn't heard of linked lists, so I was thinking I'd have to use arrays, and it seemed over-complicated to try to create arrays in each player to accomodate objects with different properties. I still have a lot to learn, of course.

One thing you should get used to is thinking in terms of abstract data types, like "list", not specific implementations like linked lists or arrays. This will help you organize your thinking, and you can work out the implementation details later. Personally I find it distracting to think in terms of implementation details when I still don't have a good high-level picture of what I'm trying to do. I try to specify the program in the most abstract way possible, sometimes thinking in terms of lists, sets, or even just collections (more general than lists or sets).

For an example of how this thinking helps, once you know that you want an ordered sequence (list) you can pick an implementation. The C++ Standard Template Library provides implementations for lists in the form of linked lists (called 'list') and vectors (called 'vector') that are basically "plug and play" – you can very easily add, remove, search etc. and it does the nitty-gritty work for you. (A detail of arrays, for instance, is dealing with reallocating it when you need more elements than you can currently hold.)

Impactus said:
Does this solution still work if there are multiple levels? For example, if you have a list of planets, and in each planet you have a list of continents, and in each continent you have a list of countries and so on? I guess it would, but wouldn't efficiency degrade each level, since you have to search deeper and deeper into the record to find a specific element?

Well, as usual, it depends on a lot of things, e.g. what exactly you mean by the above. If you use good data structures, you can actually get better performance by introducing these extra levels. Recall that following one path also means filtering out all the others, so if you go to continent A, you will no longer be looking at the stuff on continent B.

Impactus said:
A giant master database was indeed my original plan. My thinking was that when you have objects with non-straightforward relations to each other, it would be simplest to keep them all on one list. I may have to rethink this though.

Well, it depends on what those relations are. You are correct that unusual or complex relations will require some kind of solution that might mean an efficiency problem. One solution could be to keep only these special objects on a big list; the hope is that there will be few enough of them for it to matter. Still, you need to specify very precisely what kinds of relations you will actually have. Trying to design something this complex for requirements that aren't precise is rather like the metaphorical needle and haystack. :wink:

Impactus said:
What if I did this, but also used a system of pointers and maps to better access individual elements when needed? For example, I could have each item have its own record, but put a list of pointers in each player to represent their inventory. Could this be made to be efficient? I really need to read up on data structures.

Any time you have direct references, you are basically as efficient as you can be. If I know that this object's "parent" is that object, there is no search involved in finding the parent: I just dereference the pointer which is one of the fastest operations of them all. The problem is that you need to maintain these direct references. If an object disappears for some reason, you need to find some way of updating every single other object that depended on or referred to that object. This is a memory management problem so that might be a topic to look into as well.

One thing I might suggest is to start very simple, even if what you end up isn't what you wanted. Designing a MUD server is non-trivial and you'll run into several tricky issues. But as they say about running and walking, it might be simpler to start with a very basic program that acts like a chat server: accept connections on the network, and echo anything that anybody types to everybody else. This will get you started with how these beasts work, and what kind of issues you will run into. Then you can build up from there: introduce a login process; introduce special commands that do things like "say" or "exit"; create trivial "rooms" that people can be in and change from one to the other; make these rooms connected by exits on a graph; etc. You should expect to make mistakes in this process and maybe even throw away some or all of the code as you learn, but even though this might sound like the long way I think that it could be the more productive path all things considered. At least, that's been the case in my experience…
09 Jul, 2008, Impacatus wrote in the 9th comment:
Votes: 0
Quote
Well, as usual, it depends on a lot of things, e.g. what exactly you mean by the above. If you use good data structures, you can actually get better performance by introducing these extra levels. Recall that following one path also means filtering out all the others, so if you go to continent A, you will no longer be looking at the stuff on continent B.

Well my thinking was that if you were looking for a certain "city" with no information on where it is, you'd still have to search through all the cities in the system, except you'd also have to access the record of every province, country, continent, and planet in order to get to the city information. This seems more complicated than searching through a simple list. I could be wrong though.

Quote
Any time you have direct references, you are basically as efficient as you can be. If I know that this object's "parent" is that object, there is no search involved in finding the parent: I just dereference the pointer which is one of the fastest operations of them all. The problem is that you need to maintain these direct references. If an object disappears for some reason, you need to find some way of updating every single other object that depended on or referred to that object. This is a memory management problem so that might be a topic to look into as well.

Alright, I think I understand this a little better now, thanks again.

Quote
One thing I might suggest is to start very simple, even if what you end up isn't what you wanted. Designing a MUD server is non-trivial and you'll run into several tricky issues. But as they say about running and walking, it might be simpler to start with a very basic program that acts like a chat server: accept connections on the network, and echo anything that anybody types to everybody else. This will get you started with how these beasts work, and what kind of issues you will run into. Then you can build up from there: introduce a login process; introduce special commands that do things like "say" or "exit"; create trivial "rooms" that people can be in and change from one to the other; make these rooms connected by exits on a graph; etc. You should expect to make mistakes in this process and maybe even throw away some or all of the code as you learn, but even though this might sound like the long way I think that it could be the more productive path all things considered. At least, that's been the case in my experience…

When I said I was doing this from scratch, that wasn't entirely accurate. I'm planning on using the socketmud codebase, which only handles the sockets and connections. I have suceeded in adding login, chat, and room functions to it.

The main problem I have is, even if I can figure out a way to do things, I never know if it's the best way. My concern is that solutions which work for small, simple programs could degrade in efficiency once more complexity is added. Still I see your point.

Anyways, conceptually, here's what I'm thinking now. There will be a master list of all objects in the game. Each of these objects will contain references to all objects that are related to them. These references go both ways. For example, each "player" object will contain references to all items in that player's inventory. Each "item" object will contain a reference to the player who holds it in their inventory. In every function that changes these relationships, care will be taken to make sure that all these references are properly updated. I realize this would be somewhat error prone, but… I'll be really really careful. :smile:

Does this sound like a feasible solution?
10 Jul, 2008, David Haley wrote in the 10th comment:
Votes: 0
Impactus said:
Well my thinking was that if you were looking for a certain "city" with no information on where it is, you'd still have to search through all the cities in the system, except you'd also have to access the record of every province, country, continent, and planet in order to get to the city information. This seems more complicated than searching through a simple list. I could be wrong though.

If you expect that the common use case is to search for a city by its name, then you could make a map that connects city names to city objects. Then, looking up cities by name becomes quite efficient. Basically, you need to figure out what the common case(s) will be, and choose your data structures accordingly.

Impactus said:
The main problem I have is, even if I can figure out a way to do things, I never know if it's the best way.

This is a problem for nearly all programmers for nearly all problems. :lol: So you're definitely not alone here…

Impactus said:
My concern is that solutions which work for small, simple programs could degrade in efficiency once more complexity is added.

The algorithms analysis subfield of computer science deals with this kind of issue. What you want to look at is complexity analysis: the study of how a solution's run time changes with its input size. See for example Big-O notation which provides a mathematical bound on the time the solution will take as a function of the input size.

Impactus said:
Anyways, conceptually, here's what I'm thinking now. There will be a master list of all objects in the game. Each of these objects will contain references to all objects that are related to them. These references go both ways. For example, each "player" object will contain references to all items in that player's inventory. Each "item" object will contain a reference to the player who holds it in their inventory. In every function that changes these relationships, care will be taken to make sure that all these references are properly updated. I realize this would be somewhat error prone, but… I'll be really really careful. :smile:

Does this sound like a feasible solution?

This isn't so different from what SMAUG does, so yes, it is feasible. It is dangerous, though, and even the best intentions aren't always enough when it comes to being careful. :smile: There have been many bugs in SMAUG due to not correctly clearing references. For instance, if character A is following character B, and character B disappears, you need to go to character A and remove the follow reference. If you forget to do so, then the next time you try to look at who A is following, the game will crash. This kind of problem is very subtle.

Actually, this is one of the hardest problems to deal with, when taken generally. A common solution is reference counting, so that objects only disappear from memory when nobody references them anymore. This prevents crashing but won't prevent "incorrect" references: if B is gone, A really shouldn't think it's following B anymore. So you still need to do something, one way or the other.



But anyhow. You can have a master list of objects, like SMAUG does, and then have separate "views" into that list based on special cases. For instance, each character will have a list of the objects it owns. All of those will be references to objects in the master list.
0.0/10