24 Jun, 2013, Altraen wrote in the 1st comment:
Votes: 0
Hello. Sorry to make my first post a request for help, but I'm honestly at a loss here. I've been working on coding a custom MUD for several weeks now, and I've hit a slight design snag that's had me stumped for more than a few days now. Vnums are usually things that need to persist across reboots. It's also usually a good idea to have them be unique (at least in their own subcategory) and likely have them match up in their container. Now, the issue in this problem seems to stem in deletion. (This is where I'll apologize if this is better fitted for the C++ forum rather than the Coding/Design one).

In a vector, deletion comes with the issue of everything below it shifting upward in memory, and therefore by index. In a map(/set/associative array), you're not hit by that issue, but it does seem to get a bit unwieldy (and then some) when dealing with empty positions. And using a combination of the two just seems like a waste of memory. As well, there's the question of how to work things if you want two different objects to share a vnum list, but that's probably something a mutual inherited class can solve (though the whole id issue there becomes a problem).

I suppose I've rambled on for a bit now, so I'll cut it here. I've just been stuck on this, and was hoping for some input from the experts on how this would best be solved, or perhaps any obvious options I'm missing. Thank you.

P.S. I'm really sorry about how much I ramble on in this.
24 Jun, 2013, plamzi wrote in the 2nd comment:
Votes: 0
Altraen said:
In a vector, deletion comes with the issue of everything below it shifting upward in memory, and therefore by index.


This would be an issue only if you're trying to match up the unique id / vnum with the index value. Assume that those would be different and the issue goes away.

Altraen said:
In a map(/set/associative array), you're not hit by that issue, but it does seem to get a bit unwieldy (and then some) when dealing with empty positions.


I'm not exactly sure how C++ maps work, but if they are key => value structures, what is the problem with only allocating members whose key exists and deallocating members by key when they cease to exist?

Altraen said:
As well, there's the question of how to work things if you want two different objects to share a vnum list, but that's probably something a mutual inherited class can solve (though the whole id issue there becomes a problem).


I'm not sure what the design goal is here, but assuming that the list is just data and doesn't contain any methods, what is wrong with different objects having pointers to the same list?
24 Jun, 2013, Altraen wrote in the 3rd comment:
Votes: 0
plamzi said:
This would be an issue only if you're trying to match up the unique id / vnum with the index value. Assume that those would be different and the issue goes away.


I am. I didn't, however, consider not grouping them… That would simplify things, though searching for a specific ID would require a full iteration, as would getting the next free ID (unless I track it elsewhere, which for several containers, would be difficult to say the least).

plamzi said:
I'm not exactly sure how C++ maps work, but if they are key => value structures, what is the problem with only allocating members whose key exists and deallocating members by key when they cease to exist?


Yes, maps are key => value. And the issue with them isn't allocation/deallocation, but keeping track of free IDs.

plamzi said:
I'm not sure what the design goal is here, but assuming that the list is just data and doesn't contain any methods, what is wrong with different objects having pointers to the same list?


The design goal for shared vnums is, honestly, to make things in the room (mobs, items) targetable by their ID to allow a player to target/interact with an item by a unique reference.
24 Jun, 2013, Davion wrote in the 4th comment:
Votes: 0
Are your vnums going to be unique to a loaded object? The way they work in the dikurivatives, is basically using it as an index to point to the template of the object.

They have two separate classes, a _INDEX_DATA and the actual data struct for the object. Very rarely are the actual indexes deleted, although it does happen when in development and builders are chompin away. If what you are describing, is a container holding simply the index values instead of the objects themselves, your objects cannot be unique from one to the next (ie. they'd all share the same effects).

Now the objects themselves get deleted all the time! You eat something, drop a proof object, or just watch your sword blow up into a million pieces. If you delete by vnum, wouldn't that remove all instances of that object? You might be looking for a unique way to track loaded objects, in which case, vnums probably wouldn't do it for you (at least not in the classic sense).
24 Jun, 2013, Altraen wrote in the 5th comment:
Votes: 0
Davion said:
Are your vnums going to be unique to a loaded object? The way they work in the dikurivatives, is basically using it as an index to point to the template of the object.

They have two separate classes, a _INDEX_DATA and the actual data struct for the object. Very rarely are the actual indexes deleted, although it does happen when in development and builders are chompin away. If what you are describing, is a container holding simply the index values instead of the objects themselves, your objects cannot be unique from one to the next (ie. they'd all share the same effects).

Now the objects themselves get deleted all the time! You eat something, drop a proof object, or just watch your sword blow up into a million pieces. If you delete by vnum, wouldn't that remove all instances of that object? You might be looking for a unique way to track loaded objects, in which case, vnums probably wouldn't do it for you (at least not in the classic sense).


Yes, I intended for them to be unique to a loaded object. However, the template/index system Diku has does seem to have some benefits to it, and I'll have to look into that.
24 Jun, 2013, Davion wrote in the 6th comment:
Votes: 0
You might want to take a look at the way others have gone as per UUID. Here's a couple threads with people having very similar problems.
http://www.mudbytes.net/index.php?a=topi...
http://www.mudbytes.net/index.php?a=topi...

There's quite a bit if information in those threads, so I hope something helps!
24 Jun, 2013, Runter wrote in the 7th comment:
Votes: 0
Quote
I am. I didn't, however, consider not grouping them… That would simplify things, though searching for a specific ID would require a full iteration, as would getting the next free ID (unless I track it elsewhere, which for several containers, would be difficult to say the least).


I assure you that while this isn't the most efficient solution, most muds already do similarly inefficient lookups and it's most likely good enough for your purposes. And also easily encapsulated so you can change the implementation of the read later.
24 Jun, 2013, plamzi wrote in the 8th comment:
Votes: 0
Altraen said:
plamzi said:
This would be an issue only if you're trying to match up the unique id / vnum with the index value. Assume that those would be different and the issue goes away.


I am. I didn't, however, consider not grouping them… That would simplify things, though searching for a specific ID would require a full iteration, as would getting the next free ID (unless I track it elsewhere, which for several containers, would be difficult to say the least).


There's at least one algorithm that can give you 50% efficiency over a full iteration. See any Dikurivative. But, you're writing a MUD on 2013 hardware–are you that worried? As for keeping track of the next free id, that's pretty simple if you use a database for storage. If not, then you have to decide if the simplicity of an array is worth it. Often times, the answer is yes, because it's not like you'll be adding containers on a daily basis.

Altraen said:
Yes, maps are key => value. And the issue with them isn't allocation/deallocation, but keeping track of free IDs.


The only data structure I know of that will natively give you Unique ID info is a SQL database that can supply the auto-incremented ID of its newest record or can be queried in a way that returns the maximum value within a result set. Barring that, whether you go with a flat array or an associative array, you're going to have to write some utility functions to scan for the next available ID. That's just how it is when you're writing a custom codebase.

Altraen said:
The design goal for shared vnums is, honestly, to make things in the room (mobs, items) targetable by their ID to allow a player to target/interact with an item by a unique reference.


You are clearly talking about instance ID's as opposed to VNUMs. For that, you need to start with a use case. Are you expecting to serve these id's to the player's client and have the client use them as the handle, guaranteeing the right target? Or are you going to be showing the id to the users and expecting them to type it back, in which case it would have to be user-friendly?

If you're not going to show the user this data, there is really nothing stopping you from having a single sequential list of unique id's for all your instanced objects. Just remember that a lot of instanced stuff really doesn't need a unique ID until it becomes target-able. For example, items loaded in the wild would only need a unique id when they come within the reach of a human player.

If you do want to show this unique handle to the user, I would personally recommend a contextual handle (2.sword will always be more user-friendly than 91232.sword).

It's also possible to do both, like we do (for quality items only). We have a unique handle being served via GMCP and a contextual handle for users typing.
24 Jun, 2013, Altraen wrote in the 9th comment:
Votes: 0
Davion said:
There's quite a bit if information in those threads, so I hope something helps!


While sifting through the semi-offtopic arguments in them, I did find a few things that triggered some inspiration. Thank you.

Runter said:
I assure you that while this isn't the most efficient solution, most muds already do similarly inefficient lookups and it's most likely good enough for your purposes. And also easily encapsulated so you can change the implementation of the read later.


Yeah. I'm not overly concerned about efficiency, but it's not something I like to ignore without looking at alternatives either.


plamzi said:
There's at least one algorithm that can give you 50% efficiency over a full iteration. See any Dikurivative. But, you're writing a MUD on 2013 hardware–are you that worried? As for keeping track of the next free id, that's pretty simple if you use a database for storage. If not, then you have to decide if the simplicity of an array is worth it. Often times, the answer is yes, because it's not like you'll be adding containers on a daily basis.


std::sort by id over the vector, then iteration at O(N) would also, in the scheme of things, be fairly fast. I'm not overly worried about speed, but… see my reply to Runter.

plamzi said:
The only data structure I know of that will natively give you Unique ID info is a SQL database that can supply the auto-incremented ID of its newest record or can be queried in a way that returns the maximum value within a result set. Barring that, whether you go with a flat array or an associative array, you're going to have to write some utility functions to scan for the next available ID. That's just how it is when you're writing a custom codebase.


Yeah, I knew it wouldn't be easy. Was just hoping I was missing something, honestly, that others would have considered.

plamzi said:
You are clearly talking about instance ID's as opposed to VNUMs. For that, you need to start with a use case. Are you expecting to serve these id's to the player's client and have the client use them as the handle, guaranteeing the right target? Or are you going to be showing the id to the users and expecting them to type it back, in which case it would have to be user-friendly?


The former is actually my use case. The latter will also be an option for certain situations (First object in room has a symbol that matches latter objects, but is something you really don't want to be attacking. While this is arguably an example of horrid building guidelines, I'd rather not have a player's time wasted/ruined because a builder made an honest mistake. And yes, this comes from my own experiences).

plamzi said:
If you're not going to show the user this data, there is really nothing stopping you from having a single sequential list of unique id's for all your instanced objects. Just remember that a lot of instanced stuff really doesn't need a unique ID until it becomes target-able. For example, items loaded in the wild would only need a unique id when they come within the reach of a human player.

If you do want to show this unique handle to the user, I would personally recommend a contextual handle (2.sword will always be more user-friendly than 91232.sword).

It's also possible to do both, like we do (for quality items only). We have a unique handle being served via GMCP and a contextual handle for users typing.


I will be doing that as well, though the contextual handle will be implied (and mentioned in help files) while the non-contextual will be displayed. However, I personally find the contextual handle a bit more unwieldy than a simple string of "91232". Maybe that's just me, though.


Also, think I've found another option that may work. A preallocated(to some inane number that shouldn't be reached but isn't a memory-killer) vector of pointers to the objects, initially filled with pointers to a 0-id default-constructed object. This seems to solve all of the problems listed. Insertion is as simple as replacing the default pointer. Deletion, pull the pointer from the vector, replace it with a copy of index 0, and delete the pulled object. Finding the next ID should be as simple as iterating through and checking the id for 0. Getting the object by ID, as simple as… well, accessing the vector by ID. I'll give this a go, assuming no glaringly obvious problems are made aware in the meantime. Thank you all again for your help.
24 Jun, 2013, plamzi wrote in the 10th comment:
Votes: 0
Altraen said:
Also, think I've found another option that may work. A preallocated(to some inane number that shouldn't be reached but isn't a memory-killer) vector of pointers to the objects, initially filled with pointers to a 0-id default-constructed object. This seems to solve all of the problems listed. Insertion is as simple as replacing the default pointer. Deletion, pull the pointer from the vector, replace it with a copy of index 0, and delete the pulled object. Finding the next ID should be as simple as iterating through and checking the id for 0. Getting the object by ID, as simple as… well, accessing the vector by ID. I'll give this a go, assuming no glaringly obvious problems are made aware in the meantime. Thank you all again for your help.


What about persistence? Usually, the whole point of having unique ID's is so they are truly unique, not something that changes at every boot. Maybe you're only thinking of covering targetting at this point, but persistent unique ID's are useful for other purposes, such as debugging, tracking items in players' possession, balancing. They can also assist if you want to offer randomized items or deep crafting.

I think you really need to do some more research, and maybe come up with some more use cases, before doing anything. Sometimes, when you code something as fundamental as this, you absolutely want it to serve multiple purposes.

Altraen said:
However, I personally find the contextual handle a bit more unwieldy than a simple string of "91232". Maybe that's just me, though.


It's not important what you or I prefer. It is important to consider what your target audience would prefer (and expect).
24 Jun, 2013, Tyche wrote in the 11th comment:
Votes: 0
Altraen said:
Yes, maps are key => value. And the issue with them isn't allocation/deallocation, but keeping track of free IDs.


There is no need to keep track of free ids. All you need to keep track of is the highest object id.
Every time you create a new object you increment it and assign the new object that id.
This is how Cool/Cold/Mush/Mux/MOO databases handle it
  • . That's how I do it in TeensyMud.
  • It's also how many RDBMSs do it. You should not run out of ids.
    For example: Most RDBMSs today use a 64-bit integer to hold them, which means even if you
    created 1000 new objects every second, it would take you 5 million years to run out.

    Reuse of recently used ids would actually be a problem in TeensyMud and Cold because we
    don't destroy references to the object id until the reference is accessed and it's discovered
    the id doesn't exist.

  • There is some Mush code that keeps track of free ids. I don't recall which Mush version though.
  • 24 Jun, 2013, Tyche wrote in the 12th comment:
    Votes: 0
    Here's some psuedo-code to handle reuse of ids:
    int highest_id;
    list<int> free_ids;

    destroy_object(id) {
    free_ids.push(id);
    }

    int create_object() {
    id = free_ids.pop();
    if (id == NULL)
    id = ++highest_id;
    return id;
    }


    Highest_id and free_list can be created at startup either while reading all your objects in, or
    if more appropriate to the design they could be saved and loaded separately upon shutdown or startup.
    24 Jun, 2013, Runter wrote in the 13th comment:
    Votes: 0
    Quote
    Yeah. I'm not overly concerned about efficiency, but it's not something I like to ignore without looking at alternatives either.


    My point is a comment on development in general. Build rope bridges. It's an analogy but, there's no reasons to carefully construct a suspension bridge when you don't even know the load. So build the fast and simple one that may be dangerous, but can be upgraded easily. The best thing you can learn now is how to encapsulate the logic such that changing the implementation becomes seamless. If you stop spending time considering and weighing efficiency concerns and just start developing software, you're going to have a lot more fun. And actually have a finished project relatively fast. Plus you won't waste your life, quite literally, implementing (or considering implementing patterns) that underutilize resources. My personal consideration process for going through application design is 1. Is it the easiest way for me to implement it? 2. Is it good enough today? If both answers are yes I find it a waste to think more about it until it's no longer true.

    Just some friendly advice from someone who has learned from mistakes.
    24 Jun, 2013, Rarva.Riendf wrote in the 14th comment:
    Votes: 0
    Runter is right, if it works, and it is not a problem already, you better concentrate on what does not work or prevent you to release the game. As he said you should also code in order to have another way to store your data easily as well, a basic coding practice in this case. Tomorrow you may want to put everything in a database and access it trhough sql requests.
    24 Jun, 2013, quixadhal wrote in the 15th comment:
    Votes: 0
    I agree with Tyche, there's no reason to keep track of free ID's. Just add or delete things from a mapping as you need, and keep track of the largest ID used so far. You'll have holes, but so what? Even if you're stuck on a 32-bit platform, it will take a while to fill up 2 billion integers (assuming you're using signed, 4 billion otherwise).

    And if that day comes, you can always write code to re-compress your ID range to regain your "lost" numbers. Of course, by that time you'll likely be on a 64-bit platform and not have to worry about it in this lifetime.
    24 Jun, 2013, Rarva.Riendf wrote in the 16th comment:
    Votes: 0
    quixadhal said:
    I agree with Tyche, there's no reason to keep track of free ID's. Just add or delete things from a mapping as you need, and keep track of the largest ID used so far. You'll have holes, but so what? Even if you're stuck on a 32-bit platform, it will take a while to fill up 2 billion integers (assuming you're using signed, 4 billion otherwise).


    That and having holes never been a problem even for old muds, where you allocated 1000 vnums for areas that would in the end use like 100 at max.
    24 Jun, 2013, quixadhal wrote in the 17th comment:
    Votes: 0
    Of course, if you're using mappings, there's no real reason to even use numbers as your keys.

    npc[3712]->currentHitPoints() -= 12;

    vs.

    npc["/DarkContinent/RedridgeMountains/OrcCave/Uruk"]->currentHitPoints() -= 12;

    Sure,the one using a string is more typing, but it also shows exactly what NPC you're talking about without having to go look up WTF "vnum 3712" is.
    24 Jun, 2013, Kline wrote in the 18th comment:
    Votes: 0
    quixadhal said:
    Of course, if you're using mappings, there's no real reason to even use numbers as your keys.

    npc[3712]->currentHitPoints() -= 12;

    vs.

    npc["/DarkContinent/RedridgeMountains/OrcCave/Uruk"]->currentHitPoints() -= 12;

    Sure,the one using a string is more typing, but it also shows exactly what NPC you're talking about without having to go look up WTF "vnum 3712" is.


    Glad to see someone raised this point. Why even muck about with numbers in the first place? The concept of vnums in my own server is simply a unique string. Then it's not only a unique identifier to an object/npc template but also descriptive, too, rather than "wtf is vnum 3712". There are no concerns about "zones" having to fall within a specified realm of numbers, or having to expand the usable range for a zone, etc. Each instance of an object in memory is then given a unique ID based on total object count and time, which is again just a string. Why the hangup over using numbers?
    25 Jun, 2013, Tyche wrote in the 19th comment:
    Votes: 0
    Of course the user/builder/programmer(script) shouldn't need object ids/vnums in most cases.
    However, confusing that issue with the internal code that looks up and maintains relationships between objects isn't very useful.
    0.0/19