-
Notifications
You must be signed in to change notification settings - Fork 0
/
mapindexreduction.html
191 lines (159 loc) · 15.7 KB
/
mapindexreduction.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
<!DOCTYPE html>
<html lang="en-us">
<head>
<title>Marathon Mapmaking: Reducing Map Index Use</title>
<link rel="stylesheet" type="text/css" href="https://code.cdn.mozilla.net/fonts/fira.css">
<link rel="stylesheet" type="text/css" href="css.css">
<script>
function sortTable(table, col, reverse) {
var tb = table.tBodies[0], // use `<tbody>` to ignore `<thead>` and `<tfoot>` rows
tr = Array.prototype.slice.call(tb.rows, 0), // put rows into array
i;
reverse = -((+reverse) || -1);
tr = tr.sort(function (a, b) { // sort rows
return reverse // `-1 *` if want opposite order
* (a.cells[col].textContent.trim() // using `.textContent.trim()` for test
.localeCompare(b.cells[col].textContent.trim(), undefined, {numeric: true})
);
});
for(i = 0; i < tr.length; ++i) tb.appendChild(tr[i]); // append each row in order
}
function makeSortable(table) {
var th = table.tHead, i;
th && (th = th.rows[0]) && (th = th.cells);
if (th) i = th.length;
else return; // if no `<thead>` then do nothing
while (--i >= 0) (function (i) {
var dir = 1;
th[i].addEventListener('click', function () {sortTable(table, i, (dir = 1 - dir))});
}(i));
}
function makeAllSortable(parent) {
parent = parent || document.body;
var t = parent.getElementsByTagName('table'), i = t.length;
while (--i >= 0) makeSortable(t[i]);
}
window.onload = function () {makeAllSortable();};
</script>
</head>
<body>
<header>
<h1><em>Marathon</em> Mapmaking: Reducing Map Index Use</h1>
<p>A supplement to my <a href="mapmaking.html">advanced <em>Marathon</em> Aleph One mapmaking guide</a>, though if you’re new to mapmaking, you should definitely start with my <a href="mapmaking101.html">beginners’ guide</a>. This is also something of a follow-up to a <a href="mapcomplexity.html">case study I wrote on map complexity</a>.</p>
<p>Please <a href="aboutme.html">contact me</a> if you notice any errors or omissions.</p>
<h1 id="contents">Table of Contents</h1>
<ol class="toclite">
<li><a href="#top">Intro</a></li>
<li><a href="#contents">Table of Contents</a> (you’re looking at it)</li>
<li><a href="#outofindices">I ran out of map indices. Wat do?</a></li>
<li><a href="#polygonpruning">Prune Polygons Where Possible</a></li>
<li><a href="#principles">Principles of Pruning</a></li>
<li><a href="#pitfalls">Potential Pitfalls of Pruning</a></li>
</ol>
<h1 id="outofindices">I ran out of map indices. Wat do?</h1>
<p>In any case, a problem that has plagued every creator of sufficiently complex <em>Marathon</em> Aleph One maps is the limit of 65,536 map indices, the primary factor that limits map complexity in the engine. I explain the matter <a href="mapmaking.html#generalmapmaking">at greater length</a> in my general guide, but in short, each vertex, each line, each polygon, each line shorter than 0.5 World Units (polygon exclusion zones, used to calculate lines the player cannot cross), each platform, and each polygon within a 10 World Unit X/Y radius of each sound object uses a map index. (<strong>Note:</strong> Take this list and all map index totals listed here with a grain of salt – the list may not be complete, and I may not have every factor exactly right. I plan to do a deep dive into the source code within the coming weeks.) 65,536 initially sounds like a lot, but this all adds up quickly!</p>
<p>Unfortunately, if you run out of map indices, your only choice is to simplify your level – otherwise, it won’t even load due to an assertion failure. If you have an easy way to split it into two levels without compromising the mission or the flow, that’s by far the optimal choice, as it allows you to leave its detail intact. (The sole caveat is that you’ll need to be sure any geometry shared between both levels remains consistent, or it’ll spoil the effect of them being connected.)</p>
<p>If that isn’t an option, you’ll have to reduce the level’s count of one or more of the following:</p>
<ul>
<li>Polygons</li>
<li>Lines</li>
<li>Vertices</li>
<li>Platforms</li>
<li>Polygon exclusion zones (lines shorter than 0.5 World Units)</li>
<li>Sound objects</li>
</ul>
<p>It may seem tempting to prune sound objects first, as they are by far the largest user of map indices, but I’d advise caution in doing so – sudden transitions from one ‘sound region’ to another can be jarring. Aleph One 1.7’s new OpenAL sound engine actually lessens this problem somewhat by preventing sounds from suddenly <em>cutting off</em> when the player crosses from one boundary to another; however, they still suddenly <em>start up</em>, so only half the problem has been solved.</p>
<h1 id="polygonpruning">Prune Polygons Where Possible</h1>
<p>More importantly, though, you almost certainly didn’t fill polygons as efficiently as you could’ve. I mentioned in my <a href="mapcomplexity.html#monument">case study on map complexity</a> that ‘Monument to All Your Sins’ (a massive level from RyokoTK’s brilliant net map pack <em><a href="https://simplici7y.com/items/starlight/" target="_blank">Starlight</a></em>) has 1,843 polygons. In addition, it has 3,277 vertices and 5,171 lines.</p>
<p>Before I proceed here, I want to be extremely clear that the following is not in any sense meant to throw shade at Ryoko, who is one of the most prolific and consistently brilliant level designers ever to create <em>Marathon</em> content. I’m not on his level and doubt I ever will be. That said, the solo adaptation I created for <em>Marathon Chronicles</em>, from which I removed none of the original’s visual complexity, contains 1,784 polygons, 3,271 vertices, and 5,106 lines (a savings of 59 polygons, 6 vertices, and 65 lines). The image below (click to enlarge) compares the two versions to show where I pruned polygons:</p>
<div class="image"><a href="monument-to-nonexistence.gif" target="_blank"><img src="monument-to-nonexistence.gif" title="I will destroy extraneous polygons! I will create a monument to fear, surprise, ruthless efficiency, an almost fanatical devotion to the pope, and nice, red uniforms… oh, bugger" width="512" /></a></div>
<p>The fact that I only found 59 polygons to prune is actually quite impressive. Here are a few levels from various editions of <em>Where Monsters Are in Dreams</em> with their initial polygon counts, the polygon counts I pruned them to, and the number of polygons I pruned. (In all cases, the levels’ appearance was not visibly changed.)</p>
<table>
<thead>
<tr>
<th>Level</th>
<th class="right">Ante</th>
<th class="right">Post</th>
<th class="right">Δ</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>We Were Speaking of Fate</strong></td>
<td class="integer">1,705</td>
<td class="integer">1,500</td>
<td class="integer">−205</td>
</tr>
<tr>
<td><strong>Cause & Effect</strong> (first iteration)</td>
<td class="integer">2,466</td>
<td class="integer">2,222</td>
<td class="integer">−244</td>
</tr>
<tr>
<td><strong>Burning Memories</strong></td>
<td class="integer">2,217</td>
<td class="integer">2,020</td>
<td class="integer">−197</td>
</tr>
<tr>
<td><strong>Cast Your Fate to the Stars</strong></td>
<td class="integer">1,950</td>
<td class="integer">1,768</td>
<td class="integer">−182</td>
</tr>
</tbody>
</table>
<p>Lest anyone think I’m letting myself off the hook for inefficient polygon use, ‘Cast Your Fate to the Stars’ is my level!</p>
<p>In any case, I’m not saying this because I think it demonstrates any kind of talent on my part (for one thing, as El Estepario Siberiano, arguably the greatest drummer alive, has argued, <a href="https://youtu.be/iproGrE6rCg" target="_blank">talent is a lie</a>); it simply requires attention to detail and understanding of geometry, both of which can be learned. I’m revealing this solely to indicate how many polygons it’s often possible to remove without negatively impacting a map’s appearance. Furthermore, not merely will pruning polygons reduce a level’s map index use, but it will also improve its performance.</p>
<p class="sectionbreak"><a href="#top">Back to top</a> · <a href="mapmaking101.html">Mapmaking (basic)</a> · <a href="mapmaking.html">Mapmaking (advanced)</a> · <a href="aboutme.html">Contact me</a> · <a href="/">Website index</a></p>
<h1 id="principles">Principles of Pruning</h1>
<p>A few principles I find have served me well:</p>
<ul>
<li>Look at the floor and ceiling heights. If you have a large cluster of polygons at the same height, they may be inefficiently filled.</li>
<li>Triangles are rarely the most efficient way to fill a space. Examine them especially closely.</li>
<li>Moving a point by an amount that’s imperceptible to humans can often change a convex angle into a concave angle, thus allowing two polygons to be combined into one.</li>
<li>Pruning lines and vertices that are attached to polygons is at least as important as pruning polygons, though it’s harder to keep track of since Weland doesn’t print those at the bottom of each level.
<ul>
<li>To find out how many lines and vertices your map has, draw a new line unconnected to any other line. Select the line; its index will be your line count. Select the vertex you drew <em>first</em>; its index will be your vertex count. Now delete it. (Lines and vertices that are unconnected to any polygon don’t actually count to the map index count, so this won’t give you an exact count, but it’ll get you a rough estimate.)</li>
</ul>
</li>
<li>Pruning lines that are shorter than 0.5 World Units is more important, since they also use up polygon exclusion zones.</li>
<li>Pruning clusters of polygons that are close to sound objects is most important of all – as I’ve said elsewhere, every single polygon within a 10 World Unit X/Y radius of a sound object uses up a map index. (Height doesn’t matter at all here.)</li>
<li>Learn to recognize patterns. Here are three example patterns I find myself running into <em>all the time</em>. (We’ll assume that none of the pitfalls mentioned in the section below this one apply to any of these cases.)
<div class="image"><img src="example-savings.png" width="465" height="401" title="Three examples of geometry that can be filled more efficiently. (Note that 3a does not actually save map indices.)"/></div>
<ol>
<li>Our initial instinct might be to keep polygon sizes relatively constant here, but by redrawing the area so that the leftmost protrusion is one polygon and the remaining space is another, we save ourselves not only one polygon, but also three lines and two vertices – if I understand how map indices are allocated correctly, this saves us six.</li>
<li>It’s often tempting to draw split polygons at every polygon boundary, but they can often be combined. In this case, we save ourselves four vertices, eight lines, four polygons, and possibly four polygon exclusion zones – again, if I understand map index allocation correctly (which may not be the case), this saves us a net <em>twenty</em>.</li>
<li>There are two options here, and they are not created equal:
<ol class="loweralpha">
<li>Again, our instinct might be to keep polygon sizes equal, but filling this area with two equal-sized polygons actually <em>adds</em> a vertex while not reducing our line count – thus using the same number of indices we started with!</li>
<li>Simply combining the leftmost polygon with the bottom-most polygon, on the other hand, saves us both a polygon and a line. This represents the most modest savings among these three examples (two map indices), but it’s also the most straightforward: it merely requires deleting a line and refilling a polygon. (You could also combine the rightmost polygon with the bottom-most one; of course, you can’t do both.)</li>
</ol>
</li>
</ol>
</li>
</ul>
<p class="sectionbreak"><a href="#top">Back to top</a> · <a href="mapmaking101.html">Mapmaking (basic)</a> · <a href="mapmaking.html">Mapmaking (advanced)</a> · <a href="aboutme.html">Contact me</a> · <a href="/">Website index</a></p>
<h1 id="pitfalls">Potential Pitfalls of Pruning</h1>
<p>There are, of course, potential pitfalls as well:</p>
<ul>
<li>The floor and ceiling heights should match.</li>
<li>The floor and ceiling textures should match.</li>
<li>The liquid assignments should match.</li>
<li>The floor, ceiling, and liquid lights should match (or at least be indistinguishable).</li>
<li>The ambient and random sounds on each polygon should match (or at least be indistinguishable).</li>
<li>The polygon types (and, if applicable, their permutations) should either match or be possible to reassign in a way that meaningfully preserves their gameplay effect.</li>
<li>Redrawing the polygons must not mess up movement either for the player or monsters. (If you need a refresher on how monsters move, see this <a href="https://citadel.lhowon.org/litterbox/Forge/hastursworkshop/things2.html" target="_blank">Hastur’s Workshop piece</a> I linked above.)</li>
<li>You’ll have to recreate any objects that occupied these polygons after remaking them.</li>
<li>If you have any terminals that use intralevel teleports, you’ll probably have to redo them after deleting and remaking polygons.</li>
<li>If any teleporters took players to one of these polygons, you’ll have to reassign them.</li>
<li>If there was a platform on one of these polygons, you’ll have to remake it.
<ul><li>If any platform switches referred to such a platform, you’ll have to reassign them.</li></ul>
</li>
<li>If redrawing the geometry causes ‘bouncy walls’ that eject players upon collisions, you may wish to avoid doing so. (Bouncy walls are especially likely to happen with narrow polygons [<1/4 WU width] or heavily acute angles, though not all bouncy walls are caused by acute angles or narrow polygons, and not all narrow polygons or acute angles cause bouncy walls.)</li>
<li>The overhead map uses polygon index to determine display order, which can mess up aesthetics – however, I should note that as conscious of aesthetics as I am, even I don’t pay a ton of attention to this. (I plan to write a Weland plugin to swap two polygons’ indices soon™.)</li>
</ul>
<p>With all this in mind (not to mention what a pain it is to retexture areas after deleting and remaking polygons – Weland’s ‘Remember Deleted Sides’ only works some of the time), I can’t blame anyone for not finding polygon pruning to be the most attractive solution. Ideally, you can prevent the need to prune by looking closely at your map geometry before you start texturing to begin with. However, I’m surely not the only person who’s planned one thing for a level, then wound up doing something entirely different that required fewer polygons than expected.</p>
<p>In any case, as time-consuming and frustrating as this process can be, it’s still – to me at least – far preferable to having to sacrifice map complexity. Hopefully this helps.</p>
<p class="sectionbreak"><a href="#top">Back to top</a> · <a href="mapmaking101.html">Mapmaking (basic)</a> · <a href="mapmaking.html">Mapmaking (advanced)</a> · <a href="aboutme.html">Contact me</a> · <a href="/">Website index</a></p>