Guilds/Bastet/Our Two Scents Worth/Energy Graph

Solving the Resin Map

Introduction

A number of fellow programmer-types have expressed interested in the domain problem of solving the incense resin map. This is a problem primer and some data to aid in that goal.

I'm inclined to solve the Resin map using a spring graph solving algorithm. This is complicated by the nature of the data we have and the the problem we're solving, so it's not as cut-and-dried as solving a normal graph. However, given the data I have collected and some initial discoveries to provide seed values, I think it can be solved best this way.

The Nature of the Problem

The graph we're trying to solve is the map of the Resin Plane of incense in Tale 4 Bastet. So there is an ideal solution, barring small numerical errors due to the rounding.

There are three types of points in the map. There are "start points", "resin points" and "stat points". When a batch of incense is started, it is randomly assigned one of the 12 start points on the plane as a working point. The user is then given a resin quality measurement and told which stat point (of 17) is closest. The quality measurement is (Q-D) where Q is some arbitrary base quality and D is the distance from the working point (which begins as a "Start point") to the named stat point.

As a resin is added, the working point moves in a straight line from the start point to the resin point in decreasing steps. (We ignore multiple resin types as an unnecessary complication right now) At each step the user is given a quality measurement which uses the same base Q value and reflects the distance to the nearest stat point, and the identity of that stat point.

A considerable amount of data has been collected using different starts and resins. We'll use this to regenerate the map.

How the Problem Deviates From a Traditional Spring Graph

Normally we use damped springs to solve graphs with dimensionless nodes connected by weighted edges of known value. This problem has a few differences:

There are effectively two entities in the graph we're solving: "Sticks" which are a series of nodes beginning at a "start point" and ending at a "resin point"; and "atoms" which are more traditional dimensionless nodes representing the "Stat points" we get measurements to. We can constrain the problem to keep these nodes collinear and regularly spaced according to a known formula.

Furthermore, the nature of the data means that any resin runs we do from a common start point will share the starting point, so these "sticks" share their zeroth node. Also, any data runs using the same resin will begin at different start points, but terminate in a common "resin point".

The values we have recorded are not distances to the atoms, but are arithmetically related to those distances. All the data from a single run uses the same Q value, so we need to relate these to determine actual distances.

Finally, the length of the stick is not known but needs to be determined. Luckily, the nodes are regularly spaced, so they will all compress or expand together.

Nitty-Gritty

I will designate the stat points - the atoms - as A₁ A₂ etc. I'll provide a legend to convert them to the stats for those of us not only looking at the pure math side of the problem. :) These are graph nodes in the traditional sense. There are no atom-atom edges. There are atom-stick edges.

I will designate sticks as S_S1R1 as a code for which start point and resin they represent. Any sticks which share the "S#" designation, such as S_S3R4, S_S3R12 and S_S3R7, all start from the same point; that is their zeroth node is the same. Similarly, any sticks which share the "R#" designation share their endpoint, which I refer to as the R^th node, or node R.

Nodes are regularly distributed along a stick. Node₀ is one endpoint, and Node_R is the other. Node_k is at position

( 7 × Node₀ + k × Node_R ) / ( 7 + k )

Each node on a stick will have a single edge connected to an atom. For sanity-checking purposes, it will always be the closest atom. The data for a stick will name the atom and give a value. The value is equal to (Q-D) where Q is an arbitrary value which is constant for this stick only and D is the distance from the node to the atom. To reiterate, for nodes 0, 1, 2, ... we will have values X₀, X₁, X₂, ... where X_k = Q - D_k where D_k is the distance from Node_k of this stick to the atom.

Where a length is given, this is the Node₀ to Node_R distance. Where a Q-value is given, this is the value we can use to calculate the accurate edge weights to atoms within this stick. These are usually pretty close approximations and will serve to help set up an initial state that is more likely to solve.

The Data

The atoms

• A₁ = STRconf
• A₂ = PERweak
• A₃ = ENDconf
• A₄ = FOCclum
• A₅ = DEXfrag

The Sticks

Stick S_S1R1

Start point: STRconf

Resin: Arconis

Length: ~478

Q value: ~336

Data:

Node	Quality	Atom
Node0	213	A1
Node1	273	A1
Node2	318	A1
Node3	314	A1
Node4	285	A1
Node5	259	A1
Node6	238	A1
Node7	220	A1