Hunter Hale

Science:

I have been working on several decomp quality metrics to allow us a suite of tools to evaluate different decomps of the same world.

Metrics – All these metrics assume a decomp is readily available.

1. Object Placement Analysis (OPA) -  Consider each individual region in the decomp.  Attempt to place as many copies of a user defined object into each region as possible.  For the purposes of testing this on paper I have been using pennys.  Graph the results of this analysis by placing #number of objects placed on the x axis, and number of regions that could only fit that many objects on the y – axis.  For this metric we would consider decomps that showed high values for the lower number of objects (lots of regions that can only fit 0-2 of the choosen object) to be bad which large numbers of regions that can fit a high (user defined but probably 10+) number of regions to be good.  ie the graph should have a strong right skew.  Regions that can fit an insaine number of objects (50+) are probably indicative of regions that might be to large for proper information compartmentalization.

—extension to above — In addition to looking at the above graph it should be possible to determine how much of each region cannot be filled with an object and the amount of “wasted” or “dead” space could be calculated and graphed

2. Co-Existant Point Graph — Consider the listing of vertexs composing the decomposition. It is possible to graph the occurances of and numbers of indentical vertexs.  The x-axis would show vertexs sharing a common point(ascending integers) and the y-axis would indicate how many times this occured.  For example if x = 2 and y = 10 then that would mean that 2 different vertexes overlaped 10 times in the final decomposition.  High numbers in this graph would indicate the existance of problem areas where information compartmentalization might break down due to multiple regions coming together in a point.

3.  Decomp Efficency Metric — I devised a simple equation to determine how well a area is decomposed.  (Area covered by regions / sum of interior angles of regions)/ (Total Area/ 360)  – Assuming the original area is roughly square (thats where the 360 comes from).  This metric can be used give a flat numeric score to different decomps of the same map (it does not carry to comparing different maps). Maximizing this score will result in the formation of fewer larger decomp regions.

4. Region Homogenaty Analysis — By finding the maximum size of a region in two perpendicular directions it is possible to get a feel for the regions compactness (squareness).  The quotent of these two value for each region can then be used to generate a box and whisker plot (with outliers included) to visually see how compact and normal shaped the decomposition is.  Good tight decompositions will generate data with a low standard deviation and few outliers.  Poor decompositions will generate data that has a high standard deviation and many outliers.

5. Coverage %

6. Number of Regions

7. Connectivity Distribution Graph (x – Number of connections, y – Regions with that number of connections)

8.  Distribution of Mininum Angles per polygon

Finally the existing techinques of  completeness of the navigation graph, minimum interior angles, and number of regions can be used for decomposition quality metrics as well.