XMLDiff/XMLMerge... HELP!!

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderator: Committer

Post Reply
Message
Author
OceanMachine
Pupating Mass
Posts: 95
Joined: Thu Jun 26, 2003 12:09 pm
Location: Chicago

XMLDiff/XMLMerge... HELP!!

#1 Post by OceanMachine »

I recall there was some discussion of these things between Josh and Zach on the old forum not long before it went down. I don't recall what was said there... I've got all the basic encoding/decode done for universe and am at the point of handing the diff and merge part of it and would like to review things a bit before I make any huge mistakes. I spent some time looking at the Empire implementation of things, and am left with numerous questions. So here goes:

On the server side, I think I pretty well understand the creating of the diff XMLElement, although I don't see where the last turn map is getting updated... I rather suspect that's just a bug..

So I'll create a map of last_turn XMLElements indexed by empire ID's, initialize it with empty XMLElements, then each turn generate the full encoded universe for each player and diff it with what is in the map for them, then store the encoded universe I just generated into the last_turn map for them, and return the diff.

On the client side, I've stored the encoded Universe from the previous turn and XPatch that with the diff that was sent from the server. This gives me an updated, encoded Universe. At this point, in Empire the code is something like this:

Code: Select all

    for(int i=0; i<new_state.root_node.NumChildren(); i++)
    {
        Empire decoded_empire( new_state.root_node.Child(i).Child(0) );
        Empire* old_empire = Lookup(decoded_empire.EmpireID());
        
        if(old_empire)
        {
            *old_empire = decoded_empire;
        }
        else
        {
            old_empire = new Empire( decoded_empire );
            InsertEmpire(old_empire);
        }
    }
First of all, is it safe to assign the decoded empire over the old one? I didn't think C++ memory management was up to that sort of thing...

More on point, this algorithm doesn't look like it addresses deleted empires. I don't suppose we really need to delete the empire objects, but we will want to delete universe objects. How is that supposed to get picked up from the diff? Is there some easy to tell if objects are deleted, or will I need to check through each universe object and see if it is still present in the updated xml universe? And if so would I be better off just wiping out the client's universe object map each turn and completely repopulating it from the updated xml universe? This would be easiest solution to program, but I don't know what sort of performance hit it'd carry..

Also all of the universe objects have an XMLMerge function, as does Empire. But it doesn't look like Empire is using it. Is there a reason for this?
Programming Lead

elfstone
Space Squid
Posts: 78
Joined: Fri Jun 27, 2003 9:00 am
Location: Germany

#2 Post by elfstone »

While reading this, i asked my self if there are complete snapshots to be sent, like in divx, so every X turns, the whole empire/universe xml is sent to the client, and check if its still the same. Just to make sure, that there havent been any mistakes.

After writing 3/4 of the post, i started thinking, and it would be enough and much faster to create a checksum of the empire on the server, and send it too the client, so the client can compare it.

Or even better, the client computes the checksum and sends it to the server, to be compared.

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: XMLDiff/XMLMerge... HELP!!

#3 Post by tzlaine »

OceanMachine wrote:I recall there was some discussion of these things between Josh and Zach on the old forum not long before it went down. I don't recall what was said there... I've got all the basic encoding/decode done for universe and am at the point of handing the diff and merge part of it and would like to review things a bit before I make any huge mistakes. I spent some time looking at the Empire implementation of things, and am left with numerous questions. So here goes:

On the server side, I think I pretty well understand the creating of the diff XMLElement, although I don't see where the last turn map is getting updated... I rather suspect that's just a bug..

So I'll create a map of last_turn XMLElements indexed by empire ID's, initialize it with empty XMLElements, then each turn generate the full encoded universe for each player and diff it with what is in the map for them, then store the encoded universe I just generated into the last_turn map for them, and return the diff.

On the client side, I've stored the encoded Universe from the previous turn and XPatch that with the diff that was sent from the server. This gives me an updated, encoded Universe. At this point, in Empire the code is something like this:

Code: Select all

    for(int i=0; i<new_state.root_node.NumChildren(); i++)
    {
        Empire decoded_empire( new_state.root_node.Child(i).Child(0) );
        Empire* old_empire = Lookup(decoded_empire.EmpireID());
        
        if(old_empire)
        {
            *old_empire = decoded_empire;
        }
        else
        {
            old_empire = new Empire( decoded_empire );
            InsertEmpire(old_empire);
        }
    }
First of all, is it safe to assign the decoded empire over the old one? I didn't think C++ memory management was up to that sort of thing...
Ok. The whole concept of the XMLMerge function has been removed, based on Josh's suggestions. Now, the XDiffs are automatically turned into normal XMLElements by using XPatch and the XML encoding of the previous turn's version of each object. So you should never need to look into the contents of a diff or the previous turn's objects at all.

To create a diff server-side:

- Before you do the turn updates, you create an XML encoding of everything: the empires, the universe, etc. These XMLElements go into a single XMLDoc. (You may need to make several versions of the doc, since each player should see only part of the game state.)

- After the turn updates are complete, you XDiff the empires, universe, etc. with the previous versions, to produce a single diff XMLDoc.

- Finally, you send the diff Doc.


To handle a diff-update client-side:

- XML encode everything that you encoded in the server when you made the diff, such as the universe and empires. This goes in one XMLDoc as well, representing the previous-turn's state. Delete all the actual objects used to make this Doc.

- XPatch the diff doc to the previous-turn XMLDoc, and now you havve an XML encoding of the new turn's data.

- Use the ctors for all the objects in the new Doc to recreate them.

More on point, this algorithm doesn't look like it addresses deleted empires. I don't suppose we really need to delete the empire objects, but we will want to delete universe objects. How is that supposed to get picked up from the diff? Is there some easy to tell if objects are deleted, or will I need to check through each universe object and see if it is still present in the updated xml universe?
Hopefully it's clear from the stuff above, but this should happen automatically.
And if so would I be better off just wiping out the client's universe object map each turn and completely repopulating it from the updated xml universe? This would be easiest solution to program, but I don't know what sort of performance hit it'd carry..
This is the way to go. The only performance hit is that the deletes and news are probably going to be a little expensive, but they're probably about the same as looking into all the diffs and figuring out what to change, and then doing a bunch of individual deletes and news on differences. However, this approach is much less error prone than the "manual" way of doing things.
Also all of the universe objects have an XMLMerge function, as does Empire. But it doesn't look like Empire is using it. Is there a reason for this?
Yeah, this is just because I never went back and removed all those XMLMerge functions from Universe.

jbarcz1
Creative Contributor
Posts: 226
Joined: Thu Jun 26, 2003 4:33 pm
Location: Baltimore, MD

#4 Post by jbarcz1 »

Joseph is correct that the code he posted will not deal with deleted empires. I'm going to go back in and fix it up sometime this weekend.
Empire Team Lead

OceanMachine
Pupating Mass
Posts: 95
Joined: Thu Jun 26, 2003 12:09 pm
Location: Chicago

#5 Post by OceanMachine »

Josh, how about we move the storage of the previous turn and the XDiff out of empire and up to the ServerApp level so that we can combine both Universe and Empire in one message as Zach suggested. Similarly for XPatch at the client.. So you'll just need to have an encode function that returns an XMLElement for the server and a decode function that accepts an XMLElement at the client. Acutally the decode should be present in the server as well, since last I heard we'd also be using it for loading save files..
Programming Lead

jbarcz1
Creative Contributor
Posts: 226
Joined: Thu Jun 26, 2003 4:33 pm
Location: Baltimore, MD

#6 Post by jbarcz1 »

That proably makes sense, having all the diffs in a centralized location.
I'll be happy to pass on the work to Zach if he doesn't mind :)
Empire Team Lead

jbarcz1
Creative Contributor
Posts: 226
Joined: Thu Jun 26, 2003 4:33 pm
Location: Baltimore, MD

#7 Post by jbarcz1 »

Actually, while we're on the subject of shifting work around, I have not had a whole lot to do for Empire lately, and I've had lots of free time than I did in the spring, so if you want to put me on another team to help out, I'm cool with that. It may change once I get to grad school in the fall, but I should be available more for the moment.
Empire Team Lead

OceanMachine
Pupating Mass
Posts: 95
Joined: Thu Jun 26, 2003 12:09 pm
Location: Chicago

#8 Post by OceanMachine »

jbarcz1 wrote:That proably makes sense, having all the diffs in a centralized location.
I'll be happy to pass on the work to Zach if he doesn't mind :)
I'll take this on. And Josh, will get back to you on other work...
Programming Lead

Post Reply