sys/src/games/doom/p_maputl.c

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