base/p_maputl.c

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