Dynamic path weight calcuation

[ChaoticEvilDM]

Situation:

The current program simply calculates a route from P₀ and P₁.

Issue:

While traveling on sea this is fine but land travel comes with perils such as swamps, deserts and occasional altitude changes that can influence the weight of a route dramatically. There is currently no option to influence a path weight, either by region or single path direction.

Suggestion:

Pathing will have an attribute for either direction P₀ -> P₁ and P₁ -> P₀. This should include a weightmod as a multiplier for the route weight.

Example: P₀ is situated in a valley. P₁ atop a mountain. Both are connected by a road.

p0p1: {
weightmod: "1.3"
}
p1p0:{
weightmod: "0.7"
}

Traveling from P₀ -> P₁, uphill, is significantly harder then moving downhill from P₁ -> P₀.

It is also encouraged to have a field for an optional reason (e.g. seasonal snow, flooding, snorlax on road, aso.) that can influence a parties decision on whether or not to proceed.

[ChaoticEvilDM]

This issue poses significantly more weight then initially anticipated. Mainly, the chosen free form of lines across the map space causes significant issues in terms of calculation, especially in elevation changes.

I developed two basic theories on how to address this.

1: Math, not even once

We draw a cone with a height of h that is shown a circle on a top down X/Y map.

Given is a line m P₀ -> P₁, cutting the circle c at the points mc₀ and mc₁. c has a centerpoint c₀. All these points have a Z of 0. We are using a function to determine if the line cuts the circle and if so, what the coordinates of mc₀ and mc₁ are. Given these, we can find the point mc₀ₗ₁, the exact middle between mc₀ and mc₁.

Drawing a line from c₀ through mc₀ₗ₁ with c(radius) as length, gives us the coordinates of c₁ on the circles rim. c₀ where Z=h of the cone (cₕ) is now in line with mc₀ₗ₁, c₀ and c₁. Using a simple function for right triangles, we can determine the angle ° of cₕ and therefore mc₀ₗ₁ₕ by extension. mc₀ₗ₁ₕ is the maximum elevation when crossing the cone at the choosen path and can be used in calculations. This is a very elegant way to get a very precise answer.

2: Classic grid, extended issues

Draw a hex grid. Each grid hexagon has a height of h. If a line crosses this hexagon, it influences the calculation.

\sum_{n=0}^{n_max} (n+1 - n)

This will give a rought estimation over any given length and is simple yet very unprecise.

[ChaoticEvilDM]

Hazards in general

Hazards can have a system wide rating that influence either direction either simultaneously or separate from each other due to the hazard influencing the complications of travel in a different manner.

Reasoning is, that mountains are hard to climb during thawing season but easier to get down from - yet not necessarily safer. Therefore, calculations should determine whether P₀(h) > P₁(h) and use the respective value for up/down movement - this also affects further calculations in either, case 1 or two in this comment.

[ChaoticEvilDM]

Essentially more complex systems like geo information databases work in a similar matter by overlaying height information in regular instead of dynamic intervals in forms of polygons over a wider area. This is a middle way between the more simple and more complex but more accurate way to gathering these informations and should be supported by the database down to a function level. We should check whether or not this is actually the case and if so, if it can be utilized by using less complex polygons to frame such a heighend surface.

The calculations should not be much more complicated as a polygons consists of Pₙ -> Pₙ+₁ lines where (X|Y) of Pₙ is known. Therefore a simple formula can tell us the intersections between our line m and a height limiting polygon, much in the likes of what we are using right now.

This solution is preferred even though it might prove more challenging to implement.

[ChaoticEvilDM]

Solution: Each path is defined by (X|Y)min and (X|Y)max. Using these coordinates, a bounding box using (X|Y)min and (X|Y)max is defined. This can only be done for straights or Bézier curves, if the curve is not out of bounds for (X|Y)min and (X|Y)max.

Each Box (B) can have a number of parent boxes:

• Each box that contains (P) B fully, is a parent box
• Each box that intersects (L) B, is a linked box
• Each box thats within (C) B is a child box

Boxes are build in trees. If a new box is added, the tree can be walked down, using the B(Xmin|Ymin,Xmax|Ymax) to integrate it into the tree and update the subboxes.

Once the tree is created, OTTP needs to run a calculation on applied changes. Example: Given are Boxes A, B, C, D, E, F, G

` A { child=B,C,F }

B { parent=A linked=C child=D }

C { parent=A linked=B,D }

D { parent=B linked=C child=E }

E { parent=D }

F { parent=A child=G }

G { parent=F } ` A change in C invokes a check for A,B,D,E A change in E invokes a check for A,B,C,D A change in F invokes a check for A,G

This drastically reduces the number of nodes that have to be checked when calculating the intersections between regional objects, e.G. mountains, and pathing. Once calculated, the pathing data can be stored and used for the map. Adding new nodes only invokes a recalculation for PLCs that are directly affected in the tree. This makes updating a lot faster.