summaryrefslogtreecommitdiff
path: root/apps/plugins/doom/doomdata.h
blob: f56524e6cdf0d0d13ae0d45aef67e3fbb9fc02e6 (plain)
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
// Emacs style mode select   -*- C++ -*-
//-----------------------------------------------------------------------------
//
// $Id$
//
// Copyright (C) 1993-1996 by id Software, Inc.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// DESCRIPTION:
//  all external data is defined here
//  most of the data is loaded into different structures at run time
//  some internal structures shared by many modules are here
//
//-----------------------------------------------------------------------------

#ifndef __DOOMDATA__
#define __DOOMDATA__

// The most basic types we use, portability.
#include "doomtype.h"

// Some global defines, that configure the game.
#include "doomdef.h"

#include "rockmacros.h"

//
// Map level types.
// The following data structures define the persistent format
// used in the lumps of the WAD files.
//

// Lump order in a map WAD: each map needs a couple of lumps
// to provide a complete scene geometry description.
enum {
   ML_LABEL,             // A separator, name, ExMx or MAPxx
   ML_THINGS,            // Monsters, items..
   ML_LINEDEFS,          // LineDefs, from editing
   ML_SIDEDEFS,          // SideDefs, from editing
   ML_VERTEXES,          // Vertices, edited and BSP splits generated
   ML_SEGS,              // LineSegs, from LineDefs split by BSP
   ML_SSECTORS,          // SubSectors, list of LineSegs
   ML_NODES,             // BSP nodes
   ML_SECTORS,           // Sectors, from editing
   ML_REJECT,            // LUT, sector-sector visibility
   ML_BLOCKMAP           // LUT, motion clipping, walls/grid element
};

// A single Vertex.
typedef struct {
   short x,y;
} PACKEDATTR mapvertex_t;

// A SideDef, defining the visual appearance of a wall,
// by setting textures and offsets.
typedef struct {
   short textureoffset;
   short rowoffset;
   char  toptexture[8];
   char  bottomtexture[8];
   char  midtexture[8];
   short sector;  // Front sector, towards viewer.
} PACKEDATTR mapsidedef_t;

// A LineDef, as used for editing, and as input to the BSP builder.

typedef struct {
   short v1;
   short v2;
   short flags;
   short special;
   short tag;
   short sidenum[2];  // sidenum[1] will be -1 if one sided
} PACKEDATTR maplinedef_t;


//
// LineDef attributes.
//

// Solid, is an obstacle.
#define ML_BLOCKING  1

// Blocks monsters only.
#define ML_BLOCKMONSTERS 2

// Backside will not be present at all
//  if not two sided.
#define ML_TWOSIDED  4

// If a texture is pegged, the texture will have
// the end exposed to air held constant at the
// top or bottom of the texture (stairs or pulled
// down things) and will move with a height change
// of one of the neighbor sectors.
// Unpegged textures allways have the first row of
// the texture at the top pixel of the line for both
// top and bottom textures (use next to windows).

// upper texture unpegged
#define ML_DONTPEGTOP  8

// lower texture unpegged
#define ML_DONTPEGBOTTOM 16

// In AutoMap: don't map as two sided: IT'S A SECRET!
#define ML_SECRET  32

// Sound rendering: don't let sound cross two of these.
#define ML_SOUNDBLOCK  64

// Don't draw on the automap at all.
#define ML_DONTDRAW  128

// Set if already seen, thus drawn in automap.
#define ML_MAPPED  256

//jff 3/21/98 Set if line absorbs use by player
//allow multiple push/switch triggers to be used on one push
#define ML_PASSUSE      512

// Sector definition, from editing.
typedef struct {
   short floorheight;
   short ceilingheight;
   char  floorpic[8];
   char  ceilingpic[8];
   short lightlevel;
   short special;
   short tag;
} PACKEDATTR mapsector_t;

// SubSector, as generated by BSP.
typedef struct {
   unsigned short numsegs;
   unsigned short firstseg;    // Index of first one; segs are stored sequentially.
} PACKEDATTR mapsubsector_t;

// LineSeg, generated by splitting LineDefs
// using partition lines selected by BSP builder.
typedef struct {
   short v1;
   short v2;
   short angle;
   short linedef;
   short side;
   short offset;
} PACKEDATTR mapseg_t;

// BSP node structure.

// Indicate a leaf.
#define NF_SUBSECTOR 0x8000

typedef struct {
   short x;  // Partition line from (x,y) to x+dx,y+dy)
   short y;
   short dx;
   short dy;
   // Bounding box for each child, clip against view frustum.
   short bbox[2][4];
   // If NF_SUBSECTOR its a subsector, else it's a node of another subtree.
   unsigned short children[2];
} PACKEDATTR mapnode_t;

// Thing definition, position, orientation and type,
// plus skill/visibility flags and attributes.
typedef struct {
   short x;
   short y;
   short angle;
   short type;
   short options;
} PACKEDATTR mapthing_t;



#endif   // __DOOMDATA__
span class="hl kwb">int bridge; }; struct findloopstate *findloop_new_state(int nvertices) { /* * Allocate a findloopstate structure for each vertex, and one * extra one at the end which will be the overall root of a * 'super-tree', which links the whole graph together to make it * as easy as possible to iterate over all the connected * components. */ return snewn(nvertices + 1, struct findloopstate); } void findloop_free_state(struct findloopstate *state) { sfree(state); } bool findloop_is_loop_edge(struct findloopstate *pv, int u, int v) { /* * Since the algorithm is intended for finding bridges, and a * bridge must be part of any spanning tree, it follows that there * is at most one bridge per vertex. * * Furthermore, by finding a _rooted_ spanning tree (so that each * bridge is a parent->child link), you can find an injection from * bridges to vertices (namely, map each bridge to the vertex at * its child end). * * So if the u-v edge is a bridge, then either v was u's parent * when the algorithm ran and we set pv[u].bridge = v, or vice * versa. */ return !(pv[u].bridge == v || pv[v].bridge == u); } static bool findloop_is_bridge_oneway( struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices) { int r, total, below; if (pv[u].bridge != v) return false; r = pv[u].component_root; total = pv[r].maxindex - pv[r].minindex + 1; below = pv[u].maxindex - pv[u].minindex + 1; if (u_vertices) *u_vertices = below; if (v_vertices) *v_vertices = total - below; return true; } bool findloop_is_bridge( struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices) { return (findloop_is_bridge_oneway(pv, u, v, u_vertices, v_vertices) || findloop_is_bridge_oneway(pv, v, u, v_vertices, u_vertices)); } bool findloop_run(struct findloopstate *pv, int nvertices, neighbour_fn_t neighbour, void *ctx) { int u, v, w, root, index; int nbridges, nedges; root = nvertices; /* * First pass: organise the graph into a rooted spanning forest. * That is, a tree structure with a clear up/down orientation - * every node has exactly one parent (which may be 'root') and * zero or more children, and every parent-child link corresponds * to a graph edge. * * (A side effect of this is to find all the connected components, * which of course we could do less confusingly with a dsf - but * then we'd have to do that *and* build the tree, so it's less * effort to do it all at once.) */ for (v = 0; v <= nvertices; v++) { pv[v].parent = root; pv[v].child = -2; pv[v].sibling = -1; pv[v].visited = false; } pv[root].child = -1; nedges = 0; debug(("------------- new find_loops, nvertices=%d\n", nvertices)); for (v = 0; v < nvertices; v++) { if (pv[v].parent == root) { /* * Found a new connected component. Enumerate and treeify * it. */ pv[v].sibling = pv[root].child; pv[root].child = v; pv[v].component_root = v; debug(("%d is new child of root\n", v)); u = v; while (1) { if (!pv[u].visited) { pv[u].visited = true; /* * Enumerate the neighbours of u, and any that are * as yet not in the tree structure (indicated by * child==-2, and distinct from the 'visited' * flag) become children of u. */ debug((" component pass: processing %d\n", u)); for (w = neighbour(u, ctx); w >= 0; w = neighbour(-1, ctx)) { debug((" edge %d-%d\n", u, w)); if (pv[w].child == -2) { debug((" -> new child\n")); pv[w].child = -1; pv[w].sibling = pv[u].child; pv[w].parent = u; pv[w].component_root = pv[u].component_root; pv[u].child = w; } /* While we're here, count the edges in the whole * graph, so that we can easily check at the end * whether all of them are bridges, i.e. whether * no loop exists at all. */ if (w > u) /* count each edge only in one direction */ nedges++; } /* * Now descend in depth-first search. */ if (pv[u].child >= 0) { u = pv[u].child; debug((" descending to %d\n", u)); continue; } } if (u == v) { debug((" back at %d, done this component\n", u)); break; } else if (pv[u].sibling >= 0) { u = pv[u].sibling; debug((" sideways to %d\n", u)); } else { u = pv[u].parent; debug((" ascending to %d\n", u)); } } } } /* * Second pass: index all the vertices in such a way that every * subtree has a contiguous range of indices. (Easily enough done, * by iterating through the tree structure we just built and * numbering its elements as if they were those of a sorted list.) * * For each vertex, we compute the min and max index of the * subtree starting there. * * (We index the vertices in preorder, per Tarjan's original * description, so that each vertex's min subtree index is its own * index; but that doesn't actually matter; either way round would * do. The important thing is that we have a simple arithmetic * criterion that tells us whether a vertex is in a given subtree * or not.) */ debug(("--- begin indexing pass\n")); index = 0; for (v = 0; v < nvertices; v++) pv[v].visited = false; pv[root].visited = true; u = pv[root].child; while (1) { if (!pv[u].visited) { pv[u].visited = true; /* * Index this node. */ pv[u].minindex = pv[u].index = index; debug((" vertex %d <- index %d\n", u, index)); index++; /* * Now descend in depth-first search. */ if (pv[u].child >= 0) { u = pv[u].child; debug((" descending to %d\n", u)); continue; } } if (u == root) { debug((" back at %d, done indexing\n", u)); break; } /* * As we re-ascend to here from its children (or find that we * had no children to descend to in the first place), fill in * its maxindex field. */ pv[u].maxindex = index-1; debug((" vertex %d <- maxindex %d\n", u, pv[u].maxindex)); if (pv[u].sibling >= 0) { u = pv[u].sibling; debug((" sideways to %d\n", u)); } else { u = pv[u].parent; debug((" ascending to %d\n", u)); } } /* * We're ready to generate output now, so initialise the output * fields. */ for (v = 0; v < nvertices; v++) pv[v].bridge = -1; /* * Final pass: determine the min and max index of the vertices * reachable from every subtree, not counting the link back to * each vertex's parent. Then our criterion is: given a vertex u, * defining a subtree consisting of u and all its descendants, we * compare the range of vertex indices _in_ that subtree (which is * just the minindex and maxindex of u) with the range of vertex * indices in the _neighbourhood_ of the subtree (computed in this * final pass, and not counting u's own edge to its parent), and * if the latter includes anything outside the former, then there * must be some path from u to outside its subtree which does not * go through the parent edge - i.e. the edge from u to its parent * is part of a loop. */ debug(("--- begin min-max pass\n")); nbridges = 0; for (v = 0; v < nvertices; v++) pv[v].visited = false; u = pv[root].child; pv[root].visited = true; while (1) { if (!pv[u].visited) { pv[u].visited = true; /* * Look for vertices reachable directly from u, including * u itself. */ debug((" processing vertex %d\n", u)); pv[u].minreachable = pv[u].maxreachable = pv[u].minindex; for (w = neighbour(u, ctx); w >= 0; w = neighbour(-1, ctx)) { debug((" edge %d-%d\n", u, w)); if (w != pv[u].parent) { int i = pv[w].index; if (pv[u].minreachable > i) pv[u].minreachable = i; if (pv[u].maxreachable < i) pv[u].maxreachable = i; } } debug((" initial min=%d max=%d\n", pv[u].minreachable, pv[u].maxreachable)); /* * Now descend in depth-first search. */ if (pv[u].child >= 0) { u = pv[u].child; debug((" descending to %d\n", u)); continue; } } if (u == root) { debug((" back at %d, done min-maxing\n", u)); break; } /* * As we re-ascend to this vertex, go back through its * immediate children and do a post-update of its min/max. */ for (v = pv[u].child; v >= 0; v = pv[v].sibling) { if (pv[u].minreachable > pv[v].minreachable) pv[u].minreachable = pv[v].minreachable; if (pv[u].maxreachable < pv[v].maxreachable) pv[u].maxreachable = pv[v].maxreachable; } debug((" postorder update of %d: min=%d max=%d (indices %d-%d)\n", u, pv[u].minreachable, pv[u].maxreachable, pv[u].minindex, pv[u].maxindex)); /* * And now we know whether each to our own parent is a bridge. */ if ((v = pv[u].parent) != root) { if (pv[u].minreachable >= pv[u].minindex && pv[u].maxreachable <= pv[u].maxindex) { /* Yes, it's a bridge. */ pv[u].bridge = v; nbridges++; debug((" %d-%d is a bridge\n", v, u)); } else { debug((" %d-%d is not a bridge\n", v, u)); } } if (pv[u].sibling >= 0) { u = pv[u].sibling; debug((" sideways to %d\n", u)); } else { u = pv[u].parent; debug((" ascending to %d\n", u)); } } debug(("finished, nedges=%d nbridges=%d\n", nedges, nbridges)); /* * Done. */ return nbridges < nedges; } /* * Appendix: the long and painful history of loop detection in these puzzles * ========================================================================= * * For interest, I thought I'd write up the five loop-finding methods * I've gone through before getting to this algorithm. It's a case * study in all the ways you can solve this particular problem * wrongly, and also how much effort you can waste by not managing to * find the existing solution in the literature :-( * * Vertex dsf * ---------- * * Initially, in puzzles where you need to not have any loops in the * solution graph, I detected them by using a dsf to track connected * components of vertices. Iterate over each edge unifying the two * vertices it connects; but before that, check if the two vertices * are _already_ known to be connected. If so, then the new edge is * providing a second path between them, i.e. a loop exists. * * That's adequate for automated solvers, where you just need to know * _whether_ a loop exists, so as to rule out that move and do * something else. But during play, you want to do better than that: * you want to _point out_ the loops with error highlighting. * * Graph pruning * ------------- * * So my second attempt worked by iteratively pruning the graph. Find * a vertex with degree 1; remove that edge; repeat until you can't * find such a vertex any more. This procedure will remove *every* * edge of the graph if and only if there were no loops; so if there * are any edges remaining, highlight them. * * This successfully highlights loops, but not _only_ loops. If the * graph contains a 'dumb-bell' shaped subgraph consisting of two * loops connected by a path, then we'll end up highlighting the * connecting path as well as the loops. That's not what we wanted. * * Vertex dsf with ad-hoc loop tracing * ----------------------------------- * * So my third attempt was to go back to the dsf strategy, only this * time, when you detect that a particular edge connects two * already-connected vertices (and hence is part of a loop), you try * to trace round that loop to highlight it - before adding the new * edge, search for a path between its endpoints among the edges the * algorithm has already visited, and when you find one (which you * must), highlight the loop consisting of that path plus the new * edge. * * This solves the dumb-bell problem - we definitely now cannot * accidentally highlight any edge that is *not* part of a loop. But * it's far from clear that we'll highlight *every* edge that *is* * part of a loop - what if there were multiple paths between the two * vertices? It would be difficult to guarantee that we'd always catch * every single one. * * On the other hand, it is at least guaranteed that we'll highlight * _something_ if any loop exists, and in other error highlighting * situations (see in particular the Tents connected component * analysis) I've been known to consider that sufficient. So this * version hung around for quite a while, until I had a better idea. * * Face dsf * -------- * * Round about the time Loopy was being revamped to include non-square * grids, I had a much cuter idea, making use of the fact that the * graph is planar, and hence has a concept of faces. * * In Loopy, there are really two graphs: the 'grid', consisting of * all the edges that the player *might* fill in, and the solution * graph of the edges the player actually *has* filled in. The * algorithm is: set up a dsf on the *faces* of the grid. Iterate over * each edge of the grid which is _not_ marked by the player as an * edge of the solution graph, unifying the faces on either side of * that edge. This groups the faces into connected components. Now, * there is more than one connected component iff a loop exists, and * moreover, an edge of the solution graph is part of a loop iff the * faces on either side of it are in different connected components! * * This is the first algorithm I came up with that I was confident * would successfully highlight exactly the correct set of edges in * all cases. It's also conceptually elegant, and very easy to * implement and to be confident you've got it right (since it just * consists of two very simple loops over the edge set, one building * the dsf and one reading it off). I was very pleased with it. * * Doing the same thing in Slant is slightly more difficult because * the set of edges the user can fill in do not form a planar graph * (the two potential edges in each square cross in the middle). But * you can still apply the same principle by considering the 'faces' * to be diamond-shaped regions of space around each horizontal or * vertical grid line. Equivalently, pretend each edge added by the * player is really divided into two edges, each from a square-centre * to one of the square's corners, and now the grid graph is planar * again. * * However, it fell down when - much later - I tried to implement the * same algorithm in Net. * * Net doesn't *absolutely need* loop detection, because of its system * of highlighting squares connected to the source square: an argument * involving counting vertex degrees shows that if any loop exists, * then it must be counterbalanced by some disconnected square, so * there will be _some_ error highlight in any invalid grid even * without loop detection. However, in large complicated cases, it's * still nice to highlight the loop itself, so that once the player is * clued in to its existence by a disconnected square elsewhere, they * don't have to spend forever trying to find it. * * The new wrinkle in Net, compared to other loop-disallowing puzzles, * is that it can be played with wrapping walls, or - topologically * speaking - on a torus. And a torus has a property that algebraic * topologists would know of as a 'non-trivial H_1 homology group', * which essentially means that there can exist a loop on a torus * which *doesn't* separate the surface into two regions disconnected * from each other. * * In other words, using this algorithm in Net will do fine at finding * _small_ localised loops, but a large-scale loop that goes (say) off * the top of the grid, back on at the bottom, and meets up in the * middle again will not be detected. * * Footpath dsf * ------------ * * To solve this homology problem in Net, I hastily thought up another * dsf-based algorithm. * * This time, let's consider each edge of the graph to be a road, with * a separate pedestrian footpath down each side. We'll form a dsf on * those imaginary segments of footpath. * * At each vertex of the graph, we go round the edges leaving that * vertex, in order around the vertex. For each pair of edges adjacent * in this order, we unify their facing pair of footpaths (e.g. if * edge E appears anticlockwise of F, then we unify the anticlockwise * footpath of F with the clockwise one of E) . In particular, if a * vertex has degree 1, then the two footpaths on either side of its * single edge are unified. * * Then, an edge is part of a loop iff its two footpaths are not * reachable from one another. * * This algorithm is almost as simple to implement as the face dsf, * and it works on a wider class of graphs embedded in plane-like * surfaces; in particular, it fixes the torus bug in the face-dsf * approach. However, it still depends on the graph having _some_ sort * of embedding in a 2-manifold, because it relies on there being a * meaningful notion of 'order of edges around a vertex' in the first * place, so you couldn't use it on a wildly nonplanar graph like the * diamond lattice. Also, more subtly, it depends on the graph being * embedded in an _orientable_ surface - and that's a thing that might * much more plausibly change in future puzzles, because it's not at * all unlikely that at some point I might feel moved to implement a * puzzle that can be played on the surface of a Mobius strip or a * Klein bottle. And then even this algorithm won't work. * * Tarjan's bridge-finding algorithm * --------------------------------- * * And so, finally, we come to the algorithm above. This one is pure * graph theory: it doesn't depend on any concept of 'faces', or 'edge * ordering around a vertex', or any other trapping of a planar or * quasi-planar graph embedding. It should work on any graph * whatsoever, and reliably identify precisely the set of edges that * form part of some loop. So *hopefully* this long string of failures * has finally come to an end... */