Reflexive Detecting in Meta Related Code

Moderator: Altimit01

User avatar
Modzy
Green Beret
Posts: 3056
Joined: Fri Feb 22, 2008 11:06 pm
Location: Portland, OR

Reflexive Detecting in Meta Related Code

Post by Modzy » Fri Aug 07, 2009 12:25 am

All current map editors have the issue I'll be discussing in this topic; false positives.
When extracting tag meta, the map editor will find something it thinks is a reflexive and add it to an .xml file. This sounds fine when you're not considering the amount of false positives most map editors will output.
During my development of Pearl, I learned many ways of checking possible reflexives to get them as accurate as possible.

As an example, I'll use a snippet of an .xml file extracted using the latest Eschaton (0.8 )

Code: Select all

<Reflexive location="0x148C" chunkcount="-1101209351" translation="0x12D5F"/>
Now how can there be a negative number of chunks?

There are a few simple checks you can apply to your code to make sure you're getting as much accuracy as possible:
1. Make sure the potential reflexive is inside the tag's meta section; it's value is greater than the tag offset, yet smaller than the tag offset plus the tag length.
2. Making sure that the reflexive modified by the map magic is greater than the current stream's position.
3. THIS IS A BIGGY! Make sure the suspected count is GREATER than zero. This will not allow things that look like chunks but have no count, or the count is negative, to be considered a reflexive.

That should do it!
Last edited by Modzy on Fri Aug 07, 2009 11:35 am, edited 2 times in total.

User avatar
Altimit01
Eschaton Dev
Eschaton Dev
Posts: 2108
Joined: Sun Apr 15, 2007 7:43 pm

Re: Reflective Detecting in Meta Related Code

Post by Altimit01 » Fri Aug 07, 2009 5:42 am

Never heard 'em called reflectives before. As for negative values. That's laziness. The problem with not using them is if they're actually unsigned. Probably not though. This stuff'll be in 0.8.1 though.
Disclaimer: I am no longer active. Any posts, PMs or other communication I use has no guarantee of accuracy or follow up.
Download Eschaton: Mediafire

User avatar
Modzy
Green Beret
Posts: 3056
Joined: Fri Feb 22, 2008 11:06 pm
Location: Portland, OR

Re: Reflective Detecting in Meta Related Code

Post by Modzy » Fri Aug 07, 2009 11:31 am

Altimit01 wrote:Never heard 'em called reflectives before.
Reflectives? What reflectives. :P

User avatar
Altimit01
Eschaton Dev
Eschaton Dev
Posts: 2108
Joined: Sun Apr 15, 2007 7:43 pm

Re: Reflexive Detecting in Meta Related Code

Post by Altimit01 » Mon Aug 10, 2009 9:28 pm

So I couldn't get to sleep and started thinking about how to find reflexives properly. I'm going to do this in a bit of a formal method so bare with me. I'm going to get the basics out of the way for completeness.

The form of the reflexive is as follows:

Code: Select all

int32 chunk_count //signed
int32 translation //relative to start of meta
int32 zero //always zero
Also assuming certain values such as:

Code: Select all

meta_size //the size in bytes of the meta file
offset //the offset of the reflexive data structure
1. Chunk counts are positive. (Predicated on a signed chunk count.)

Code: Select all

if chunk_count < 0 then false
2. Zero is always zero.

Code: Select all

if zero <> 0 then false
3. Translations are within the meta. (Some optimizations can be made here based on assumptions of minimum chunk sizes.)

Code: Select all

if translation >= meta_size then false
4. Translations only point forward. (Included full size of reflexive data structure.)

Code: Select all

if translation <= offset + 8 then false
So those are the basic assumptions and knowns of reflexives. Now here are a few more that I can think of that could lead to greater accuracy.

5. All discrete elements of a meta file are in 32-bit increments.

Code: Select all

if translation mod 4 != 0 then false
6. The first recorded reflexive is correct.
This is based off the idea that meta files put organizational data first and then any raw data is kept further along.
7. There is no padding between the start of one reflexives chunk data and another reflexives chunk data.

Using 5, 6 and 7 allows for some interesting checks. For example:

Code: Select all

//reflexives start sorted by translation

//remove any reflexives that don't align with the previous reflexive
for i = 0 to reflexives.ubound - 1
  while (i+1 <= reflexives.ubound) AND ((reflexives(i+1).translation - reflexives(i).translation) mod (reflexives(i).chunk_count * 4) <> 0)
    reflexives.remove(i+1)
  wend
next

//remove any final reflexive that doesn't align with the end of the meta file
while (reflexives.ubound >= 0) AND ((meta_size - reflexives(reflexives.ubound).translation) mod (reflexives(reflexives.ubound).chunk_count * 4) <> 0)
  reflexives.remove(reflexives.ubound)
wend
The lynch pin of the first part is that the first recorded reflexive is correct. If it's not then that section falls to pieces. If you don't assume 6 then it becomes much more interesting. The process to solve for which reflexives don't align with all the others becomes a very fun optimization problem. I believe there may be a dynamic programming solution to that problem.

An exhaustive (and inefficient and boring) approach would be along these lines:
For all reflexives pick one and assume it is correct.
For all other reflexives that align (can be ahead of or after) with the previous, pick one and assume it is correct.
Recurse until no more reflexives align.
Save that list of reflexives.
Iterate over the solutions and find the maximum list of reflexives.

I can't think of the dynamic approach right now but it would be some variation on that except that it would take advantage of previous solutions in some way. Another approach might be to create a graph where each node is a reflexive and each edge joins two reflexives that align to each other and then determining the longest path. I'm not sure that the graph could be made directed acyclic (and thus solveable) or not.

Thoughts?
Disclaimer: I am no longer active. Any posts, PMs or other communication I use has no guarantee of accuracy or follow up.
Download Eschaton: Mediafire

User avatar
Modzy
Green Beret
Posts: 3056
Joined: Fri Feb 22, 2008 11:06 pm
Location: Portland, OR

Re: Reflexive Detecting in Meta Related Code

Post by Modzy » Mon Aug 10, 2009 9:49 pm

Can't wait for the day when we've got everything mapped out.
I was considering the check of the four bytes that are 0x8 bytes into a reflexive, but I thought it would slow down checking. But since we're going for accuracy, I suppose that's worth it.

EDIT: I'm gonna put off this BSP method for Eschaton and try a few things.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest