// Emacs style mode select -*- C++ -*- //----------------------------------------------------------------------------- // // $Id: P_setup.c,v 1.2 2000/04/30 15:28:24 proff_fs Exp $ // // PRBOOM/GLBOOM (C) Florian 'Proff' Schulze (florian.proff.schulze@gmx.net) // based on // BOOM, a modified and improved DOOM engine // Copyright (C) 1999 by // id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman // // 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. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA // 02111-1307, USA. // // DESCRIPTION: // Do all the WAD I/O, get map description, // set up initial state and misc. LUTs. // //----------------------------------------------------------------------------- static const char rcsid[] = "$Id: P_setup.c,v 1.2 2000/04/30 15:28:24 proff_fs Exp $"; #ifdef _MSC_VER // proff #define strcasecmp _stricmp #define strncasecmp _strnicmp #endif //_MSC_VER #ifdef GL_DOOM #include "gl_struct.h" #endif #include "doomstat.h" #include "m_bbox.h" #include "m_argv.h" #include "g_game.h" #include "w_wad.h" #include "r_main.h" #include "r_things.h" #include "p_maputl.h" #include "p_map.h" #include "p_setup.h" #include "p_spec.h" #include "p_tick.h" #include "p_enemy.h" #include "s_sound.h" // // MAP related Lookup tables. // Store VERTEXES, LINEDEFS, SIDEDEFS, etc. // int numvertexes; vertex_t *vertexes; int numsegs; seg_t *segs; int numsectors; sector_t *sectors; int numsubsectors; subsector_t *subsectors; int numnodes; node_t *nodes; int numlines; line_t *lines; int numsides; side_t *sides; // BLOCKMAP // Created from axis aligned bounding box // of the map, a rectangular array of // blocks of size ... // Used to speed up collision detection // by spatial subdivision in 2D. // // Blockmap size. int bmapwidth, bmapheight; // size in mapblocks // killough 3/1/98: remove blockmap limit internally: long *blockmap; // was short -- killough // offsets in blockmap are from here long *blockmaplump; // was short -- killough fixed_t bmaporgx, bmaporgy; // origin of block map mobj_t **blocklinks; // for thing chains // // REJECT // For fast sight rejection. // Speeds up enemy AI by skipping detailed // LineOf Sight calculation. // Without the special effect, this could // be used as a PVS lookup as well. // byte *rejectmatrix; // Maintain single and multi player starting spots. // 1/11/98 killough: Remove limit on deathmatch starts mapthing_t *deathmatchstarts; // killough size_t num_deathmatchstarts; // killough mapthing_t *deathmatch_p; mapthing_t playerstarts[MAXPLAYERS]; // // P_LoadVertexes // // killough 5/3/98: reformatted, cleaned up void P_LoadVertexes (int lump) { byte *data; int i; // Determine number of lumps: // total lump length / vertex record length. numvertexes = W_LumpLength(lump) / sizeof(mapvertex_t); // Allocate zone memory for buffer. vertexes = Z_Malloc(numvertexes*sizeof(vertex_t),PU_LEVEL,0); // Load data into cache. data = W_CacheLumpNum(lump, PU_STATIC); // Copy and convert vertex coordinates, // internal representation as fixed. for (i=0; iv1 = &vertexes[SHORT(ml->v1)]; li->v2 = &vertexes[SHORT(ml->v2)]; li->angle = (SHORT(ml->angle))<<16; li->offset = (SHORT(ml->offset))<<16; linedef = SHORT(ml->linedef); ldef = &lines[linedef]; li->linedef = ldef; side = SHORT(ml->side); li->sidedef = &sides[ldef->sidenum[side]]; li->frontsector = sides[ldef->sidenum[side]].sector; // killough 5/3/98: ignore 2s flag if second sidedef missing: if (ldef->flags & ML_TWOSIDED && ldef->sidenum[side^1]!=-1) li->backsector = sides[ldef->sidenum[side^1]].sector; else li->backsector = 0; } Z_Free (data); } // // P_LoadSubsectors // // killough 5/3/98: reformatted, cleaned up void P_LoadSubsectors (int lump) { byte *data; int i; numsubsectors = W_LumpLength (lump) / sizeof(mapsubsector_t); subsectors = Z_Malloc(numsubsectors*sizeof(subsector_t),PU_LEVEL,0); data = W_CacheLumpNum(lump, PU_STATIC); memset(subsectors, 0, numsubsectors*sizeof(subsector_t)); for (i=0; iiSectorID=i; // proff 11/99: needed for OpenGL and used in debugmode by the HUD to draw sectornum ss->floorheight = SHORT(ms->floorheight)<ceilingheight = SHORT(ms->ceilingheight)<floorpic = R_FlatNumForName(ms->floorpic); ss->ceilingpic = R_FlatNumForName(ms->ceilingpic); ss->lightlevel = SHORT(ms->lightlevel); ss->special = SHORT(ms->special); ss->oldspecial = SHORT(ms->special); ss->tag = SHORT(ms->tag); ss->thinglist = NULL; ss->touching_thinglist = NULL; // phares 3/14/98 ss->nextsec = -1; //jff 2/26/98 add fields to support locking out ss->prevsec = -1; // stair retriggering until build completes // killough 3/7/98: ss->floor_xoffs = 0; ss->floor_yoffs = 0; // floor and ceiling flats offsets ss->ceiling_xoffs = 0; ss->ceiling_yoffs = 0; ss->heightsec = -1; // sector used to get floor and ceiling height ss->floorlightsec = -1; // sector used to get floor lighting // killough 3/7/98: end changes // killough 4/11/98 sector used to get ceiling lighting: ss->ceilinglightsec = -1; // killough 4/4/98: colormaps: ss->bottommap = ss->midmap = ss->topmap = 0; // killough 10/98: sky textures coming from sidedefs: ss->sky = 0; } Z_Free (data); } // // P_LoadNodes // // killough 5/3/98: reformatted, cleaned up void P_LoadNodes (int lump) { byte *data; int i; numnodes = W_LumpLength (lump) / sizeof(mapnode_t); nodes = Z_Malloc (numnodes*sizeof(node_t),PU_LEVEL,0); data = W_CacheLumpNum (lump, PU_STATIC); for (i=0; ix = SHORT(mn->x)<y = SHORT(mn->y)<dx = SHORT(mn->dx)<dy = SHORT(mn->dy)<children[j] = SHORT(mn->children[j]); for (k=0 ; k<4 ; k++) no->bbox[j][k] = SHORT(mn->bbox[j][k])<type) { case 68: // Arachnotron case 64: // Archvile case 88: // Boss Brain case 89: // Boss Shooter case 69: // Hell Knight case 67: // Mancubus case 71: // Pain Elemental case 65: // Former Human Commando case 66: // Revenant case 84: // Wolf SS continue; } // Do spawn all other stuff. mt->x = SHORT(mt->x); mt->y = SHORT(mt->y); mt->angle = SHORT(mt->angle); mt->type = SHORT(mt->type); mt->options = SHORT(mt->options); P_SpawnMapThing (mt); } Z_Free (data); } // // P_LoadLineDefs // Also counts secret lines for intermissions. // ^^^ // ??? killough ??? // Does this mean secrets used to be linedef-based, rather than sector-based? // // killough 4/4/98: split into two functions, to allow sidedef overloading // // killough 5/3/98: reformatted, cleaned up void P_LoadLineDefs (int lump) { byte *data; int i; numlines = W_LumpLength (lump) / sizeof(maplinedef_t); lines = Z_Malloc (numlines*sizeof(line_t),PU_LEVEL,0); memset (lines, 0, numlines*sizeof(line_t)); data = W_CacheLumpNum (lump,PU_STATIC); for (i=0; iflags = SHORT(mld->flags); ld->special = SHORT(mld->special); ld->tag = SHORT(mld->tag); v1 = ld->v1 = &vertexes[SHORT(mld->v1)]; v2 = ld->v2 = &vertexes[SHORT(mld->v2)]; ld->dx = v2->x - v1->x; ld->dy = v2->y - v1->y; ld->tranlump = -1; // killough 4/11/98: no translucency by default ld->slopetype = !ld->dx ? ST_VERTICAL : !ld->dy ? ST_HORIZONTAL : FixedDiv(ld->dy, ld->dx) > 0 ? ST_POSITIVE : ST_NEGATIVE; if (v1->x < v2->x) { ld->bbox[BOXLEFT] = v1->x; ld->bbox[BOXRIGHT] = v2->x; } else { ld->bbox[BOXLEFT] = v2->x; ld->bbox[BOXRIGHT] = v1->x; } if (v1->y < v2->y) { ld->bbox[BOXBOTTOM] = v1->y; ld->bbox[BOXTOP] = v2->y; } else { ld->bbox[BOXBOTTOM] = v2->y; ld->bbox[BOXTOP] = v1->y; } ld->iLineID=i; // proff 11/99: needed for OpenGL ld->sidenum[0] = SHORT(mld->sidenum[0]); ld->sidenum[1] = SHORT(mld->sidenum[1]); // killough 4/4/98: support special sidedef interpretation below if (ld->sidenum[0] != -1 && ld->special) sides[*ld->sidenum].special = ld->special; } Z_Free (data); } // killough 4/4/98: delay using sidedefs until they are loaded // killough 5/3/98: reformatted, cleaned up void P_LoadLineDefs2(int lump) { int i = numlines; register line_t *ld = lines; for (;i--;ld++) { // killough 11/98: fix common wad errors (missing sidedefs): if (ld->sidenum[0] == -1) ld->sidenum[0] = 0; // Substitute dummy sidedef for missing right side if (ld->sidenum[1] == -1) ld->flags &= ~ML_TWOSIDED; // Clear 2s flag for missing left side ld->frontsector = ld->sidenum[0]!=-1 ? sides[ld->sidenum[0]].sector : 0; ld->backsector = ld->sidenum[1]!=-1 ? sides[ld->sidenum[1]].sector : 0; switch (ld->special) { // killough 4/11/98: handle special types int lump, j; case 260: // killough 4/11/98: translucent 2s textures lump = sides[*ld->sidenum].special; // translucency from sidedef if (!ld->tag) // if tag==0, ld->tranlump = lump; // affect this linedef only else for (j=0;jtag) // affect all matching linedefs lines[j].tranlump = lump; break; } } } // // P_LoadSideDefs // // killough 4/4/98: split into two functions void P_LoadSideDefs (int lump) { numsides = W_LumpLength(lump) / sizeof(mapsidedef_t); sides = Z_Malloc(numsides*sizeof(side_t),PU_LEVEL,0); memset(sides, 0, numsides*sizeof(side_t)); } // killough 4/4/98: delay using texture names until // after linedefs are loaded, to allow overloading. // killough 5/3/98: reformatted, cleaned up void P_LoadSideDefs2(int lump) { byte *data = W_CacheLumpNum(lump,PU_STATIC); int i; for (i=0; itextureoffset = SHORT(msd->textureoffset)<rowoffset = SHORT(msd->rowoffset)<sector = sec = §ors[SHORT(msd->sector)]; switch (sd->special) { case 242: // variable colormap via 242 linedef sd->bottomtexture = (sec->bottommap = R_ColormapNumForName(msd->bottomtexture)) < 0 ? sec->bottommap = 0, R_TextureNumForName(msd->bottomtexture): 0 ; sd->midtexture = (sec->midmap = R_ColormapNumForName(msd->midtexture)) < 0 ? sec->midmap = 0, R_TextureNumForName(msd->midtexture) : 0 ; sd->toptexture = (sec->topmap = R_ColormapNumForName(msd->toptexture)) < 0 ? sec->topmap = 0, R_TextureNumForName(msd->toptexture) : 0 ; break; case 260: // killough 4/11/98: apply translucency to 2s normal texture sd->midtexture = strncasecmp("TRANMAP", msd->midtexture, 8) ? (sd->special = W_CheckNumForName(msd->midtexture)) < 0 || W_LumpLength(sd->special) != 65536 ? sd->special=0, R_TextureNumForName(msd->midtexture) : (sd->special++, 0) : (sd->special=0); sd->toptexture = R_TextureNumForName(msd->toptexture); sd->bottomtexture = R_TextureNumForName(msd->bottomtexture); break; default: // normal cases sd->midtexture = R_TextureNumForName(msd->midtexture); sd->toptexture = R_TextureNumForName(msd->toptexture); sd->bottomtexture = R_TextureNumForName(msd->bottomtexture); break; } } Z_Free (data); } // // killough 10/98: // // Rewritten to use faster algorithm. // // New procedure uses Bresenham-like algorithm on the linedefs, adding the // linedef to each block visited from the beginning to the end of the linedef. // // The algorithm's complexity is on the order of nlines*total_linedef_length. // // Please note: This section of code is not interchangable with TeamTNT's // code which attempts to fix the same problem. static void P_CreateBlockMap(void) { register int i; fixed_t minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN, maxy = INT_MIN; // First find limits of map for (i=0; i> FRACBITS < minx) minx = vertexes[i].x >> FRACBITS; else if (vertexes[i].x >> FRACBITS > maxx) maxx = vertexes[i].x >> FRACBITS; if (vertexes[i].y >> FRACBITS < miny) miny = vertexes[i].y >> FRACBITS; else if (vertexes[i].y >> FRACBITS > maxy) maxy = vertexes[i].y >> FRACBITS; } // Save blockmap parameters bmaporgx = minx << FRACBITS; bmaporgy = miny << FRACBITS; bmapwidth = ((maxx-minx) >> MAPBTOFRAC) + 1; bmapheight = ((maxy-miny) >> MAPBTOFRAC) + 1; // Compute blockmap, which is stored as a 2d array of variable-sized lists. // // Pseudocode: // // For each linedef: // // Map the starting and ending vertices to blocks. // // Starting in the starting vertex's block, do: // // Add linedef to current block's list, dynamically resizing it. // // If current block is the same as the ending vertex's block, exit loop. // // Move to an adjacent block by moving towards the ending block in // either the x or y direction, to the block which contains the linedef. { typedef struct { int n, nalloc, *list; } bmap_t; // blocklist structure unsigned tot = bmapwidth * bmapheight; // size of blockmap bmap_t *bmap = calloc(sizeof *bmap, tot); // array of blocklists for (i=0; i < numlines; i++) { // starting coordinates int x = (lines[i].v1->x >> FRACBITS) - minx; int y = (lines[i].v1->y >> FRACBITS) - miny; // x-y deltas int adx = lines[i].dx >> FRACBITS, dx = adx < 0 ? -1 : 1; int ady = lines[i].dy >> FRACBITS, dy = ady < 0 ? -1 : 1; // difference in preferring to move across y (>0) instead of x (<0) // proff: Changed abs to D_abs (see m_fixed.h) int diff = !adx ? 1 : !ady ? -1 : (((x >> MAPBTOFRAC) << MAPBTOFRAC) + (dx > 0 ? MAPBLOCKUNITS-1 : 0) - x) * (ady = D_abs(ady)) * dx - (((y >> MAPBTOFRAC) << MAPBTOFRAC) + (dy > 0 ? MAPBLOCKUNITS-1 : 0) - y) * (adx = D_abs(adx)) * dy; /* int diff = !adx ? 1 : !ady ? -1 : (((x >> MAPBTOFRAC) << MAPBTOFRAC) + (dx > 0 ? MAPBLOCKUNITS-1 : 0) - x) * (ady = abs(ady)) * dx - (((y >> MAPBTOFRAC) << MAPBTOFRAC) + (dy > 0 ? MAPBLOCKUNITS-1 : 0) - y) * (adx = abs(adx)) * dy;*/ // starting block, and pointer to its blocklist structure int b = (y >> MAPBTOFRAC)*bmapwidth + (x >> MAPBTOFRAC); // ending block int bend = (((lines[i].v2->y >> FRACBITS) - miny) >> MAPBTOFRAC) * bmapwidth + (((lines[i].v2->x >> FRACBITS) - minx) >> MAPBTOFRAC); // delta for pointer when moving across y dy *= bmapwidth; // deltas for diff inside the loop adx <<= MAPBTOFRAC; ady <<= MAPBTOFRAC; // Now we simply iterate block-by-block until we reach the end block. while ((unsigned) b < tot) // failsafe -- should ALWAYS be true { // Increase size of allocated list if necessary if (bmap[b].n >= bmap[b].nalloc) bmap[b].list = realloc(bmap[b].list, (bmap[b].nalloc = bmap[b].nalloc ? bmap[b].nalloc*2 : 8)*sizeof*bmap->list); // Add linedef to end of list bmap[b].list[bmap[b].n++] = i; // If we have reached the last block, exit if (b == bend) break; // Move in either the x or y direction to the next block if (diff < 0) diff += ady, b += dx; else diff -= adx, b += dy; } } // Compute the total size of the blockmap. // // Compression of empty blocks is performed by reserving two offset words // at tot and tot+1. // // 4 words, unused if this routine is called, are reserved at the start. { int count = tot+6; // we need at least 1 word per block, plus reserved's for (i = 0; i < tot; i++) if (bmap[i].n) count += bmap[i].n + 2; // 1 header word + 1 trailer word + blocklist // Allocate blockmap lump with computed count blockmaplump = Z_Malloc(sizeof(*blockmaplump) * count, PU_LEVEL, 0); } // Now compress the blockmap. { int ndx = tot += 4; // Advance index to start of linedef lists bmap_t *bp = bmap; // Start of uncompressed blockmap blockmaplump[ndx++] = 0; // Store an empty blockmap list at start blockmaplump[ndx++] = -1; // (Used for compression) for (i = 4; i < tot; i++, bp++) if (bp->n) // Non-empty blocklist { blockmaplump[blockmaplump[i] = ndx++] = 0; // Store index & header do blockmaplump[ndx++] = bp->list[--bp->n]; // Copy linedef list while (bp->n); blockmaplump[ndx++] = -1; // Store trailer free(bp->list); // Free linedef list } else // Empty blocklist: point to reserved empty blocklist blockmaplump[i] = tot; free(bmap); // Free uncompressed blockmap } } } // // P_LoadBlockMap // // killough 3/1/98: substantially modified to work // towards removing blockmap limit (a wad limitation) // // killough 3/30/98: Rewritten to remove blockmap limit // void P_LoadBlockMap (int lump) { long count; if (M_CheckParm("-blockmap") || (count = W_LumpLength(lump)/2) >= 0x10000) P_CreateBlockMap(); else { long i; short *wadblockmaplump = W_CacheLumpNum (lump, PU_LEVEL); blockmaplump = Z_Malloc(sizeof(*blockmaplump) * count, PU_LEVEL, 0); // killough 3/1/98: Expand wad blockmap into larger internal one, // by treating all offsets except -1 as unsigned and zero-extending // them. This potentially doubles the size of blockmaps allowed, // because Doom originally considered the offsets as always signed. blockmaplump[0] = SHORT(wadblockmaplump[0]); blockmaplump[1] = SHORT(wadblockmaplump[1]); blockmaplump[2] = (long)(SHORT(wadblockmaplump[2])) & 0xffff; blockmaplump[3] = (long)(SHORT(wadblockmaplump[3])) & 0xffff; for (i=4 ; iblockbox, l->v1->x, l->v1->y); M_AddToBox(s->blockbox, l->v2->x, l->v2->y); *s->lines++ = l; } void P_GroupLines (void) { int i, total; line_t **linebuffer; // look up sector number for each subsector for (i=0; isector; // count number of lines in each sector for (i=0; ilinecount++; if (lines[i].backsector && lines[i].backsector != lines[i].frontsector) lines[i].backsector->linecount++; } // compute total number of lines and clear bounding boxes for (total=0, i=0; ilines -= sector->linecount; // set the degenmobj_t to the middle of the bounding box sector->soundorg.x = (sector->blockbox[BOXRIGHT] + sector->blockbox[BOXLEFT])/2; sector->soundorg.y = (sector->blockbox[BOXTOP] + sector->blockbox[BOXBOTTOM])/2; // adjust bounding box to map blocks block = (sector->blockbox[BOXTOP]-bmaporgy+MAXRADIUS)>>MAPBLOCKSHIFT; block = block >= bmapheight ? bmapheight-1 : block; sector->blockbox[BOXTOP]=block; block = (sector->blockbox[BOXBOTTOM]-bmaporgy-MAXRADIUS)>>MAPBLOCKSHIFT; block = block < 0 ? 0 : block; sector->blockbox[BOXBOTTOM]=block; block = (sector->blockbox[BOXRIGHT]-bmaporgx+MAXRADIUS)>>MAPBLOCKSHIFT; block = block >= bmapwidth ? bmapwidth-1 : block; sector->blockbox[BOXRIGHT]=block; block = (sector->blockbox[BOXLEFT]-bmaporgx-MAXRADIUS)>>MAPBLOCKSHIFT; block = block < 0 ? 0 : block; sector->blockbox[BOXLEFT]=block; } } // // killough 10/98 // // Remove slime trails. // // Slime trails are inherent to Doom's coordinate system -- i.e. there is // nothing that a node builder can do to prevent slime trails ALL of the time, // because it's a product of the integer coodinate system, and just because // two lines pass through exact integer coordinates, doesn't necessarily mean // that they will intersect at integer coordinates. Thus we must allow for // fractional coordinates if we are to be able to split segs with node lines, // as a node builder must do when creating a BSP tree. // // A wad file does not allow fractional coordinates, so node builders are out // of luck except that they can try to limit the number of splits (they might // also be able to detect the degree of roundoff error and try to avoid splits // with a high degree of roundoff error). But we can use fractional coordinates // here, inside the engine. It's like the difference between square inches and // square miles, in terms of granularity. // // For each vertex of every seg, check to see whether it's also a vertex of // the linedef associated with the seg (i.e, it's an endpoint). If it's not // an endpoint, and it wasn't already moved, move the vertex towards the // linedef by projecting it using the law of cosines. Formula: // // 2 2 2 2 // dx x0 + dy x1 + dx dy (y0 - y1) dy y0 + dx y1 + dx dy (x0 - x1) // {---------------------------------, ---------------------------------} // 2 2 2 2 // dx + dy dx + dy // // (x0,y0) is the vertex being moved, and (x1,y1)-(x1+dx,y1+dy) is the // reference linedef. // // Segs corresponding to orthogonal linedefs (exactly vertical or horizontal // linedefs), which comprise at least half of all linedefs in most wads, don't // need to be considered, because they almost never contribute to slime trails // (because then any roundoff error is parallel to the linedef, which doesn't // cause slime). Skipping simple orthogonal lines lets the code finish quicker. // // Please note: This section of code is not interchangable with TeamTNT's // code which attempts to fix the same problem. // // Firelines (TM) is a Rezistered Trademark of MBF Productions // void P_RemoveSlimeTrails(void) // killough 10/98 { byte *hit = calloc(1, numvertexes); // Hitlist for vertices int i; for (i=0; idx && l->dy) // We can ignore orthogonal lines { vertex_t *v = segs[i].v1; do if (!hit[v - vertexes]) // If we haven't processed vertex { hit[v - vertexes] = 1; // Mark this vertex as processed if (v != l->v1 && v != l->v2) // Exclude endpoints of linedefs { // Project the vertex back onto the parent linedef longlong dx2 = (l->dx >> FRACBITS) * (l->dx >> FRACBITS); longlong dy2 = (l->dy >> FRACBITS) * (l->dy >> FRACBITS); longlong dxy = (l->dx >> FRACBITS) * (l->dy >> FRACBITS); longlong s = dx2 + dy2; int x0 = v->x, y0 = v->y, x1 = l->v1->x, y1 = l->v1->y; v->x = (int)((dx2 * x0 + dy2 * x1 + dxy * (y0 - y1)) / s); v->y = (int)((dy2 * y0 + dx2 * y1 + dxy * (x0 - x1)) / s); } } // Obsfucated C contest entry: :) while ((v != segs[i].v2) && (v = segs[i].v2)); } } free(hit); } // // P_SetupLevel // // killough 5/3/98: reformatted, cleaned up void P_SetupLevel(int episode, int map, int playermask, skill_t skill) { int i; char lumpname[9]; int lumpnum; totalkills = totalitems = totalsecret = wminfo.maxfrags = 0; wminfo.partime = 180; for (i=0; i