Line data Source code
1 : /**
2 : * Returns the wall piece entities needed to construct a wall between start.pos and end.pos. Assumes start.pos != end.pos.
3 : * The result is an array of objects, each one containing the following information about a single wall piece entity:
4 : * - 'template': the template name of the entity
5 : * - 'pos': position of the entity, as an object with keys 'x' and 'z'
6 : * - 'angle': orientation of the entity, as an angle in radians
7 : *
8 : * All the pieces in the resulting array are ordered left-to-right (or right-to-left) as they appear in the physical wall.
9 : *
10 : * @param placementData Object that associates the wall piece template names with information about those kinds of pieces.
11 : * Expects placementData[templateName].templateData to contain the parsed template information about
12 : * the template whose filename is <i>templateName</i>.
13 : * @param wallSet Object that primarily holds the template names for the supported wall pieces in this set (under the
14 : * 'templates' key), as well as the min and max allowed overlap factors (see GetWallSegmentsRec). Expected
15 : * to contain template names for keys "long" (long wall segment), "medium" (medium wall segment), "short"
16 : * (short wall segment), "tower" (intermediate tower between wall segments), "gate" (replacement for long
17 : * walls).
18 : * @param start Object holding the starting position of the wall. Must contain keys 'x' and 'z'.
19 : * @param end Object holding the ending position of the wall. Must contains keys 'x' and 'z'.
20 : */
21 : function GetWallPlacement(placementData, wallSet, start, end)
22 : {
23 0 : let candidateSegments = ["long", "medium", "short"].map(size => ({
24 : "template": wallSet.templates[size],
25 : "len": placementData[wallSet.templates[size]].templateData.wallPiece.length
26 : }));
27 :
28 0 : let towerWidth = placementData[wallSet.templates.tower].templateData.wallPiece.length;
29 :
30 0 : let dir = {
31 : "x": end.pos.x - start.pos.x,
32 : "z": end.pos.z - start.pos.z
33 : };
34 :
35 0 : let len = Math.sqrt(dir.x * dir.x + dir.z * dir.z);
36 :
37 : // we'll need room for at least our starting and ending towers to fit next to eachother
38 0 : if (len <= towerWidth)
39 0 : return [];
40 :
41 0 : let placement = GetWallSegmentsRec(
42 : len,
43 : candidateSegments,
44 : wallSet.minTowerOverlap,
45 : wallSet.maxTowerOverlap,
46 : towerWidth,
47 : 0, []
48 : );
49 :
50 : // TODO: make sure intermediate towers are spaced out far enough for their obstructions to not overlap, implying that
51 : // tower's wallpiece lengths should be > their obstruction width, which is undesirable because it prevents towers with
52 : // wide bases
53 0 : if (!placement)
54 : {
55 0 : error("No placement possible for distance=" +
56 : Math.round(len * 1000) / 1000.0 +
57 : ", minOverlap=" + wallSet.minTowerOverlap +
58 : ", maxOverlap=" + wallSet.maxTowerOverlap);
59 :
60 0 : return [];
61 : }
62 :
63 : // List of chosen candidate segments
64 0 : let placedEntities = placement.segments;
65 :
66 : // placement.r is the remaining distance to target without towers (must be <= (N-1) * towerWidth)
67 0 : let spacing = placement.r / (2 * placedEntities.length);
68 :
69 0 : let dirNormalized = { "x": dir.x / len, "z": dir.z / len };
70 :
71 : // Angle of this wall segment (relative to world-space X/Z axes)
72 0 : let angle = -Math.atan2(dir.z, dir.x);
73 :
74 0 : let progress = 0;
75 0 : let result = [];
76 :
77 0 : for (let i = 0; i < placedEntities.length; ++i)
78 : {
79 0 : let placedEntity = placedEntities[i];
80 :
81 0 : result.push({
82 : "template": placedEntity.template,
83 : "pos": {
84 : "x": start.pos.x + (progress + spacing + placedEntity.len/2) * dirNormalized.x,
85 : "z": start.pos.z + (progress + spacing + placedEntity.len/2) * dirNormalized.z
86 : },
87 : "angle": angle,
88 : });
89 :
90 0 : if (i < placedEntities.length - 1)
91 : {
92 0 : result.push({
93 : "template": wallSet.templates.tower,
94 : "pos": {
95 : "x": start.pos.x + (progress + placedEntity.len + 2 * spacing) * dirNormalized.x,
96 : "z": start.pos.z + (progress + placedEntity.len + 2 * spacing) * dirNormalized.z
97 : },
98 : "angle": angle,
99 : });
100 : }
101 :
102 0 : progress += placedEntity.len + 2 * spacing;
103 : }
104 :
105 0 : return result;
106 : }
107 :
108 : /**
109 : * Helper function for GetWallPlacement. Finds a list of wall segments and the corresponding remaining spacing/overlap
110 : * distance "r" that will suffice to construct a wall of the given distance. It is understood that two extra towers will
111 : * be placed centered at the starting and ending points of the wall.
112 : *
113 : * @param d Total distance between starting and ending points (constant throughout calls).
114 : * @param candidateSegments List of candidate segments (constant throughout calls). Should be ordered longer-to-shorter
115 : * for better execution speed.
116 : * @param minOverlap Minimum overlap factor (constant throughout calls). Must have a value between 0 (meaning walls are
117 : * not allowed to overlap towers) and 1 (meaning they're allowed to overlap towers entirely).
118 : * Must be <= maxOverlap.
119 : * @param maxOverlap Maximum overlap factor (constant throughout calls). Must have a value between 0 (meaning walls are
120 : * not allowed to overlap towers) and 1 (meaning they're allowed to overlap towers entirely).
121 : * Must be >= minOverlap.
122 : * @param t Length of a single tower (constant throughout calls). Acts as buffer space for wall segments (see comments).
123 : * @param distSoFar Sum of all the wall segments' lengths in 'segments'.
124 : * @param segments Current list of wall segments placed.
125 : */
126 : function GetWallSegmentsRec(d, candidateSegments, minOverlap, maxOverlap, t, distSoFar, segments)
127 : {
128 : // The idea is to find a number N of wall segments (excluding towers) so that the sum of their lengths adds up to a
129 : // value that is within certain bounds of the distance 'd' between the starting and ending points of the wall. This
130 : // creates either a positive or negative 'buffer' of space, that can be compensated for by spacing the wall segments
131 : // out away from each other, or inwards, overlapping each other. The spaces or overlaps can then be covered up by
132 : // placing towers on top of them. In this way, the same set of wall segments can be used to span a wider range of
133 : // target distances.
134 : //
135 : // In this function, it is understood that two extra towers will be placed centered at the starting and ending points.
136 : // They are allowed to contribute to the buffer space.
137 : //
138 : // The buffer space equals the difference between d and the sum of the lengths of all the wall segments, and is denoted
139 : // 'r' for 'remaining space'. Positive values of r mean that the walls will need to be spaced out, negative values of r
140 : // mean that they will need to overlap. Clearly, there are limits to how far wall segments can be spaced out or
141 : // overlapped, depending on how much 'buffer space' each tower provides, and how far 'into' towers the wall segments are
142 : // allowed to overlap.
143 : //
144 : // Let 't' signify the width of a tower. When there are N wall segments, then the maximum distance that can be covered
145 : // using only these walls (plus the towers covering up any gaps) is achieved when the walls and towers touch outer-border-
146 : // to-outer-border. Therefore, the maximum value of r is then given by:
147 : //
148 : // rMax = t/2 + (N-1)*t + t/2
149 : // = N*t
150 : //
151 : // where the two half-tower widths are buffer space contributed by the implied towers on the starting and ending points.
152 : // Similarly, a value rMin = -N*t can be derived for the minimal value of r. Note that a value of r = 0 means that the
153 : // wall segment lengths add up to exactly d, meaning that each one starts and ends right in the center of a tower.
154 : //
155 : // Thus, we establish:
156 : // -Nt <= r <= Nt
157 : //
158 : // We can further generalize this by adding in parameters to control the depth to within which wall segments are allowed to
159 : // overlap with a tower. The bounds above assume that a wall segment is allowed to overlap across the entire range of 0
160 : // (not overlapping at all, as in the upper boundary) to 1 (overlapping maximally, as in the lower boundary).
161 : //
162 : // By requiring that walls overlap towers to a degree of at least 0 < minOverlap <= 1, it is clear that this lowers the
163 : // distance that can be maximally reached by the same set of wall segments, compared to the value of minOverlap = 0 that
164 : // we assumed to initially find Nt.
165 : //
166 : // Consider a value of minOverlap = 0.5, meaning that any wall segment must protrude at least halfway into towers; in this
167 : // situation, wall segments must at least touch boundaries or overlap mutually, implying that the sum of their lengths
168 : // must equal or exceed 'd', establishing an upper bound of 0 for r.
169 : // Similarly, consider a value of minOverlap = 1, meaning that any wall segment must overlap towers maximally; this situation
170 : // is equivalent to the one for finding the lower bound -Nt on r.
171 : //
172 : // With the implicit value minOverlap = 0 that yielded the upper bound Nt above, simple interpolation and a similar exercise
173 : // for maxOverlap, we find:
174 : // (1-2*maxOverlap) * Nt <= r <= (1-2*minOverlap) * Nt
175 : //
176 : // To find N segments that satisfy this requirement, we try placing L, M and S wall segments in turn and continue recursively
177 : // as long as the value of r is not within the bounds. If continuing recursively returns an impossible configuration, we
178 : // backtrack and try a wall segment of the next length instead. Note that we should prefer to use the long segments first since
179 : // they can be replaced by gates.
180 :
181 0 : for (let candSegment of candidateSegments)
182 : {
183 0 : segments.push(candSegment);
184 :
185 0 : let newDistSoFar = distSoFar + candSegment.len;
186 0 : let r = d - newDistSoFar;
187 :
188 0 : let rLowerBound = (1 - 2 * maxOverlap) * segments.length * t;
189 0 : let rUpperBound = (1 - 2 * minOverlap) * segments.length * t;
190 :
191 0 : if (r < rLowerBound)
192 : {
193 : // we've allocated too much wall length, pop the last segment and try the next
194 : //warn("Distance so far exceeds target, trying next level");
195 0 : segments.pop();
196 0 : continue;
197 : }
198 0 : else if (r > rUpperBound)
199 : {
200 0 : let recursiveResult = GetWallSegmentsRec(d, candidateSegments, minOverlap, maxOverlap, t, newDistSoFar, segments);
201 0 : if (!recursiveResult)
202 : {
203 : // recursive search with this piece yielded no results, pop it and try the next one
204 0 : segments.pop();
205 0 : continue;
206 : }
207 :
208 0 : return recursiveResult;
209 : }
210 :
211 0 : return { "segments": segments, "r": r };
212 : }
213 :
214 0 : return false;
215 : }
216 :
217 0 : Engine.RegisterGlobal("GetWallPlacement", GetWallPlacement);
|
