Comments on: A Technique for Applying Updates to Serialized Persistent Levels Sorry for the late response, I was expecting an automated email if there were any replies :) Yes, I was proposing reusing the array to point to the next in the free list, but you're right, it makes it harder to check whether an ID is free. A thought just occurred to me though - you could check this by testing whether the pointer points inside the bounds of the array. If it does, then it's not pointing to an object. Sorry for the late response, I was expecting an automated email if there were any replies :) Yes, I was proposing reusing the array to point to the next in the free list, but you’re right, it makes it harder to check whether an ID is free. A thought just occurred to me though – you could check this by testing whether the pointer points inside the bounds of the array. If it does, then it’s not pointing to an object.

]]>
By: James Podesta/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-775 James Podesta Tue, 15 Feb 2011 03:00:31 +0000 Some people prefer to serialize with explicit functions... stream.Serialize( myValue ) or stream.int32( myValue ) I don't advocate for any specific method. I learnt the '&' from Boost and, if the serialize function is kept clean and simple, it seems to work alright without too much confusion. Some people prefer to serialize with explicit functions…

stream.Serialize( myValue )

or

stream.int32( myValue )

I don’t advocate for any specific method. I learnt the ‘&’ from Boost and, if the serialize function is kept clean and simple, it seems to work alright without too much confusion.

]]>
By: Pal-Kristian Engstad/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-770 Pal-Kristian Engstad Mon, 14 Feb 2011 21:31:13 +0000 Thanks RedDog, though I didn't explain that I use the same array to resolve a UID into an Entity pointer. This is probably where the confusion is. Yes, you could do simple allocation/free in O(1) without extra memory using an unordered push_front/pop_front mechanism, but that is only part of what I am doing with the one array here. However, I have updated the code to use the unordered push/pop approach and move the entity resolve into a separate array, to avoid confusion. I think this is the most reliably efficient technique though it uses up more memory than the original single-array technique. Thanks RedDog, though I didn’t explain that I use the same array to resolve a UID into an Entity pointer. This is probably where the confusion is. Yes, you could do simple allocation/free in O(1) without extra memory using an unordered push_front/pop_front mechanism, but that is only part of what I am doing with the one array here.

However, I have updated the code to use the unordered push/pop approach and move the entity resolve into a separate array, to avoid confusion. I think this is the most reliably efficient technique though it uses up more memory than the original single-array technique.

]]>
By: Reddog/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-763 Reddog Mon, 14 Feb 2011 08:26:56 +0000 ...editted response... To elaborate, the allocation algorithm is O(1) allocation UNTIL you have used up all your free UIDs in a single session, then it degenerates to an O(N). I did indeed use the O(N) syntax incorrectly. It will generally be a single iteration lookup, even if it can't claim an O(1) label due to worst case situations. I'm still struggling to understand the linked list approach. I don't see how you make a linked list that you can add and remove from in O(1) time without it being a double linked list, which as the DATA + 2 node ptrs. I'm obviously missing something. (edit - the bit I was missing is that you aren't taking into account that Entity Resolve is done with the same table). …editted response…

To elaborate, the allocation algorithm is O(1) allocation UNTIL you have used up all your free UIDs in a single session, then it degenerates to an O(N). I did indeed use the O(N) syntax incorrectly. It will generally be a single iteration lookup, even if it can’t claim an O(1) label due to worst case situations.

I’m still struggling to understand the linked list approach. I don’t see how you make a linked list that you can add and remove from in O(1) time without it being a double linked list, which as the DATA + 2 node ptrs. I’m obviously missing something. (edit – the bit I was missing is that you aren’t taking into account that Entity Resolve is done with the same table).

]]>
By: Glenn Watson/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-758 Glenn Watson Mon, 14 Feb 2011 02:20:57 +0000 My entity types are defined in an XML, so you could add new types by updating the XML and scripts give you a fair bit off flexibility on what a new type can do. To add new "classes" of objects that have extra data needing to be serialized, that requires a code update currently. If you wanted to go fully update-only you could just drive all that with scripts and support serialization from script code. I don't currently. From the tool chain, I modified Tiled map editor to generate UIDs. If you wanted a streaming game you need to add a UID extension per level or chunk so they are universally unique. My entity types are defined in an XML, so you could add new types by updating the XML and scripts give you a fair bit off flexibility on what a new type can do. To add new “classes” of objects that have extra data needing to be serialized, that requires a code update currently. If you wanted to go fully update-only you could just drive all that with scripts and support serialization from script code. I don’t currently.

From the tool chain, I modified Tiled map editor to generate UIDs. If you wanted a streaming game you need to add a UID extension per level or chunk so they are universally unique.

]]>
By: jamie/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-756 jamie Mon, 14 Feb 2011 02:10:50 +0000 Love it. :-) Some observations: If you only have 8192 UIDs then you have three extra bits to store extra info in. Just mask them off before looking them up. Rather than cycle thru looking for a free dynamic slot, keep a free list of slots: the "free list" is the first free UID. In the UID table, instead of a pointer at this address, there actually the next UID instead. If need be, modify the UID so that it cant possibly be a pointer (e.g. its top bit is set, or if you are in kernel land, its bottom bit is clear). Love it. :-)

Some observations:

If you only have 8192 UIDs then you have three extra bits to store extra info in. Just mask them off before looking them up.

Rather than cycle thru looking for a free dynamic slot, keep a free list of slots: the “free list” is the first free UID. In the UID table, instead of a pointer at this address, there actually the next UID instead. If need be, modify the UID so that it cant possibly be a pointer (e.g. its top bit is set, or if you are in kernel land, its bottom bit is clear).

]]>
By: Glenn Watson/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-754 Glenn Watson Mon, 14 Feb 2011 01:56:16 +0000 I think the big difference with an MMO is that you wouldn't have Type 3 entities to deal with... dynamically allocated entities. Any time the MMO is taken offline for updates, all temporary entities would just be cleared. So you're down to just updating all known static entities, which, since they are permanently allocated GUIDs you could just update via database queries. In a sense, updating a massive MMO becomes a simpler problem then updating a "save anytime" single player RPG. For instance, if you summon a bunch of skeletons to fight for you, you don't expect those skeletons to still be around after MMO downtime. However, if you are on your iPad, and exit to answer a phone call, when you return you expect to continue exactly from where you left it. I think the big difference with an MMO is that you wouldn’t have Type 3 entities to deal with… dynamically allocated entities. Any time the MMO is taken offline for updates, all temporary entities would just be cleared. So you’re down to just updating all known static entities, which, since they are permanently allocated GUIDs you could just update via database queries. In a sense, updating a massive MMO becomes a simpler problem then updating a “save anytime” single player RPG.

For instance, if you summon a bunch of skeletons to fight for you, you don’t expect those skeletons to still be around after MMO downtime. However, if you are on your iPad, and exit to answer a phone call, when you return you expect to continue exactly from where you left it.

]]>
By: Tweets that mention A Technique for Applying Updates to Serialized Persistent Levels » #AltDevBlogADay -- Topsy.com/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-752 Tweets that mention A Technique for Applying Updates to Serialized Persistent Levels » #AltDevBlogADay -- Topsy.com Mon, 14 Feb 2011 01:39:06 +0000 [...]

]]>
By: Glenn Watson/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-751 Glenn Watson Mon, 14 Feb 2011 01:33:44 +0000 I've never worked on an MMO (would love to). I imagine MMOs would generally keep status of all objects in a global database. So they can just update the global database during downtime and the new data will propogate to the player next time he is online. If you want to use up extra memory you can certainly reduce the allocation time to O(1) by using two arrays for lookup, but since the system I outlined will generally be O(1) to allocate and is always O(1) time to free, it didn't seem worth the extra memory. I'm not sure what technique your referring to that wouldn't use any extra ram. At the very least, a linked list approach would need a node ptr, and to get an (1) removal you would need 2 node ptrs. I’ve never worked on an MMO (would love to). I imagine MMOs would generally keep status of all objects in a global database. So they can just update the global database during downtime and the new data will propogate to the player next time he is online.

If you want to use up extra memory you can certainly reduce the allocation time to O(1) by using two arrays for lookup, but since the system I outlined will generally be O(1) to allocate and is always O(1) time to free, it didn’t seem worth the extra memory. I’m not sure what technique your referring to that wouldn’t use any extra ram. At the very least, a linked list approach would need a node ptr, and to get an (1) removal you would need 2 node ptrs.

]]>
By: Ben Wooller/2011/02/13/a-technique-for-applying-updates-to-serialized-persistent-levels/#comment-743 Ben Wooller Sun, 13 Feb 2011 12:58:12 +0000