|
|
1.1 root 1: 1.1.1.2 ! root 2: // P_maputl.c 1.1 root 3: 1.1.1.2 ! root 4: #include "DoomDef.h" ! 5: #include "P_local.h" 1.1 root 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: 1.1.1.2 ! root 58: left = FixedMul ( line->dy>>FRACBITS , dx ); ! 59: right = FixedMul ( dy , line->dx>>FRACBITS ); 1.1 root 60: 61: if (right < left) 1.1.1.2 ! root 62: return 0; // front side ! 63: return 1; // back side 1.1 root 64: } 65: 66: 67: /* 1.1.1.2 ! root 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, p2; ! 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: /* 1.1 root 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: 1.1.1.2 ! root 146: // try to quickly decide by looking at sign bits 1.1 root 147: if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 ) 148: { 149: if ( (line->dy ^ dx) & 0x80000000 ) 1.1.1.2 ! root 150: return 1; // (left is negative) 1.1 root 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) 1.1.1.2 ! root 158: return 0; // front side ! 159: return 1; // back side 1.1 root 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: /* 1.1.1.2 ! root 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: /* 1.1 root 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) 1.1.1.2 ! root 246: { // single sided line 1.1 root 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) ) 1.1.1.2 ! root 295: { // inert things don't need to be in blockmap ! 296: // unlink from subsector 1.1 root 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) ) 1.1.1.2 ! root 306: { // inert things don't need to be in blockmap ! 307: // unlink from block map 1.1 root 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; 1.1.1.2 ! root 316: if (blockx>=0 && blockx < bmapwidth ! 317: && blocky>=0 && blocky <bmapheight) 1.1 root 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: 1.1.1.2 ! root 342: // ! 343: // link into subsector ! 344: // 1.1 root 345: ss = R_PointInSubsector (thing->x,thing->y); 346: thing->subsector = ss; 347: if ( ! (thing->flags & MF_NOSECTOR) ) 1.1.1.2 ! root 348: { // invisible things don't go into the sector links 1.1 root 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: 1.1.1.2 ! root 358: // ! 359: // link into blockmap ! 360: // 1.1 root 361: if ( ! (thing->flags & MF_NOBLOCKMAP) ) 1.1.1.2 ! root 362: { // inert things don't need to be in blockmap 1.1 root 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 1.1.1.2 ! root 375: { // thing is off the map 1.1 root 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) 1.1.1.2 ! root 421: continue; // line has already been checked 1.1 root 422: ld->validcount = validcount; 423: 424: if ( !func(ld) ) 425: return false; 426: } 427: 1.1.1.2 ! root 428: return true; // everything was checked 1.1 root 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: 1.1.1.2 ! root 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:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.