• Advertisement
Sign in to follow this  

MMORPG monster ID's

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to make the game engine and I have a few concepts I don't quite get. It's more like, I know a solution, but I don't think it is the optimal one. What I want is an "ID Handler". We all know in am MMORPG, monsters spawn and die all the time. We also know each monster is probably represented by some kind of ID in our game server. Now then thing is this. For example: I make 3 monsters with IDs: 1, 2, and 3 Now, If I spawn another monster, obviously the ID would be 4. However!! If monster 1 dies. There is only monster 2 and monster 3 left. NOW! If I make a new monster, I should assign the ID of the new monster "1" instead of "4" right? How do I know that "1" is missing in the most efficient way? Currently, I store my objects in a hash map. I thought of making a queue of dead monsters. But this way seems tedious and messy. I don't know if this is the professional way to do it. Does anyone know the "correct" way of doing this? Thanks in Advance! Thomas

Share this post


Link to post
Share on other sites
Advertisement
A queue of dead monsters is pretty good to me. Although I wonder why you'd want to reuse 1, instead of using 4.

Share this post


Link to post
Share on other sites
There are a few correct ways. I'd be interested in hearing how other people handle it.

The quick, dirty, ugly way is to just use an unsigned long. If you create a monster every second, it'll take over a month before you loop back to 0. You could do a quick check before you instantiate the new object to see if any old objects have that ID. Most of the time, the answer will be no.

You could also use a queue as you described, which is an elegant but slightly more expensive solution. You could treat it as a circular buffer to speed it up a little, but then you'd have to deal with the possibility of overflowing it.

You could make the ID more of an encoding, in order to make it easier to ensure uniqueness. Maybe make monster IDs unique to the zone they're in instead of globally. Or eve unique to their type and the zone. So it'd be the 3rd Swamp Monster in SwampLand. That way, you'd just need to check SwampLand's array of SwampMonsters for uniqueness. This approach has some overhead, though, so it'd only be a good idea if your world was quite large.

I wrote a particle engine once, and I had decided I wanted to keep the particle numbers as low as possible (can't remember why anymore), so I stored the IDs of dead particles in a priority queue. I don't really recommend it, but it was sort of interesting.

There are probably other approaches, too. Anybody?

Share this post


Link to post
Share on other sites
Well, you could iterate the list of monsters and check for the lowest available ID to use. Start by checking for ID 1. If it is found. Check for 2. And so on until the requested ID is not found in the list. This can be quite a heavy task especially if the monster list contains lots of entries.

Another things you could do is just give every newly spawned monster a unique ID. Just have a counter that increases everytime a monster spawns. The downside of this is that the counter will eventually reach the highest possible number allowed by the datatype of the counter. If you use a 64bit counter though it will take a very, very long time to reach that point.

A queue sounds like a good choice to me though, if you really want to reuse IDs.

Share this post


Link to post
Share on other sites
I wouldn't re-use free numbers. Using the typical natural word size of 32 bit (unsigned), then spawing every second a new monster will overflow the counter after 136 years! (Using a 64 bit counter here brings no advantage but slows down computation unnecessarily.)

However, there is another aspect. Allocating and freeing memory often will slow down. You may consider to re-use the monster instances (and hence re-use the IDs stored with them automatically as well). For that purpose a list of "unused" monsters will work fine. A new ID will then be determined only if the list is empty, and a new monster instance is to be allocated.

Share this post


Link to post
Share on other sites
I would avoid reusing IDs, simply because you don't need to, and it can lead to really annoying bugs. (if some effect refers to a monster ID that dies, and you don't clean it up, it now refers to a completely different critter)

Using GUIDs or or int64s int128s that simply increment is a decent solution.

At 1000000 (1 million) players and 100 monsters spawned every 1/100th of a second that is 33 bits/second of monsters (2^33), or 58 bits/year (2^58) of monsters.

That leaves ~64 years if you use an int64, or a many trillion years if you use an int128.

Now every monster-type thing that ever existed has it's own unique ID. Spells that somehow refer to no-longer-existing monsters can generate error messages or deal with it in a sensable way.

Share this post


Link to post
Share on other sites
Having a local (zone) ID generated per entity is one approach - but you may need to consider a larger internal ID to allow for intra-zone interactions, prefixing a zone ID onto the entity ID, and issuing a renomenclature if the entity moves into another juristiction. I've used 16 bit base ID's because I'm lazy and don't want to type lots. ;-) Anyway, the design I have is vaguely similar to this:

Example: We have 2 zones, Forest and Town: ID's 0x0001 and 0x0002.

'Gunther the Orc' is spawned in the Forest, and given an ID 0x00010001.

He moves around there with his local ID - if he approaches the town, the town zone is issued an event announcing his presence, and ID. Any events to do with him can immediately be passed on for resolution by the other zone server, as his ID is non-local.

If he actually moves INTO the town a handover event is issued - data is serialised and transferred from zoneserver to zoneserver (or simply flat copied if using 'virtual' zones within a process), and the new entity is created from that data and given a NEW ID: 0x00020001. The new entity is introduced (remember its status has been transferred so is apparently unchanged) to the original zone.

This is robust for identification of entities across boundaries, but you still don't want to do too much transferral; there's inevitably an overhead in the serialisation and selection of a new ID, even given the smaller range demanded by localising ID generation.

We allocate ID's in two ways, from different ranges. Temporary IDs (for short-lived, mostly individual entities like fire walls, campfires, etc) are drawn from a circular buffer at the high end of the ID range. Longer-lived IDs are drawn from a range map (like a block allocation scheme) at the lower end of the ID scheme. Drawing long-lived entities from the circular section of the range is not a good idea, since you're more likely to run into overflow with long-lived entities, which can trigger a very slow lookup process.

The range map holds start point and runs of free allocations. Often we're spawning more than one entity as a result of an event (and so we can allocate ID's by block). We look for the first block we find with sufficient allocations in it as our best solution. Optionally, we can search the 'fragmented' space, but this isn't a great idea. On release, entries are made back into the range map, producing a fragmented table. Since the entities may be referred to from elsewhere, we can't easily implement a sliding block mechanism (as you might for a memory allocation table). We're left with a couple of mechanisms that help - firstly, if you spawn something in a group, chances are it'll move on or get destroyed in a group - if you don't deallocate the ID's immediately but instead wait for the release of the entire group you save yourself a big headache. Secondly, and perhaps more reliably, we operate a housekeeping process that spends a little time defragging the allocation table.

Hope this helps.


Share this post


Link to post
Share on other sites
thx u guys really helped me

now i just finished implementing my solution... if ur interested... here is how it works...


i have a small array of "ready made" monsters that are being reused all the time. as haegarr said, making new instances will slow down my server... so i will reuse the instances... and in each instance,i have a new variable called "mAlive"... this tells us if the monster is actually present or not in the game world...

whenever i make a monster, one of those "mAlive = false" instances will become "mAlive = true"... and then a monsterID (which basically just increments, as all of u agree with) will be assigned to this instance..., i never reuse the old ID again, since most of u guys said it was pointless to do so...

thanks for all the help... hope this will run efficiently on a server

Share this post


Link to post
Share on other sites
One other point with re-using identities: It's unlikely your servers will stay up for long enough to clean out an int64. You can always clear out the active monsters and start over when you restart the game server, which should realistically give you all the time you need.

Share this post


Link to post
Share on other sites
Quote:
Original post by eraser_iresa
i have a small array of "ready made" monsters that are being reused all the time. as haegarr said, making new instances will slow down my server... so i will reuse the instances... and in each instance,i have a new variable called "mAlive"... this tells us if the monster is actually present or not in the game world...

whenever i make a monster, one of those "mAlive = false" instances will become "mAlive = true"...


I suggest that you use a pool allocator instead. This way, you gain all the benefits of memory reuse without the disadvantages of multiple responsibility in a given class.

Share this post


Link to post
Share on other sites
Quote:
Original post by haegarr
I wouldn't re-use free numbers. Using the typical natural word size of 32 bit (unsigned), then spawing every second a new monster will overflow the counter after 136 years!


Then that's a problem. Say you have a codebase of > 1 million lines of code some ~150 years into the future, and a userbase of several thousand users that are playing daily. Then, all of a sudden, because you can't remember that you used a natural word size of 32 bit for the ID counter, the monsters start behaving weirdly, or, in the worst possible scenario, the server crashes for no apparent reason in the middle of the night during peak hour! And that's not all; What if the main coder (I.E you) is dead or in a retirement home? Then your family is going to have a problem on their hands because the family business goes bankrupt because the current main coder can't figure out what on earth is wrong.

Short hand version: Use a queue.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Some games have a fixed number of monsters tied to a spawn area. When the monster dies, a timer starts and after the timeout it gets respawn. This ensures that the number of monsters is constant and that each monster has its assinged area. Camping can be defeated by respawning it in an area instead of a fixed point. The monster ids can be fix, even assigned during map construction. The monster states are: alive inactive, alive active, dead. The respawn delay is the time the monster spends in dead state.

Viktor

Share this post


Link to post
Share on other sites
Quote:

Quote:
Original post by haegarr
I wouldn't re-use free numbers. Using the typical natural word size of 32 bit (unsigned), then spawing every second a new monster will overflow the counter after 136 years!


Then that's a problem. Say you have a codebase of > 1 million lines of code some ~150 years into the future, and a userbase of several thousand users that are playing daily. Then, all of a sudden, because you can't remember that you used a natural word size of 32 bit for the ID counter, the monsters start behaving weirdly, or, in the worst possible scenario, the server crashes for no apparent reason in the middle of the night during peak hour! And that's not all; What if the main coder (I.E you) is dead or in a retirement home? Then your family is going to have a problem on their hands because the family business goes bankrupt because the current main coder can't figure out what on earth is wrong.

Short hand version: Use a queue.


ROFL. I have never heard of a system that has stayed up for more then 6 months, let alone 150 years. PARTICULARLY a game server, its just not feasable. with the evolution of games the rate they are, you couldent possiably bank on that game 10 years after its creation, yet alone 20... and god help me not 150. And I dont think a family business can run on 1 game produced even 20 years beforehand....

Edit: not to mention, if 1 crash during peak hour once in 150 years is enough to make a company bankrupt, microsoft, sony, toshiba, dell, and practicaly every software company in existance would be declaring bankruptcy on a bi-second bases.

Share this post


Link to post
Share on other sites
True - you're going to want the downtime just for maintenance now and then, or the implementation of revised subsystems.

Share this post


Link to post
Share on other sites
Quote:
Original post by Afr0m@n
Quote:
Original post by haegarr
I wouldn't re-use free numbers. Using the typical natural word size of 32 bit (unsigned), then spawing every second a new monster will overflow the counter after 136 years!


Then that's a problem. Say you have a codebase of > 1 million lines of code some ~150 years into the future, and a userbase of several thousand users that are playing daily. Then, all of a sudden, because you can't remember that you used a natural word size of 32 bit for the ID counter, the monsters start behaving weirdly, or, in the worst possible scenario, the server crashes for no apparent reason in the middle of the night during peak hour! And that's not all; What if the main coder (I.E you) is dead or in a retirement home? Then your family is going to have a problem on their hands because the family business goes bankrupt because the current main coder can't figure out what on earth is wrong.

Short hand version: Use a queue.
There's an advantage there: the monster IDs would start back at 0 after a restart, assuming spawned monsters are not persistant (saved). :)

Share this post


Link to post
Share on other sites
The best way to me to reuse ID's would be to have a list of unused ID's. If you ever need an ID, pull the first one off the list and if the list is empty, create a new id.

When you remove a monster, just push the ID onto the free list.

Share this post


Link to post
Share on other sites
The answer lies in databases and how to properly record data. Tried and true method is to autoincrement. 1..2..3..4 ... Wolf monster 2 dies, next monster is 5. Now you can query the data in the future, how did the monster die, when did it die, how many Wolf monsters has this person killed (query the history) and how does that make Wolf-Hunter NPCs feel? etc.

You increment IDs so that they are unique. This is how it is done.

Share this post


Link to post
Share on other sites
Really sugjest you don't reuse ID's, for reasons that would be elaborated on below. Even if you waste some ID's, using more than you need is better than running into problems by using too few. Personally I use a direct hash, an array that holds the objects, and the ID % array size is the index that the entity holds. The ID's are just incremented, and if the spot is filled, it just skips the ID entirely until it finds an empty one. It expands the array once it reaches a certain density [80% full for me], and re-inserts everything back into the listing.

REASONS TO USE UNIQUE IDS INSTEAD OF REUSED IDS [these are actually problems that I've personally had, and were the two biggest problems I faced with this issue]

Delayed messages destined to an object that has just died, being sent to an object that has just spawned.

AI interactions causing pursuit or whatever, for an object that has just been deleted being carried over to an object that has just been created.

Share this post


Link to post
Share on other sites
If you really want to reuse the IDs. Then this way probably is the best way i can think of without using extra memory. Have two data containers(queue) that will store one alive monsters id and the other data container will dead monster id. When the monster #1 dies, it's ID goes to dead mosnter container. Say you have #2 and #3 monster alive and you don't want to have #4 monster spawned. Then what you can do is, take the ID from dead monster container and assign it to the new spawing monster. Voila! Your new monster is using ID #1.

Share this post


Link to post
Share on other sites
Quote:
Original post by busytree
If you really want to reuse the IDs. Then this way probably is the best way i can think of without using extra memory. Have two data containers(queue) that will store one alive monsters id and the other data container will dead monster id. When the monster #1 dies, it's ID goes to dead mosnter container. Say you have #2 and #3 monster alive and you don't want to have #4 monster spawned. Then what you can do is, take the ID from dead monster container and assign it to the new spawing monster. Voila! Your new monster is using ID #1.


To make this even better, one can put all monster objects into an array (vector) and use a free list that contains all the free (dead) objects. Delayed message problems can be solved with timestamping every message and checking the action's timestamp against the monster's creation time. The additional benefit is that the approach requires no memory allocation/deallocation or any database operations, so the the server can run for extended time without maintenace downtime or the need to add more storage because of a growing state file or database.

Viktor

Share this post


Link to post
Share on other sites
depends how many you want to ID, and in what range (16 bit number? 8 bit number? 32 bit number?).

Reusing IDs can be bad, you'll need timestamping to make sure you don't receive a delayed message for a dead monster.

Just store the dead ones in a list, the alive ones in another list, and pick the ones in the dead list. If the list is empty, it means that the alive list is a continuous list of entites and there is no gaps, so you can pick IDs outside the range (so you need to keep track of ID bounds in use).

But frankly, this is not really a critical problem. You can just iterate the list, see if a number is used or not, use a hashtable, ... The time it will take to create the entity itself should be much greater than the time to find a usable ID anyway.

Share this post


Link to post
Share on other sites
How about just marking the monster as 'dead' in the list. When a time has elapsed then reset the monster. Maybe have a status member variable in the monster class.


enum MonsterStatus
{
STATUS_ALIVE,
STATUS_SPAWNING,
STATUS_DEAD,
};


Share this post


Link to post
Share on other sites
I'd like to jump on the 'don't reuse' bandwagon too, if there's still space. The only time you should do that is when you wrap around your address space (and, imo, you should use something nice and fast to hash on like uint32 and prepare for wrapping – either a good way to avoid it or a way of dealing with it gracefully).

My suggestion for that would be something like Winterdyne's defragger running periodically and reallocating IDs to old, long-lived objects to free up contiguous blocks. When you get a contiguous block of say 1000 IDs or more, you start addressing within that block for the next 1000 creations. If you run your defragger relatively frequently (like, once a week or more often, so not that frequently!) you should never overflow unless the number of objects in your game approaches MAX_INT, in which case you've probably hit all sorts of other problems already.

You can also help things by having a transient object pool for things that are guaranteed to live less than (say) a minute. (Particles and other special effects are the prime candidates for this, but bombs, projectiles and even some monsters might go there too.) For those objects you can just loop (even on a uint16 maybe) and assume that by the time you overflow the previous object with that ID has died. That keeps all the crap out of the main, properly managed object pool and will make the defragger's job a lot easier.

Share this post


Link to post
Share on other sites
In my opinion the server should only really track interactive objects - there's no point in allocating an ID to a transient particle system (like an explosion), or non-interactive beasties. Basically, you only *really* need to track things that have bearing on more than one entity (player, typically) or are persistent. Anything else can be handled as an event directed towards or triggered by the relevant entity.

Say you have a woodland zone - you may have a number of things happen that although you want to inform the client of, have no bearing or interaction as far as the game mechanics are concerned - an example might be a 'falling leaf' particle system, that occasionally drops a few leaves from trees.

I'd trigger the 'falling leaves' as an event on a tree, now and then. When passed to a player, their client spawns and drops the leaf particles. The server doesn't need to know about them. If another player enters the area after the event has fired they simply don't see the leaves drop - it's not game critical so it doesn't matter.

Tracked projectiles are actually a pretty bad idea because of lag constraints - by short lived I mean things like individual mobs, or potentially (if you want to make a feature of it) relatively static 'clue' objects for recent history like bullet holes and blood splats. Long-lived entities are more things like resource generators (mining points, harvestable trees) and interactive artefacts or components thereof (scalable cliff walls, doors, windows).

Share this post


Link to post
Share on other sites
I was working at a place that ran a small mmorpg before. So I was speaking to an ex coworker the other day, we were just chatting about who was doing what now since I knew him for a few year. Well, he mentionned that the 32 bit ID looped around. The shit really hit the fan so to speak. What's worse, the server didn't crash, it just kept going and saving the game state at set time but weird things started cropping up, like invicible monsters etc.

This just confirms something that I already knew in mmorpg. Don't take ANY chances, don't make assumptions of it'll be good enough. Put safeguards that make the server shut down at the very least so that you don't have to rollback 1 week and have a lynch mob of very angry customers try to find out where your home office is =).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement