base/p_maputl.c

   1
   2 // P_maputl.c
   3
   4 #include <stdlib.h>
   5 #include "doomdef.h"
   6 #include "p_local.h"
   7
   8
   9 /*
  10 ===================
  11 =
  12 = P_AproxDistance
  13 =
  14 = Gives an estimation of distance (not exact)
  15 =
  16 ===================
  17 */
  18
  19 fixed_t P_AproxDistance (fixed_t dx, fixed_t dy)
  20 {
  21         dx = abs(dx);
  22         dy = abs(dy);
  23         if (dx < dy)
  24                 return dx+dy-(dx>>1);
  25         return dx+dy-(dy>>1);
  26 }
  27
  28
  29 /*
  30 ==================
  31 =
  32 = P_PointOnLineSide
  33 =
  34 = Returns 0 or 1
  35 ==================
  36 */
  37
  38 int P_PointOnLineSide (fixed_t x, fixed_t y, line_t *line)
  39 {
  40         fixed_t dx,dy;
  41         fixed_t left, right;
  42
  43         if (!line->dx)
  44         {
  45                 if (x <= line->v1->x)
  46                         return line->dy > 0;
  47                 return line->dy < 0;
  48         }
  49         if (!line->dy)
  50         {
  51                 if (y <= line->v1->y)
  52                         return line->dx < 0;
  53                 return line->dx > 0;
  54         }
  55
  56         dx = (x - line->v1->x);
  57         dy = (y - line->v1->y);
  58
  59         left = FixedMul ( line->dy>>FRACBITS , dx );
  60         right = FixedMul ( dy , line->dx>>FRACBITS );
  61
  62         if (right < left)
  63                 return 0;               // front side
  64         return 1;                       // back side
  65 }
  66
  67
  68 /*
  69 =================
  70 =
  71 = P_BoxOnLineSide
  72 =
  73 = Considers the line to be infinite
  74 = Returns side 0 or 1, -1 if box crosses the line
  75 =================
  76 */
  77
  78 int P_BoxOnLineSide (fixed_t *tmbox, line_t *ld)
  79 {
  80         int             p1=0, p2=0;
  81
  82         switch (ld->slopetype)
  83         {
  84         case ST_HORIZONTAL:
  85                 p1 = tmbox[BOXTOP] > ld->v1->y;
  86                 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
  87                 if (ld->dx < 0)
  88                 {
  89                         p1 ^= 1;
  90                         p2 ^= 1;
  91                 }
  92                 break;
  93         case ST_VERTICAL:
  94                 p1 = tmbox[BOXRIGHT] < ld->v1->x;
  95                 p2 = tmbox[BOXLEFT] < ld->v1->x;
  96                 if (ld->dy < 0)
  97                 {
  98                         p1 ^= 1;
  99                         p2 ^= 1;
 100                 }
 101                 break;
 102         case ST_POSITIVE:
 103                 p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
 104                 p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
 105                 break;
 106         case ST_NEGATIVE:
 107                 p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
 108                 p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
 109                 break;
 110         }
 111
 112         if (p1 == p2)
 113                 return p1;
 114         return -1;
 115 }
 116
 117 /*
 118 ==================
 119 =
 120 = P_PointOnDivlineSide
 121 =
 122 = Returns 0 or 1
 123 ==================
 124 */
 125
 126 int P_PointOnDivlineSide (fixed_t x, fixed_t y, divline_t *line)
 127 {
 128         fixed_t dx,dy;
 129         fixed_t left, right;
 130
 131         if (!line->dx)
 132         {
 133                 if (x <= line->x)
 134                         return line->dy > 0;
 135                 return line->dy < 0;
 136         }
 137         if (!line->dy)
 138         {
 139                 if (y <= line->y)
 140                         return line->dx < 0;
 141                 return line->dx > 0;
 142         }
 143
 144         dx = (x - line->x);
 145         dy = (y - line->y);
 146
 147 // try to quickly decide by looking at sign bits
 148         if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
 149         {
 150                 if ( (line->dy ^ dx) & 0x80000000 )
 151                         return 1;       // (left is negative)
 152                 return 0;
 153         }
 154
 155         left = FixedMul ( line->dy>>8, dx>>8 );
 156         right = FixedMul ( dy>>8 , line->dx>>8 );
 157
 158         if (right < left)
 159                 return 0;               // front side
 160         return 1;                       // back side
 161 }
 162
 163
 164
 165 /*
 166 ==============
 167 =
 168 = P_MakeDivline
 169 =
 170 ==============
 171 */
 172
 173 void P_MakeDivline (line_t *li, divline_t *dl)
 174 {
 175         dl->x = li->v1->x;
 176         dl->y = li->v1->y;
 177         dl->dx = li->dx;
 178         dl->dy = li->dy;
 179 }
 180
 181
 182 /*
 183 ===============
 184 =
 185 = P_InterceptVector
 186 =
 187 = Returns the fractional intercept point along the first divline
 188 =
 189 = This is only called by the addthings and addlines traversers
 190 ===============
 191 */
 192
 193 fixed_t P_InterceptVector (divline_t *v2, divline_t *v1)
 194 {
 195 #if 1
 196         fixed_t frac, num, den;
 197
 198         den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
 199         if (den == 0)
 200                 return 0;
 201 //              I_Error ("P_InterceptVector: parallel");
 202         num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) +
 203                 FixedMul ( (v2->y - v1->y)>>8 , v1->dx);
 204         frac = FixedDiv (num , den);
 205
 206         return frac;
 207 #else
 208 float   frac, num, den, v1x,v1y,v1dx,v1dy,v2x,v2y,v2dx,v2dy;
 209
 210         v1x = (float)v1->x/FRACUNIT;
 211         v1y = (float)v1->y/FRACUNIT;
 212         v1dx = (float)v1->dx/FRACUNIT;
 213         v1dy = (float)v1->dy/FRACUNIT;
 214         v2x = (float)v2->x/FRACUNIT;
 215         v2y = (float)v2->y/FRACUNIT;
 216         v2dx = (float)v2->dx/FRACUNIT;
 217         v2dy = (float)v2->dy/FRACUNIT;
 218
 219         den = v1dy*v2dx - v1dx*v2dy;
 220         if (den == 0)
 221                 return 0;       // parallel
 222         num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
 223         frac = num / den;
 224
 225         return frac*FRACUNIT;
 226 #endif
 227 }
 228
 229 /*
 230 ==================
 231 =
 232 = P_LineOpening
 233 =
 234 = Sets opentop and openbottom to the window through a two sided line
 235 = OPTIMIZE: keep this precalculated
 236 ==================
 237 */
 238
 239 fixed_t opentop, openbottom, openrange;
 240 fixed_t lowfloor;
 241
 242 void P_LineOpening (line_t *linedef)
 243 {
 244         sector_t        *front, *back;
 245
 246         if (linedef->sidenum[1] == -1)
 247         {       // single sided line
 248                 openrange = 0;
 249                 return;
 250         }
 251
 252         front = linedef->frontsector;
 253         back = linedef->backsector;
 254
 255         if (front->ceilingheight < back->ceilingheight)
 256                 opentop = front->ceilingheight;
 257         else
 258                 opentop = back->ceilingheight;
 259         if (front->floorheight > back->floorheight)
 260         {
 261                 openbottom = front->floorheight;
 262                 lowfloor = back->floorheight;
 263         }
 264         else
 265         {
 266                 openbottom = back->floorheight;
 267                 lowfloor = front->floorheight;
 268         }
 269
 270         openrange = opentop - openbottom;
 271 }
 272
 273 /*
 274 ===============================================================================
 275
 276                                                 THING POSITION SETTING
 277
 278 ===============================================================================
 279 */
 280
 281 /*
 282 ===================
 283 =
 284 = P_UnsetThingPosition
 285 =
 286 = Unlinks a thing from block map and sectors
 287 =
 288 ===================
 289 */
 290
 291 void P_UnsetThingPosition (mobj_t *thing)
 292 {
 293         int                             blockx, blocky;
 294
 295         if ( ! (thing->flags & MF_NOSECTOR) )
 296         {       // inert things don't need to be in blockmap
 297 // unlink from subsector
 298                 if (thing->snext)
 299                         thing->snext->sprev = thing->sprev;
 300                 if (thing->sprev)
 301                         thing->sprev->snext = thing->snext;
 302                 else
 303                         thing->subsector->sector->thinglist = thing->snext;
 304         }
 305
 306         if ( ! (thing->flags & MF_NOBLOCKMAP) )
 307         {       // inert things don't need to be in blockmap
 308 // unlink from block map
 309                 if (thing->bnext)
 310                         thing->bnext->bprev = thing->bprev;
 311                 if (thing->bprev)
 312                         thing->bprev->bnext = thing->bnext;
 313                 else
 314                 {
 315                         blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
 316                         blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
 317                         if (blockx>=0 && blockx < bmapwidth
 318                         && blocky>=0 && blocky <bmapheight)
 319                         blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
 320                 }
 321         }
 322 }
 323
 324
 325 /*
 326 ===================
 327 =
 328 = P_SetThingPosition
 329 =
 330 = Links a thing into both a block and a subsector based on it's x y
 331 = Sets thing->subsector properly
 332 =
 333 ===================
 334 */
 335
 336 void P_SetThingPosition (mobj_t *thing)
 337 {
 338         subsector_t             *ss;
 339         sector_t                *sec;
 340         int                             blockx, blocky;
 341         mobj_t                  **link;
 342
 343 //
 344 // link into subsector
 345 //
 346         ss = R_PointInSubsector (thing->x,thing->y);
 347         thing->subsector = ss;
 348         if ( ! (thing->flags & MF_NOSECTOR) )
 349         {       // invisible things don't go into the sector links
 350                 sec = ss->sector;
 351
 352                 thing->sprev = NULL;
 353                 thing->snext = sec->thinglist;
 354                 if (sec->thinglist)
 355                         sec->thinglist->sprev = thing;
 356                 sec->thinglist = thing;
 357         }
 358
 359 //
 360 // link into blockmap
 361 //
 362         if ( ! (thing->flags & MF_NOBLOCKMAP) )
 363         {       // inert things don't need to be in blockmap
 364                 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
 365                 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
 366                 if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky <bmapheight)
 367                 {
 368                         link = &blocklinks[blocky*bmapwidth+blockx];
 369                         thing->bprev = NULL;
 370                         thing->bnext = *link;
 371                         if (*link)
 372                                 (*link)->bprev = thing;
 373                         *link = thing;
 374                 }
 375                 else
 376                 {       // thing is off the map
 377                         thing->bnext = thing->bprev = NULL;
 378                 }
 379         }
 380 }
 381
 382
 383
 384 /*
 385 ===============================================================================
 386
 387                                                 BLOCK MAP ITERATORS
 388
 389 For each line/thing in the given mapblock, call the passed function.
 390 If the function returns false, exit with false without checking anything else.
 391
 392 ===============================================================================
 393 */
 394
 395 /*
 396 ==================
 397 =
 398 = P_BlockLinesIterator
 399 =
 400 = The validcount flags are used to avoid checking lines
 401 = that are marked in multiple mapblocks, so increment validcount before
 402 = the first call to P_BlockLinesIterator, then make one or more calls to it
 403 ===================
 404 */
 405
 406 boolean P_BlockLinesIterator (int x, int y, boolean(*func)(line_t*) )
 407 {
 408         int                     offset;
 409         short           *list;
 410         line_t          *ld;
 411
 412         if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
 413                 return true;
 414         offset = y*bmapwidth+x;
 415
 416         offset = *(blockmap+offset);
 417
 418         for ( list = blockmaplump+offset ; *list != -1 ; list++)
 419         {
 420                 ld = &lines[*list];
 421                 if (ld->validcount == validcount)
 422                         continue;               // line has already been checked
 423                 ld->validcount = validcount;
 424
 425                 if ( !func(ld) )
 426                         return false;
 427         }
 428
 429         return true;            // everything was checked
 430 }
 431
 432
 433 /*
 434 ==================
 435 =
 436 = P_BlockThingsIterator
 437 =
 438 ==================
 439 */
 440
 441 boolean P_BlockThingsIterator (int x, int y, boolean(*func)(mobj_t*) )
 442 {
 443         mobj_t          *mobj;
 444
 445         if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
 446                 return true;
 447
 448         for (mobj = blocklinks[y*bmapwidth+x] ; mobj ; mobj = mobj->bnext)
 449                 if (!func( mobj ) )
 450                         return false;
 451
 452         return true;
 453 }
 454
 455 /*
 456 ===============================================================================
 457
 458                                         INTERCEPT ROUTINES
 459
 460 ===============================================================================
 461 */
 462
 463 intercept_t             intercepts[MAXINTERCEPTS], *intercept_p;
 464
 465 divline_t       trace;
 466 boolean         earlyout;
 467 int                     ptflags;
 468
 469 /*
 470 ==================
 471 =
 472 = PIT_AddLineIntercepts
 473 =
 474 = Looks for lines in the given block that intercept the given trace
 475 = to add to the intercepts list
 476 = A line is crossed if its endpoints are on opposite sides of the trace
 477 = Returns true if earlyout and a solid line hit
 478 ==================
 479 */
 480
 481 boolean PIT_AddLineIntercepts (line_t *ld)
 482 {
 483         int                     s1, s2;
 484         fixed_t         frac;
 485         divline_t       dl;
 486
 487 // avoid precision problems with two routines
 488         if ( trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16
 489         || trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
 490         {
 491                 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
 492                 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
 493         }
 494         else
 495         {
 496                 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
 497                 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
 498         }
 499         if (s1 == s2)
 500                 return true;            // line isn't crossed
 501
 502 //
 503 // hit the line
 504 //
 505         P_MakeDivline (ld, &dl);
 506         frac = P_InterceptVector (&trace, &dl);
 507         if (frac < 0)
 508                 return true;            // behind source
 509
 510 // try to early out the check
 511         if (earlyout && frac < FRACUNIT && !ld->backsector)
 512                 return false;   // stop checking
 513
 514         intercept_p->frac = frac;
 515         intercept_p->isaline = true;
 516         intercept_p->d.line = ld;
 517         intercept_p++;
 518
 519         return true;            // continue
 520 }
 521
 522
 523
 524 /*
 525 ==================
 526 =
 527 = PIT_AddThingIntercepts
 528 =
 529 ==================
 530 */
 531
 532 boolean PIT_AddThingIntercepts (mobj_t  *thing)
 533 {
 534         fixed_t         x1,y1, x2,y2;
 535         int                     s1, s2;
 536         boolean         tracepositive;
 537         divline_t       dl;
 538         fixed_t         frac;
 539
 540         tracepositive = (trace.dx ^ trace.dy)>0;
 541
 542         // check a corner to corner crossection for hit
 543
 544         if (tracepositive)
 545         {
 546                 x1 = thing->x - thing->radius;
 547                 y1 = thing->y + thing->radius;
 548
 549                 x2 = thing->x + thing->radius;
 550                 y2 = thing->y - thing->radius;
 551         }
 552         else
 553         {
 554                 x1 = thing->x - thing->radius;
 555                 y1 = thing->y - thing->radius;
 556
 557                 x2 = thing->x + thing->radius;
 558                 y2 = thing->y + thing->radius;
 559         }
 560         s1 = P_PointOnDivlineSide (x1, y1, &trace);
 561         s2 = P_PointOnDivlineSide (x2, y2, &trace);
 562         if (s1 == s2)
 563                 return true;    // line isn't crossed
 564
 565         dl.x = x1;
 566         dl.y = y1;
 567         dl.dx = x2-x1;
 568         dl.dy = y2-y1;
 569         frac = P_InterceptVector (&trace, &dl);
 570         if (frac < 0)
 571                 return true;            // behind source
 572         intercept_p->frac = frac;
 573         intercept_p->isaline = false;
 574         intercept_p->d.thing = thing;
 575         intercept_p++;
 576
 577         return true;                    // keep going
 578 }
 579
 580
 581 /*
 582 ====================
 583 =
 584 = P_TraverseIntercepts
 585 =
 586 = Returns true if the traverser function returns true for all lines
 587 ====================
 588 */
 589
 590 boolean P_TraverseIntercepts ( traverser_t func, fixed_t maxfrac )
 591 {
 592         int                             count;
 593         fixed_t                 dist;
 594         intercept_t             *scan, *in;
 595
 596         count = intercept_p - intercepts;
 597         in = 0;                 // shut up compiler warning
 598
 599         while (count--)
 600         {
 601                 dist = MAXINT;
 602                 for (scan = intercepts ; scan<intercept_p ; scan++)
 603                         if (scan->frac < dist)
 604                         {
 605                                 dist = scan->frac;
 606                                 in = scan;
 607                         }
 608
 609                 if (dist > maxfrac)
 610                         return true;                    // checked everything in range
 611 #if 0
 612                 {       // don't check these yet, ther may be others inserted
 613                         in = scan = intercepts;
 614                         for ( scan = intercepts ; scan<intercept_p ; scan++)
 615                                 if (scan->frac > maxfrac)
 616                                         *in++ = *scan;
 617                         intercept_p = in;
 618                         return false;
 619                 }
 620 #endif
 621
 622                 if ( !func (in) )
 623                         return false;                   // don't bother going farther
 624                 in->frac = MAXINT;
 625         }
 626
 627         return true;            // everything was traversed
 628 }
 629
 630
 631
 632 /*
 633 ==================
 634 =
 635 = P_PathTraverse
 636 =
 637 = Traces a line from x1,y1 to x2,y2, calling the traverser function for each
 638 = Returns true if the traverser function returns true for all lines
 639 ==================
 640 */
 641
 642 boolean P_PathTraverse (fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
 643         int flags, boolean (*trav) (intercept_t *))
 644 {
 645         fixed_t xt1,yt1,xt2,yt2;
 646         fixed_t xstep,ystep;
 647         fixed_t partial;
 648         fixed_t xintercept, yintercept;
 649         int             mapx, mapy, mapxstep, mapystep;
 650         int             count;
 651
 652         earlyout = flags & PT_EARLYOUT;
 653
 654         validcount++;
 655         intercept_p = intercepts;
 656
 657         if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
 658                 x1 += FRACUNIT;                         // don't side exactly on a line
 659         if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
 660                 y1 += FRACUNIT;                         // don't side exactly on a line
 661         trace.x = x1;
 662         trace.y = y1;
 663         trace.dx = x2 - x1;
 664         trace.dy = y2 - y1;
 665
 666         x1 -= bmaporgx;
 667         y1 -= bmaporgy;
 668         xt1 = x1>>MAPBLOCKSHIFT;
 669         yt1 = y1>>MAPBLOCKSHIFT;
 670
 671         x2 -= bmaporgx;
 672         y2 -= bmaporgy;
 673         xt2 = x2>>MAPBLOCKSHIFT;
 674         yt2 = y2>>MAPBLOCKSHIFT;
 675
 676         if (xt2 > xt1)
 677         {
 678                 mapxstep = 1;
 679                 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
 680                 ystep = FixedDiv (y2-y1,abs(x2-x1));
 681         }
 682         else if (xt2 < xt1)
 683         {
 684                 mapxstep = -1;
 685                 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
 686                 ystep = FixedDiv (y2-y1,abs(x2-x1));
 687         }
 688         else
 689         {
 690                 mapxstep = 0;
 691                 partial = FRACUNIT;
 692                 ystep = 256*FRACUNIT;
 693         }
 694         yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
 695
 696
 697         if (yt2 > yt1)
 698         {
 699                 mapystep = 1;
 700                 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
 701                 xstep = FixedDiv (x2-x1,abs(y2-y1));
 702         }
 703         else if (yt2 < yt1)
 704         {
 705                 mapystep = -1;
 706                 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
 707                 xstep = FixedDiv (x2-x1,abs(y2-y1));
 708         }
 709         else
 710         {
 711                 mapystep = 0;
 712                 partial = FRACUNIT;
 713                 xstep = 256*FRACUNIT;
 714         }
 715         xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
 716
 717
 718 //
 719 // step through map blocks
 720 // Count is present to prevent a round off error from skipping the break
 721         mapx = xt1;
 722         mapy = yt1;
 723
 724         for (count = 0 ; count < 64 ; count++)
 725         {
 726                 if (flags & PT_ADDLINES)
 727                 {
 728                         if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
 729                                 return false;   // early out
 730                 }
 731                 if (flags & PT_ADDTHINGS)
 732                 {
 733                         if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
 734                                 return false;   // early out
 735                 }
 736
 737                 if (mapx == xt2 && mapy == yt2)
 738                         break;
 739
 740                 if ( (yintercept >> FRACBITS) == mapy)
 741                 {
 742                         yintercept += ystep;
 743                         mapx += mapxstep;
 744                 }
 745                 else if ( (xintercept >> FRACBITS) == mapx)
 746                 {
 747                         xintercept += xstep;
 748                         mapy += mapystep;
 749                 }
 750
 751         }
 752
 753
 754 //
 755 // go through the sorted list
 756 //
 757         return P_TraverseIntercepts ( trav, FRACUNIT );
 758 }
 759
 760
 761