Arcen Games

Other => Game Development => Topic started by: RogueDeus on September 20, 2011, 04:05:29 PM

Title: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 20, 2011, 04:05:29 PM
Me again. Finely have reason to bother you!

I have one of those pesky Unity questions I warned you about... Hope you don't mind.


Q: Since there is very little built in support for saving data in the Unity library, I was wondering how you implemented serialization in your games?
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 20, 2011, 04:21:38 PM
Completely custom.  Our serialization is based on custom input and output encoding buffers that write ascii data, which is then compressed when need be.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 20, 2011, 06:41:32 PM
Completely custom.  Our serialization is based on custom input and output encoding buffers that write ascii data, which is then compressed when need be.

How often do you write it to disk?
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 20, 2011, 06:43:42 PM
It really varies, and depends on what game you're talking about.  If you mean AI War, it's as often as every minute, depending on how autosave is set up.  With Tidalis, it's whenever data changes that we persist.  With AVWW, it's in thousands of smaller files that get written (and read, for that matter) only as their data changes, but with a max amount of data allowed to be saved at any given time.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 20, 2011, 06:49:13 PM
It really varies, and depends on what game you're talking about.  If you mean AI War, it's as often as every minute, depending on how autosave is set up.  With Tidalis, it's whenever data changes that we persist.  With AVWW, it's in thousands of smaller files that get written (and read, for that matter) only as their data changes, but with a max amount of data allowed to be saved at any given time.

Thanks for the swift replies.

So in AVWW when you enter an area with persisted data, you check to see if serialization has already occurred for that data, and if so you retrieve it?

I am wondering about serialization mostly because it is the most mysterious part of coding for me.  (at the moment)
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 20, 2011, 06:51:32 PM
Thanks for the swift replies.

Sure thing.

So in AVWW when you enter an area with persisted data, you check to see if serialization has already occurred for that data, and if so you retrieve it?

Pretty much.  And if it's not there, then we generate it at that time, and then flag it to be saved when the program feels like it has time to.

I am wondering about serialization mostly because it is the most mysterious part of coding for me.

There's nothing that magic about it; it's like writing notes to yourself on paper, and then remembering where the notes are.  You only look at the notes when you need the info they have, and you only write to the notes when something actually changes and you don't want to keep the info in your head anymore (for fear of forgetting, or because you want to think about something else now).
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 20, 2011, 07:01:18 PM
So in AVWW when you enter an area with persisted data, you check to see if serialization has already occurred for that data, and if so you retrieve it?

Pretty much.  And if it's not there, then we generate it at that time, and then flag it to be saved when the program feels like it has time to.

Do you cache it in an array and manipulate it there till its written?


Most of the mystery for me is in when where and how to (de)serialize stuff. The whole idea of starting a game, as a movement of data, I get. But restoring the movement from a serialized state often turns my brain inside out for some odd reason.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 20, 2011, 07:07:37 PM
We don't use an array, no.  Usually.  The answer actually varies a bit.

If we have things that no longer need to be in memory but which need to be written to disk "at some point soon before they are dropped from memory," then we'll stick that in a generic list (in C# parlance).  Then the game can write from that list at its leisure, and remove the items as it goes.  That's very easy to throttle.

For other things, when determining what to write, it's usually just a bool on the object.  Then something else checks the bools on all the objects every so often, and writes the ones to disk that are flagged.  This also is easy to throttle if you have to, although slightly harder.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 20, 2011, 07:13:36 PM
We don't use an array, no.  Usually.  The answer actually varies a bit.

If we have things that no longer need to be in memory but which need to be written to disk "at some point soon before they are dropped from memory," then we'll stick that in a generic list (in C# parlance).  Then the game can write from that list at its leisure, and remove the items as it goes.  That's very easy to throttle.

For other things, when determining what to write, it's usually just a bool on the object.  Then something else checks the bools on all the objects every so often, and writes the ones to disk that are flagged.  This also is easy to throttle if you have to, although slightly harder.

By generic I guess you mean by 'type'? If so that is one of the other mysterious parts of coding for me. I have not quite digested generic type coding yet... :( Or reflection for that matter. (Though I want too!!)

Thanks for the info. As always you are great at feedback!
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 20, 2011, 07:16:48 PM
Generics have a specific meaning in C#, which is different from type.  It's basically just a way of having a single "generic class" that inserts other types in place of the generic notation to make it as efficient as if you coded out the generic class once for each specific instance of the class.  So you don't get boxing and unboxing, etc.  And you don't need a ListOfInts class, or a ListOfGameObjects class.  You just have List<int> and List<GameObject> and that's that.  Much better than in the old days before generics.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 20, 2011, 07:27:17 PM
Generics have a specific meaning in C#, which is different from type.  It's basically just a way of having a single "generic class" that inserts other types in place of the generic notation to make it as efficient as if you coded out the generic class once for each specific instance of the class.  So you don't get boxing and unboxing, etc.  And you don't need a ListOfInts class, or a ListOfGameObjects class.  You just have List<int> and List<GameObject> and that's that.  Much better than in the old days before generics.

I suppose I am showing my ignorance. :) FYI , I only just recently got the idea of the need for Delegates... :p


Anyway, the way you are handling serialization is much how I would like too, but it seems I have a lot more learning to do.

My current game design will only require the main PC and a few global variables to be serialized so it wont be to difficult. I am going to use a custom serializer just to help myself learn though.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 20, 2011, 07:29:26 PM
Cool stuff.  It's a long road, but if you enjoy the process that makes it much easier.  And I think delegates are overrated, by the way.  We use them, but minimally.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 20, 2011, 07:34:17 PM
Cool stuff.  It's a long road, but if you enjoy the process that makes it much easier.  And I think delegates are overrated, by the way.  We use them, but minimally.

I have not found anything more fun to learn.

Till next time.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 29, 2011, 01:15:12 PM
I just tackled Enums, Delegates, and Generic Class/Method/Delegates this week and I find myself unsure why I thought them so difficult before hand. They are actually quite intuitive once you understand them.

Earlier in this thread I was a bit confused by how you where talking about Generics an assumed you where using some custom Generic Classing to handle custom lists, but I suppose you merely meant that you like using the Generic Collections introduced in C# 2.0? I had actually been using them in my practicing and never thought about it that way...

Delegates are an interesting way to add method calls to collections, or even clean up some extremely long method calls with simple place holders, but otherwise I can see why you find them overrated. And Enums strike me as a convenient way to simplify the creation of constants. Only, from what I have read, C# creates a lot of temporary code when using Enums and slows things down when iterating through them. So calling them in long loops may end up seriously effecting performance.

You know, the more I look at these short cuts (like Enums and Delegates) the more I realize why code is getting bigger and slower... Its faster (easier) to write, but takes longer to process. I suppose that is the trade off really. Otherwise we would still be writing in machine code! :p

I also played a lot with Unity GUI. It is remarkably simple to use, and will make prototyping mechanics a lot less time consuming.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 29, 2011, 01:17:13 PM
You know, the more I look at these short cuts (like Enums and Delegates) the more I realize why code is getting bigger and slower... Its faster (easier) to write, but takes longer to process. I suppose that is the trade off really. Otherwise we would still be writing in machine code! :p

Enums add no extra processing whatsoever if you use them right.  They are just like CONSTs.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 29, 2011, 01:33:41 PM
You know, the more I look at these short cuts (like Enums and Delegates) the more I realize why code is getting bigger and slower... Its faster (easier) to write, but takes longer to process. I suppose that is the trade off really. Otherwise we would still be writing in machine code! :p

Enums add no extra processing whatsoever if you use them right.  They are just like CONSTs.

Maybe I am misunderstanding this then?

http://stackoverflow.com/questions/105372/c-how-to-enumerate-an-enum

In the comments on the answer there is this:
Quote
52    
   
Enumerating an enum with 52 values 100000 times: 3884ms Enumerating an int[] with 52 values 100000 times: 99ms yes, far slower than an array - but still fast unless you have 51 million enum values ;) – TheSoftwareJedi Oct 15 '08 at 1:41

If I understand this correctly, he is saying that a foreach loop using a list of Enums is slower then using an array. Not exactly game breakingly slow, just slower.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 29, 2011, 02:18:06 PM
I apologize if I am being argumentative. Just trying to make sure I understand which is correct.

If there is no performance hit with liberal use of Enums then I will use them as often as I can. But if there is, I will use them only when a more complex solution is less agreeable.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 29, 2011, 02:28:20 PM
You've have to check the specs, and which version of .NET is in question, and so on.  But unless there's a lot of boxing/unboxing going on, there should be no reason.

And actually: with a foreach loop, which is horribly inefficient to begin with, there would be boxing.  So I'm not surprised at that.  But that's a problem with foreach, not with using an enum.  Use for, while, and do while -- never use foreach.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 29, 2011, 02:30:13 PM
You've have to check the specs, and which version of .NET is in question, and so on.  But unless there's a lot of boxing/unboxing going on, there should be no reason.

And actually: with a foreach loop, which is horribly inefficient to begin with, there would be boxing.  So I'm not surprised at that.  But that's a problem with foreach, not with using an enum.  Use for, while, and do while -- never use foreach.

Thanks I will remember that!
Title: Re: How are you handling Serialization with Unity3D?
Post by: Hearteater on September 29, 2011, 02:31:48 PM
I'd like to point out is that the comment you quoted RogueDeus is almost 3 years old.  It may not be reflective of C#'s current performance.

For what it is worth, my general rule is to get clean, maintainable code working and come back with a better solution later if that turns out to be your bottleneck.  Chances are you'll have a better understanding of how to do good optimizations later anyway.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 29, 2011, 02:35:19 PM
I'd like to point out is that the comment you quoted RogueDeus is almost 3 years old.  It may not be reflective of C#'s current performance.

For what it is worth, my general rule is to get clean, maintainable code working and come back with a better solution later if that turns out to be your bottleneck.  Chances are you'll have a better understanding of how to do good optimizations later anyway.

Good point. I often forget to check that... It is so easy to get overloaded with info on that site that I only grab the gist of something before moving to the next most relevant tidbit.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 30, 2011, 04:23:20 PM
I am paying around with Dictionaries to create a local variable system so I can store/retrieve data on objects that have the script component available, and I was wondering about anyone's thoughts on its feasibility.

Essentially, when run, the script creates up to four Dictionaries Int, Float, String, and Object types, with string Keys. (I may change that to an enum). This is primarily to save serializable data for that whole (data, manipulator, projector) thing I talked about.

I tried using the dictionaries via a generic methods but must be doing something wrong, so I created specific methods for each. (Clipped the extra get/set's to shorten it)

Code: [Select]
public class LocalVariables : MonoBehaviour
{
private Dictionary<string, int> localIntDictionary;
private Dictionary<string, float> localFloatDictionary;
private Dictionary<string, string> localStringDictionary;
private Dictionary<string, object> localObjectDictionary;

[HideInInspector]
public bool disableLocalIntegers, disableLocalFloats, disableLocalStrings, disableLocalObjects;




// Use this for initialization
void Start ()
{
if(!disableLocalIntegers)
{
localIntDictionary = new Dictionary<string, int>();
}
if(!disableLocalFloats)
{
localFloatDictionary = new Dictionary<string, float>();
}
if(!disableLocalStrings)
{
localStringDictionary = new Dictionary<string, string>();
}
if(!disableLocalObjects)
{
localObjectDictionary = new Dictionary<string, object>();
}
}

void Update()
{

}


#region Base Getters/Setters
private void NoDictionary(string dictionary, string varName)
{
Debug.LogError(gameObject.name + " - Has no " + dictionary
+ " dictionary!! To save/get: " + varName);
Debug.Break(); //Stop the game.
}

public int GetLocalInt(string varName)
{
if(disableLocalIntegers || localIntDictionary == null)
NoDictionary("Local Integer", varName);

return localIntDictionary[varName];
}

public void SetLocalInt(string varName, int value)
{
if(disableLocalIntegers || localIntDictionary == null)
NoDictionary("Local Integer", varName);

localIntDictionary.Add(varName, value);
}

public float GetLocalFloat(string varName)
{
if(disableLocalFloats || localFloatDictionary == null)
NoDictionary("Local Float", varName);

return localFloatDictionary[varName];
}

public void SetLocalFloat(string varName, float value)
{
if(disableLocalFloats || localFloatDictionary == null)
NoDictionary("Local Float", varName);

localFloatDictionary.Add(varName, value);
}

public string GetLocalString(string varName)
{
if(disableLocalStrings || localStringDictionary == null)
NoDictionary("Local String", varName);

return localStringDictionary[varName];
}

public void SetLocalString(string varName, string value)
{
if(disableLocalStrings || localStringDictionary == null)
NoDictionary("Local String", varName);

localStringDictionary.Add(varName, value);
}

public object GetLocalObject(string varName)
{
if(disableLocalObjects || localObjectDictionary == null)
NoDictionary("Local Object", varName);

return localObjectDictionary[varName];
}

public void SetLocalObject(string varName, object obj)
{
if(disableLocalObjects || localObjectDictionary == null)
NoDictionary("Local Object", varName);

localObjectDictionary.Add(varName, obj);
}
#endregion

}

I think I will remove the MonoBehaviour and use it as a lib class and not a script component.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 30, 2011, 04:27:38 PM
I think you're over-generalizing.  Also, indexing by strings is incredibly slower than by enums.  String comparisons are wicked slower than enum comparisons, and the comparison time varies by the length of the string.


You don't need some fancy data structure to store data in so that you can later serialize it.  All you need is just regular variables.  Then when it comes time to serialize, your serialization code needs to automatically write those variables.  Look at how microsoft ISerializable classes tend to look.  You don't have to use their serialization method (in fact I recommend not), but their general structure is fine.  What you've got in the code you posted is just going to add slowdown and memory bloat -- take out the middle man.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 30, 2011, 05:42:42 PM
I think you're over-generalizing.  Also, indexing by strings is incredibly slower than by enums.  String comparisons are wicked slower than enum comparisons, and the comparison time varies by the length of the string.

Thanks, I had not considered searching for speed deference in key types.

You don't need some fancy data structure to store data in so that you can later serialize it.  All you need is just regular variables.  Then when it comes time to serialize, your serialization code needs to automatically write those variables.  Look at how microsoft ISerializable classes tend to look.  You don't have to use their serialization method (in fact I recommend not), but their general structure is fine.  What you've got in the code you posted is just going to add slowdown and memory bloat -- take out the middle man.

My thinking behind this is to have the option of creating the local variable storage in case I wanted to quickly add a repository of data somewhere for some reason. Say, for custom scripting later on. My inexperience in large projects means that I am pretty clueless as to what I need to have ready for later, so having a general place I can store and retrieve data when I want might help me speed up the prototyping as well. Of course, hard data would be turned into regular class variables once ironed out.

I am still kind of getting used to using collection type functions. All my previous scripting experience was absent these data structures (even arrays). Thus I had to concoct very elaborate ways of storing and retrieving data...  Now that I have free reign to use them I am sure I will get a bit carried away until experience tempers my lusts. :p
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on September 30, 2011, 06:28:24 PM
Fair enough, there's more than one way to do stuff.  My experience is that the less code you can write to do something, the better, though -- especially in the long term.  "What is the briefest, most concise, least-operations-using way I can write this?" is always my question to myself.  But Keith and I are performance tuning addicts.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on September 30, 2011, 06:33:30 PM
Fair enough, there's more than one way to do stuff.  My experience is that the less code you can write to do something, the better, though -- especially in the long term.  "What is the briefest, most concise, least-operations-using way I can write this?" is always my question to myself.  But Keith and I are performance tuning addicts.

I am sure I will be too once I get a better idea how to make things work the way I want. :)

Though I don't want to give the impression that I will be stuffing local variable banks on every object in the game or anything. Just that I like having options available in case I find a need.

Please keep critiquing me, I need to keep myself thinking. And the best way I have found to do that is my engaging others.  :)
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on October 02, 2011, 11:32:32 PM
Pardon me if this is a bit too academic but I want to make sure that I am not confusing anything in regards to the big picture of serialization as it relates to developing saved games.

Essentially when a game has the option of saved game starts, it has two movements that end in a running game.

Movement #1: Starts a game from scratch. The game program begins to run and fills the spaces with new data.

Movement #2: Starts a game from saved data. Some, usually not all, of the program is filled with retrieved data, the rest with new data.

Thus, when you write the program you are writing two start-up processes that end in the same playable state, the difference is where the data originates.

Most games serialize the savable game data  when the ‘Save Game’ button is pushed. While others serialize the data as the game is played. Either way accomplishes the same goal (saving data for later) but only the ‘as played’ version allows for more complex game play scenarios where the world can be effectively endless, as its saved and restored as needed.

I can only guess that the push button & save game version is less prone to corruption? But also more prone to lost game time as if you forget to push ‘save’ you lose the time since the last one.

Keeping this in mind, the developer must decide which is more reasonable to implement. Or even necessary.

Am I mistaking something?
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 02, 2011, 11:38:16 PM
There is no game that saves all the data as-played in the sense you seem to mean.  Data isn't just streamed to disk or anything.  Regardless of whether a button is pushed or a timer is tripped inside the game program, and regardless of whether or not the entire game state is saved or only art of it... a function moves some data to disk, that can later be read back.  That's it.

In terms of starting a new game or loading a savegame, the difference there should be minimal.  The amount of code for starting a new game or loading a savegame are both trivial compared to the amount of code for actually running the game, which is the same in either case.  It's like walking in your front door or your back door; yes, both are different -- this is obvious, but you get into your same house either way.  And those doors are just a very tiny part of the complexity of your whole house.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on October 03, 2011, 12:10:15 AM
There is no game that saves all the data as-played in the sense you seem to mean.  Data isn't just streamed to disk or anything.  Regardless of whether a button is pushed or a timer is tripped inside the game program, and regardless of whether or not the entire game state is saved or only art of it... a function moves some data to disk, that can later be read back.  That's it.

I seem to have said something wrong.

I did not mean to imply that any game state is ever fully saved, or fully streamed. Only that the data to be saved (for whatever reason) is traditionally done in a single step (such as pushing 'Save Game') or in an 'as played' step where it occurs almost immediately after savable data is available.


In terms of starting a new game or loading a savegame, the difference there should be minimal.  The amount of code for starting a new game or loading a savegame are both trivial compared to the amount of code for actually running the game, which is the same in either case.  It's like walking in your front door or your back door; yes, both are different -- this is obvious, but you get into your same house either way.  And those doors are just a very tiny part of the complexity of your whole house.

Again, I seem to have said something wrong as that is essentially what I was trying to say.

Just to reiterate for the sake of clarity…

When the game starts the relevant data is either retrieved (from a serialized location), or created (from new processes), based on whether or not it’s a saved game that’s starting, or a new game. Even if that data is nothing more than the player name and location, a saved game places them where they last exited the game and a new game places them where all new game players start… In the end, it is the same game that is running.

In more complex scenarios the developer must consider if any serializable data is relevant upon any player action.

Such that, entering a room will always check for the serializable variable that says if it’s been entered or not already. A new games flag is unset, where the saved games flag is. The question becomes when that flag is to be serialized.

Did I explain that clearer?

Note: I sometimes tend to get a bit esoteric when talking about things I am new too and I apologize if I complicate these conversations as a result. I am sure that once I get more familiar with the normal programming parlance it wont be as much of a head ache to deal with my questions...  :-[
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 03, 2011, 09:33:41 AM
Fair enough.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on October 03, 2011, 09:57:32 AM
Fair enough.

I am getting the impression that I am beginning to annoy you.

I understand that you are busy and I really do appreciate the attention you are giving me. I hope I an not squandering it with pointless questions, only to lose it when I have good ones.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 03, 2011, 10:08:04 AM
You're not particularly annoying me.  But, the questions lately have boiled down to two categories: 1) things that really are a matter of opinion and that everybody does differently and that I don't have any reason to try to convince you to do my way -- it would be a disservice to you and a waste of my time; and 2) things that are fairly basic programming questions that most professional programmers should be able to answer.

I'm happy to answer questions when I can, but I don't have any desire to convert you or anyone else to my exact methodology of doing things, or to teach C# 201, or to get into lengthy debates of any kind.  I spend most of my time trying to avoid getting into such discussions at this point, as they rarely serve any purpose as nobody comes away convinced of anything most of the time.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on October 03, 2011, 10:44:14 AM
You're not particularly annoying me.  But, the questions lately have boiled down to two categories: 1) things that really are a matter of opinion and that everybody does differently and that I don't have any reason to try to convince you to do my way -- it would be a disservice to you and a waste of my time; and 2) things that are fairly basic programming questions that most professional programmers should be able to answer.

I'm happy to answer questions when I can, but I don't have any desire to convert you or anyone else to my exact methodology of doing things, or to teach C# 201, or to get into lengthy debates of any kind.  I spend most of my time trying to avoid getting into such discussions at this point, as they rarely serve any purpose as nobody comes away convinced of anything most of the time.

Point(s) taken.

It did not occur to me that someone who has been programming for a living wouldn't exactly be as excited as I am about the possibilities of code use...  ???

Makes me want to laugh at myself for my naivete.

I shall endeavor to be less obtuse with my future inquiries!  :P
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 03, 2011, 10:46:21 AM
No worries, I'm glad you're excited about the code -- that's the right way to be.
Title: Re: How are you handling Serialization with Unity3D?
Post by: RogueDeus on October 05, 2011, 03:09:46 PM
I hope this is not an unusual question...

I have decided I will use C# standard DataContractSerializer for my needs until my needs change. Now I am thinking how I will pick and save the data.

I am thinking an easy way to contextualize serialized files is by game level (map, region, what have you). Thus when entering a map, the collection of serialized objects for that map gets checked and instantiated as necessary. But this also means that each object will either need to be individually serialized, or added to a collection for group serialization.

How do you handle this?

Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 05, 2011, 03:13:31 PM
I've never used DataContractSerializer, so I can't really comment on any of that.  However, I will say that Microsoft has a tendency of breaking its own serialization.  It's very brittle, because sometimes when they update to a new version of .NET, it loses the ability to read back some older serialized data.  This is fine if it's used for passing messages, but not for persisting data if you ever plan to upgrade .NET.
Title: Re: How are you handling Serialization with Unity3D?
Post by: keith.lamothe on October 06, 2011, 09:55:35 AM
My general advice with regard to the class library or any 3rd party code: use it to save time doing things yourself, but be prepared to have to go back and re-implement at least part of the functionality yourself.  It doesn't happen in every case but between:

1) Libraries that don't do what they say they do (actually pretty rare in my experience with .NET).
2) Hidden gotchas like:
- transient heap allocation that leads to lots of garbage collection (foreach creating enumerators, string + operator).
- not deterministic across different machines and runtimes (float, double).
3) Simply needing to make it more efficient.

I've wound up re-implementing or at least wrapping a lot of the library stuff I once used.
Title: Re: How are you handling Serialization with Unity3D?
Post by: Nalgas on October 08, 2011, 07:37:24 PM
Also, indexing by strings is incredibly slower than by enums.  String comparisons are wicked slower than enum comparisons, and the comparison time varies by the length of the string.

That is generally a good rule of thumb, but strings do come in handy for that sometimes, and there are some pretty nifty ways of dealing with them, like tries (http://en.wikipedia.org/wiki/Trie).  You can actually have your dictionary use strings for keys and be faster than a hash table in some situations, when used appropriately.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 11, 2011, 01:28:39 PM
Pretty cool on the tries!
Title: Re: How are you handling Serialization with Unity3D?
Post by: keith.lamothe on October 11, 2011, 01:50:46 PM
Yea, I love the idea of bitwise tries particularly, but all the cases I've thought to use them on (like the lookup for ForegroundObject's in AIW, since they're always uniquely identifiable by a 32-bit int primary key) don't seem like good use cases because as the number space approaches full the memory size of the trie structure would approach 2^32*sizeof(node) bytes.  That's more than a theoretical concern because the IDs cannot be reused; obviously the game would go bonkers once it ran out of IDs anyway but the memory consumption of the trie would become highly non-trivial fairly early on.  Of course, a smart trie implementation could "hollow out" the actual in-memory bits that corresponded to leaves and sub-trees of dead-and-gone units.  But it would depend on the distribution of deaths for actually being able to dump large swaths, etc.  As long as every 64th unit (in creation order) was still alive, for example, you'd still be approaching 2^26 nodes.

Or am I missing something about those wonderful little binary-math-exploiting structures?
Title: Re: How are you handling Serialization with Unity3D?
Post by: Hearteater on October 11, 2011, 03:26:51 PM
Well, a bitwise Trie's memory footprint for 32-bit IDs would not be anywhere near 2^32 until your active IDs got that high at which point I'm sure other memory issues would be the problem.  Tries aren't complete binary trees stored in a solid block of memory so they only use up memory for actual IDs not potential IDs.  If I recall correctly it would have n-1 interior nodes and n leafs where n is the number of IDs currently in use.

For example, assume you had 0x8000 and 0x0001 as the only IDs.  You would have a root node with two children.  Those children would point directly to the two objects: Left -> ID 0x0001 and Right -> ID 0x8000.  If you added ID 0x8001 the right child would point to a new node with two children: Left -> 0x8000 and Right -> 0x8001.  Every 64th unit being alive or the first 2^26 units being alive would occupy exactly the same amout of space for the Trie.

Not to imply you didn't know any of that.  I just happen to like data structures.  In my free time I read about them.  Yeah, it's a little weird.  I especially love priority queues.

Anyway, I think I have a bitwise Trie implementation around in C or C++ if you want me to dig it up.
Title: Re: How are you handling Serialization with Unity3D?
Post by: keith.lamothe on October 11, 2011, 03:37:07 PM
Well, a bitwise Trie's memory footprint for 32-bit IDs would not be anywhere near 2^32 until your active IDs got that high at which point I'm sure other memory issues would be the problem.
Right, my concern is that the memory complexity of the trie would be such that n is the number of ForegroundObject's that have ever existed in that savegame, rather than proportional to the number of ForegroundObject's that currently exist.  Not that the no-longer-existing ones would require storage, but that a single existing unit could require 32 nodes all by itself if the trie is totally uncompressed (and I'm really not clear on the insert time for compressed tries, we have frequent inserts); some those nodes would be "reused" by anything within the appropriate "subtries" but those early ones are going to get sparser and sparser as the game goes on and old units die off but the game would be unable to reclaim some (most?) of the memory due to the remaining "skeleton" being necessary to keep linking those ships from those ID intervals that were still alive.

So in a practical case we might only be talking 20MB extra late in a large game, but that could be enough to push it over the limit and we're back to OutOfMemory errors.  Those errors really annoy us ;)
Title: Re: How are you handling Serialization with Unity3D?
Post by: Hearteater on October 11, 2011, 03:55:58 PM
Yeah, it actually isn't that bad.  When inserting, you don't create extra nodes unless you hit an existing leaf and need to split it.  So at most each insert adds one node.  You actually wouldn't want a compressed Trie since you will be modifying the Trie.  But you can prune off the skeleton nodes in the delete method.  It actually isn't all that unreasonable to do so.  A recursive delete can remove nodes as it backs out when you've deleted the only leaf on a node.  Optionally adding a parent pointer to each node makes an iterative delete extremely fast at the cost of more total memory usage for the whole Trie.  I tend to favor the recursive solution, but in a Trie that can cause an issue when you use a lookup table to jump into the middle of the tree.  The best way around that is to not allow the nodes referenced in the lookup table to be deleted.  In effect that splits the Trie up into 32 smaller Tries.
Title: Re: How are you handling Serialization with Unity3D?
Post by: keith.lamothe on October 11, 2011, 03:58:52 PM
But you can prune off the skeleton nodes in the delete method.
Unless, of course, you still need them because there's still a single unit left alive in that interval :)
Title: Re: How are you handling Serialization with Unity3D?
Post by: Hearteater on October 11, 2011, 04:10:57 PM
It actually works pretty well.  Every internal node has either a) at least one leaf node, b) two internal nodes.  Deletes leave no real skeleton regardless of sparsity.  I'll dig up the code for it.  I think it may take up less memory than you are expecting.  Whether it meets any of your other needs is another question :) .

NOTE: In a way this is actually a compressed Trie implementation, but without the compact data representation that tends to make them read-only.  Because of that it adds very little to the delete operation and inserts are actually slightly faster since you don't create extra internal nodes.
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 11, 2011, 04:42:48 PM
To be clear: the AI War unit IDs can get into the millions or hundreds of millions very easily since they aren't reused.  The actual count of units active at any given time tends to remain below 100k.  Think this would still fit in the model you're thinking, Hearteater?  I expect it will based on what you said, but just wanted to make the full parameters of our use case clear. :)
Title: Re: How are you handling Serialization with Unity3D?
Post by: Hearteater on October 12, 2011, 09:34:44 AM
Yeah, it should work fine.  Memory is only used for active IDs.  Once you delete an ID from the Trie, it uses no more memory.  And the actual values of individual IDs has no (practical) bearing on the total memory footprint of the Trie itself.  I dug through my data structures library and I don't have my Trie implementation there, so tonight I'll boot up my old laptop and see if I left it on that.

I'm curious, what data structure do you use to look up IDs currently?
Title: Re: How are you handling Serialization with Unity3D?
Post by: x4000 on October 12, 2011, 10:02:15 AM
Right now, in AI War, it's a generic dictionary with int key and ForegroundObjecet value.