MMORPG monster ID's
Author
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
A queue of dead monsters is pretty good to me. Although I wonder why you'd want to reuse 1, instead of using 4.
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?
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?
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.
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.
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.
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.
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.
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.
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.
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.
Author
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
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
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
