Parsing meta from a Halo 2 Xbox map using plugins

[Win]

I am trying to create an efficient method for loading a tags meta data from the MetaTable into a derived class of MemoryStream. The problem I ran into is that when I use a normal recursive method (read each reflexive as I come to it, and write it to the stream after the last reflexive, after the Header Meta) to load the reflexive's meta the layout in memory looks like this:

Code: Select all

[Tag Header Meta]
[Reflexive]
[Child Reflexive]
[Child Reflexive]
[Reflexive]
[Child Reflexive]
[Child Reflexive]
...

When it should look like this: (This is how it is arranged in the map)

Code: Select all

[Tag Header Meta]
[Reflexive]
[Reflexive]
[Child Reflexive]
[Child Reflexive]
[Child Reflexive]
[Child Reflexive]
...

I was just wondering if anyone knew of a recursive loop system that would read each tier of meta before moving onto the next.

[Anthony]

can you post a bit of your source?

[Altimit01]

Separate your recursive reading/writing from your data reading/writing.

Right now you're doing something like:

Code: Select all

read_data()
{
	for (i = 0, i < data.count, i++)
	{
		data(i).read
	}
}

read()
{
	reading_code
	for(i = 0, i < children.count, i++)
	{
		children(i).read
	}
}

You need something like:

Code: Select all

read_data()
{
	for (i = 0, i < data.count, i++)
	{
		data(i).read
	}
	for (i = 0, i < data.count, i++)
	{
		data(i).recurse
	}
}

read()
{
	reading_code
}

recurse()
{
	for(i = 0, i < children.count, i++)
	{
		children(i).read
	}
	for(i = 0, i < children.count, i++)
	{
		children(i).recurse
	}
}

Just from what I understand you're doing, this is how I'd fix it.

[Win]

Sure but I do not know if it will help, I was playing with an idea but it proved to be obtuse.

Code: Select all

class TagStructureLoader
    {
        MapStream Map;
        public TagStructureLoader(MapStream map)
        {
            Map = map;
        }

        public TagStream ParseTag(TagInformation TagInfo)
        {
            Map.Position = TagInfo.MetaOffset;
            TagStream tag = new TagStream(TagInfo.MetaSize, Map);
            string Plugin = Application.StartupPath + string.Format("\\plugins\\{0}.ent", TagInfo.Class);
            if (File.Exists(Plugin))
            {
                ParseHeader(Plugin, tag, Map);
            }
            else
            {
                MessageBox.Show(string.Format("{0} Plugin Not Found", 
                    System.Globalization.CultureInfo.CurrentCulture.TextInfo.ToTitleCase(TagInfo.Class)));
            }
        }

        public void ParseHeader(string fileName, TagStream tag, MapStream map)
        {
            //Initialize our XmlDocument for parsing
            XmlDocument xmlDoc = new XmlDocument();
            //Load our plugin
            xmlDoc.Load(fileName);

            //Get the root to read the header information from
            XmlElement root = xmlDoc.DocumentElement;

            tag.HeaderSize = root.Attributes["headersize"].Value;

            //Create GenericList to store reflexive nodes in
            List<XmlNode> reflexives = new List<XmlNode>(tag.HeaderSize);

            //Loop through all the nodes
            for (int i = 0; i < root.ChildNodes.Count; i++)
            {
                //If the name isnt revision...
                if (root.ChildNodes[i].Name != "revision")
                {
                    //Then get the returned value.
                    HandleNode(root.ChildNodes[i], tag, reflexives);
                }
                else
                {
                    //Otherwise
                }
            }
            ParseReflexives(reflexives);
        }

        private void ParseReflexives(List<XmlNode> reflexives, TagStream tag, MapStream map)
        {
            List<List<XmlNode>> nextTierReflexives = new List<List<XmlNode>>(reflexives.Count);

            for (int i = 0; i < reflexives.Count; i++)
            {
                List<XmlNode> childReflexives = new List<XmlNode>(reflexives[i].ChildNodes.Count);
                for (int index = 0; index < reflexives[i].ChildNodes.Count; index++)
                {
                    if (reflexives[i].ChildNodes[index].Name != "revision")
                    {
                        HandleNode(reflexives[i].ChildNodes[index], tag, map);
                    }
                }
                childReflexives.TrimExcess();
                nextTierReflexives.Add(childReflexives);
            }
            foreach (List<XmlNode> CR in nextTierReflexives)
            {
                ParseReflexives(CR, tag, map);
            }
        }

Your code does the same thing I described unless I am mistaken Altimit01, just in a more direct manor: I had my code setup to place reflexives after the Header anyways. And the above code stops working after the first tier

[Altimit01]

Yeah I realized that after recursing to a lower level with it. This is an interesting situation that's for sure. I'll be working on this until it's solved most likely.

[Win]

After thinking about this for awhile, I could only come up with a few ideas:

Multi-threaded: Each Reflexive is read using a new process (so they all read at the same time), and then they wait for bool or something before reading the next tier. Thats a bit out of my league though, I have never played with processes past starting another thread within another. I also do not know how to make them share a single stream without C# throwing a fit.

Read it normally (using a default recursive method) then sort it into a another stream. (Double memory requirements)

[Altimit01]

Personally I never use thread handling except as a way of doing intensive tasks without my GUI from locking up and people thinking the program froze. I'm also fairly certain windows hates multiple streams open to the same file at once. I ran into that issue with Eschaton since OSX doesn't care unless both streams are active or something similar.

This is the best I can do in generalized form:

Code: Select all

main()
{
	recurse(0, root, queue)
	queue.sort_by_depth
	for(i = 0, i < queue.count, i++)
	{
		queue(i).data.read
	}
}

recurse(depth, data, queue)
{
	for(i = 0, i < data.count, i++)
	{
		queue.add(data(i), depth)
		recurse(depth+1, data(i).children, queue)
	}
}

It's kind of sloppy but I'm not sure there is a recursive algorithm that can do what you want to do. I'll get on adapting that to your code unless some one posts a better way. It will actually be decently light too since all the operations would be done reading from the xml data rather than the binary data.

Edit: I found a wiki article on the same sort of problem. It relates to searching through trees rather than just going through the whole thing but the algo is roughly the same. Breadth-first traversal

[Win]

The potential of the Multi-threaded approach appeals to me: it seems that it would dramatically speed up the loading larger tags with many reflexives. Does anyone have experience with working with multi-threaded applications? I do not know how to make the processes all play nicely together (they would need to be assigned an indexer I believe so that I I knew in which order to allow each thread to write to the MemoryStream) Anyone got any ideas? I am out of my league here, lul.

Looking over your code it does look like another good solution.

[OwnZ joO]

Multithreading it is not your answer. It just allows you to do two tasks at once, which can speed up the reading, but you wouldn't know which reflexives were done reading first. It wouldn't solve the problems that you're having.

[Altimit01]

After thinking about it for a bit I agree for the most part with Ownz JoO.
The problem with threading is that for how you want to use them, you gain no benefit. Unless you're storing each bit of data separately (which would remove the problem anyways) or can preallocate the data stream and have each thread write to the correct location (which also removes the ordering problem, I'm actually a bit of a fan of this) you'll have to basically delay when each thread can execute at which point you lose all the advantages of parallel processing. You'd just be ordering threads instead of ordering calls to your read method.

Now if you were able to preallocate the stream you're writing into, and can calculate the position where each bit of data needs to go (which would mean determining size and count of each reflexive and so forth) you could let each thread run without restriction. Of course there's still the problem of multiple streams open to the same object I think.

The breadth-first algorithm for tree traversal is how you would want to solve the problem without threading. The examples on the wiki article relate to either node trees or graphs but I think you could probably adapt it. It's similar to the solution I posted but instead of one big queue that is added to then sorted, you'd use a smaller queue and constantly be adding to and dequeuing from during traversal.

Btw, it's really nice to see some interesting programming discussion around here as opposed to "how do I make X GUI control do Y?" Thanks for the brain work out.

[Win]

Resolved using a queuing system. Thanks to all for all your input.