2 //**************************************************************************
4 //** p_maputl.c : Heretic 2 : Raven Software, Corp.
11 //**************************************************************************
16 static mobj_t *RoughBlockCheck(mobj_t *mo, int index);
23 = Gives an estimation of distance (not exact)
28 fixed_t P_AproxDistance (fixed_t dx, fixed_t dy)
47 int P_PointOnLineSide (fixed_t x, fixed_t y, line_t *line)
65 dx = (x - line->v1->x);
66 dy = (y - line->v1->y);
68 left = FixedMul ( line->dy>>FRACBITS , dx );
69 right = FixedMul ( dy , line->dx>>FRACBITS );
72 return 0; // front side
73 return 1; // back side
82 = Considers the line to be infinite
83 = Returns side 0 or 1, -1 if box crosses the line
87 int P_BoxOnLineSide (fixed_t *tmbox, line_t *ld)
89 int p1 = 0, p2 = 0; /* jim initialisers added */
91 switch (ld->slopetype)
94 p1 = tmbox[BOXTOP] > ld->v1->y;
95 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
103 p1 = tmbox[BOXRIGHT] < ld->v1->x;
104 p2 = tmbox[BOXLEFT] < ld->v1->x;
112 p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
113 p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
116 p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
117 p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
129 = P_PointOnDivlineSide
135 int P_PointOnDivlineSide (fixed_t x, fixed_t y, divline_t *line)
156 // try to quickly decide by looking at sign bits
157 if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
159 if ( (line->dy ^ dx) & 0x80000000 )
160 return 1; // (left is negative)
164 left = FixedMul ( line->dy>>8, dx>>8 );
165 right = FixedMul ( dy>>8 , line->dx>>8 );
168 return 0; // front side
169 return 1; // back side
182 void P_MakeDivline (line_t *li, divline_t *dl)
196 = Returns the fractional intercept point along the first divline
198 = This is only called by the addthings and addlines traversers
202 fixed_t P_InterceptVector (divline_t *v2, divline_t *v1)
205 fixed_t frac, num, den;
207 den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
210 // I_Error ("P_InterceptVector: parallel");
211 num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) +
212 FixedMul ( (v2->y - v1->y)>>8 , v1->dx);
213 frac = FixedDiv (num , den);
217 float frac, num, den, v1x,v1y,v1dx,v1dy,v2x,v2y,v2dx,v2dy;
219 v1x = (float)v1->x/FRACUNIT;
220 v1y = (float)v1->y/FRACUNIT;
221 v1dx = (float)v1->dx/FRACUNIT;
222 v1dy = (float)v1->dy/FRACUNIT;
223 v2x = (float)v2->x/FRACUNIT;
224 v2y = (float)v2->y/FRACUNIT;
225 v2dx = (float)v2->dx/FRACUNIT;
226 v2dy = (float)v2->dy/FRACUNIT;
228 den = v1dy*v2dx - v1dx*v2dy;
230 return 0; // parallel
231 num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
234 return frac*FRACUNIT;
243 = Sets opentop and openbottom to the window through a two sided line
244 = OPTIMIZE: keep this precalculated
248 fixed_t opentop, openbottom, openrange;
251 void P_LineOpening (line_t *linedef)
253 sector_t *front, *back;
255 if (linedef->sidenum[1] == -1)
256 { // single sided line
261 front = linedef->frontsector;
262 back = linedef->backsector;
264 if (front->ceilingheight < back->ceilingheight)
265 opentop = front->ceilingheight;
267 opentop = back->ceilingheight;
268 if (front->floorheight > back->floorheight)
270 openbottom = front->floorheight;
271 lowfloor = back->floorheight;
272 tmfloorpic = front->floorpic;
276 openbottom = back->floorheight;
277 lowfloor = front->floorheight;
278 tmfloorpic = back->floorpic;
281 openrange = opentop - openbottom;
285 ===============================================================================
287 THING POSITION SETTING
289 ===============================================================================
295 = P_UnsetThingPosition
297 = Unlinks a thing from block map and sectors
302 void P_UnsetThingPosition (mobj_t *thing)
306 if ( ! (thing->flags & MF_NOSECTOR) )
307 { // inert things don't need to be in blockmap
308 // unlink from subsector
310 thing->snext->sprev = thing->sprev;
312 thing->sprev->snext = thing->snext;
314 thing->subsector->sector->thinglist = thing->snext;
317 if ( ! (thing->flags & MF_NOBLOCKMAP) )
318 { // inert things don't need to be in blockmap
319 // unlink from block map
321 thing->bnext->bprev = thing->bprev;
323 thing->bprev->bnext = thing->bnext;
326 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
327 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
328 if (blockx>=0 && blockx < bmapwidth
329 && blocky>=0 && blocky <bmapheight)
330 blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
341 = Links a thing into both a block and a subsector based on it's x y
342 = Sets thing->subsector properly
347 void P_SetThingPosition (mobj_t *thing)
355 // link into subsector
357 ss = R_PointInSubsector (thing->x,thing->y);
358 thing->subsector = ss;
359 if ( ! (thing->flags & MF_NOSECTOR) )
360 { // invisible things don't go into the sector links
364 thing->snext = sec->thinglist;
366 sec->thinglist->sprev = thing;
367 sec->thinglist = thing;
371 // link into blockmap
373 if ( ! (thing->flags & MF_NOBLOCKMAP) )
374 { // inert things don't need to be in blockmap
375 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
376 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
377 if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky <bmapheight)
379 link = &blocklinks[blocky*bmapwidth+blockx];
381 thing->bnext = *link;
383 (*link)->bprev = thing;
387 { // thing is off the map
388 thing->bnext = thing->bprev = NULL;
396 ===============================================================================
400 For each line/thing in the given mapblock, call the passed function.
401 If the function returns false, exit with false without checking anything else.
403 ===============================================================================
409 = P_BlockLinesIterator
411 = The validcount flags are used to avoid checking lines
412 = that are marked in multiple mapblocks, so increment validcount before
413 = the first call to P_BlockLinesIterator, then make one or more calls to it
417 boolean P_BlockLinesIterator (int x, int y, boolean(*func)(line_t*) )
424 polyblock_t *polyLink;
426 extern polyblock_t **PolyBlockMap;
428 if (x < 0 || y<0 || x>=bmapwidth || y>=bmapheight)
430 offset = y*bmapwidth+x;
432 polyLink = PolyBlockMap[offset];
435 if(polyLink->polyobj)
437 if(polyLink->polyobj->validcount != validcount)
439 polyLink->polyobj->validcount = validcount;
440 tempSeg = polyLink->polyobj->segs;
441 for(i = 0; i < polyLink->polyobj->numsegs; i++, tempSeg++)
443 if((*tempSeg)->linedef->validcount == validcount)
447 (*tempSeg)->linedef->validcount = validcount;
448 if(!func((*tempSeg)->linedef))
455 polyLink = polyLink->next;
458 offset = *(blockmap+offset);
460 for ( list = blockmaplump+offset ; *list != -1 ; list++)
463 if (ld->validcount == validcount)
464 continue; // line has already been checked
465 ld->validcount = validcount;
471 return true; // everything was checked
478 = P_BlockThingsIterator
483 boolean P_BlockThingsIterator (int x, int y, boolean(*func)(mobj_t*) )
487 if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
490 for (mobj = blocklinks[y*bmapwidth+x] ; mobj ; mobj = mobj->bnext)
498 ===============================================================================
502 ===============================================================================
505 intercept_t intercepts[MAXINTERCEPTS], *intercept_p;
514 = PIT_AddLineIntercepts
516 = Looks for lines in the given block that intercept the given trace
517 = to add to the intercepts list
518 = A line is crossed if its endpoints are on opposite sides of the trace
519 = Returns true if earlyout and a solid line hit
523 boolean PIT_AddLineIntercepts (line_t *ld)
529 // avoid precision problems with two routines
530 if ( trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16
531 || trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
533 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
534 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
538 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
539 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
542 return true; // line isn't crossed
547 P_MakeDivline (ld, &dl);
548 frac = P_InterceptVector (&trace, &dl);
550 return true; // behind source
552 // try to early out the check
553 if (earlyout && frac < FRACUNIT && !ld->backsector)
554 return false; // stop checking
556 intercept_p->frac = frac;
557 intercept_p->isaline = true;
558 intercept_p->d.line = ld;
561 return true; // continue
569 = PIT_AddThingIntercepts
574 boolean PIT_AddThingIntercepts (mobj_t *thing)
576 fixed_t x1,y1, x2,y2;
578 boolean tracepositive;
582 tracepositive = (trace.dx ^ trace.dy)>0;
584 // check a corner to corner crossection for hit
588 x1 = thing->x - thing->radius;
589 y1 = thing->y + thing->radius;
591 x2 = thing->x + thing->radius;
592 y2 = thing->y - thing->radius;
596 x1 = thing->x - thing->radius;
597 y1 = thing->y - thing->radius;
599 x2 = thing->x + thing->radius;
600 y2 = thing->y + thing->radius;
602 s1 = P_PointOnDivlineSide (x1, y1, &trace);
603 s2 = P_PointOnDivlineSide (x2, y2, &trace);
605 return true; // line isn't crossed
611 frac = P_InterceptVector (&trace, &dl);
613 return true; // behind source
614 intercept_p->frac = frac;
615 intercept_p->isaline = false;
616 intercept_p->d.thing = thing;
619 return true; // keep going
626 = P_TraverseIntercepts
628 = Returns true if the traverser function returns true for all lines
632 boolean P_TraverseIntercepts ( traverser_t func, fixed_t maxfrac )
636 intercept_t *scan, *in;
638 count = intercept_p - intercepts;
639 in = 0; // shut up compiler warning
644 for (scan = intercepts ; scan<intercept_p ; scan++)
645 if (scan->frac < dist)
652 return true; // checked everything in range
654 { // don't check these yet, ther may be others inserted
655 in = scan = intercepts;
656 for ( scan = intercepts ; scan<intercept_p ; scan++)
657 if (scan->frac > maxfrac)
665 return false; // don't bother going farther
669 return true; // everything was traversed
679 = Traces a line from x1,y1 to x2,y2, calling the traverser function for each
680 = Returns true if the traverser function returns true for all lines
684 boolean P_PathTraverse (fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
685 int flags, boolean (*trav) (intercept_t *))
687 fixed_t xt1,yt1,xt2,yt2;
690 fixed_t xintercept, yintercept;
691 int mapx, mapy, mapxstep, mapystep;
694 earlyout = flags & PT_EARLYOUT;
697 intercept_p = intercepts;
699 if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
700 x1 += FRACUNIT; // don't side exactly on a line
701 if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
702 y1 += FRACUNIT; // don't side exactly on a line
710 xt1 = x1>>MAPBLOCKSHIFT;
711 yt1 = y1>>MAPBLOCKSHIFT;
715 xt2 = x2>>MAPBLOCKSHIFT;
716 yt2 = y2>>MAPBLOCKSHIFT;
721 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
722 ystep = FixedDiv (y2-y1,abs(x2-x1));
727 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
728 ystep = FixedDiv (y2-y1,abs(x2-x1));
734 ystep = 256*FRACUNIT;
736 yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
742 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
743 xstep = FixedDiv (x2-x1,abs(y2-y1));
748 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
749 xstep = FixedDiv (x2-x1,abs(y2-y1));
755 xstep = 256*FRACUNIT;
757 xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
761 // step through map blocks
762 // Count is present to prevent a round off error from skipping the break
766 for (count = 0 ; count < 64 ; count++)
768 if (flags & PT_ADDLINES)
770 if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
771 return false; // early out
773 if (flags & PT_ADDTHINGS)
775 if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
776 return false; // early out
779 if (mapx == xt2 && mapy == yt2)
782 if ( (yintercept >> FRACBITS) == mapy)
787 else if ( (xintercept >> FRACBITS) == mapx)
797 // go through the sorted list
799 return P_TraverseIntercepts ( trav, FRACUNIT );
802 //===========================================================================
804 // P_RoughMonsterSearch
806 // Searches though the surrounding mapblocks for monsters/players
807 // distance is in MAPBLOCKUNITS
808 //===========================================================================
810 mobj_t *P_RoughMonsterSearch(mobj_t *mo, int distance)
823 startX = (mo->x-bmaporgx)>>MAPBLOCKSHIFT;
824 startY = (mo->y-bmaporgy)>>MAPBLOCKSHIFT;
826 if(startX >= 0 && startX < bmapwidth && startY >= 0 && startY < bmapheight)
828 /* jim parens added for gcc */
829 if((target = RoughBlockCheck(mo, startY*bmapwidth+startX)))
830 { // found a target right away
834 for(count = 1; count <= distance; count++)
836 blockX = startX-count;
837 blockY = startY-count;
843 else if(blockY >= bmapheight)
845 blockY = bmapheight-1;
851 else if(blockX >= bmapwidth)
853 blockX = bmapwidth-1;
855 blockIndex = blockY*bmapwidth+blockX;
856 firstStop = startX+count;
861 if(firstStop >= bmapwidth)
863 firstStop = bmapwidth-1;
865 secondStop = startY+count;
870 if(secondStop >= bmapheight)
872 secondStop = bmapheight-1;
874 thirdStop = secondStop*bmapwidth+blockX;
875 secondStop = secondStop*bmapwidth+firstStop;
876 firstStop += blockY*bmapwidth;
877 finalStop = blockIndex;
879 // Trace the first block section (along the top)
880 for(; blockIndex <= firstStop; blockIndex++)
882 /* jim parens added for gcc */
883 if((target = RoughBlockCheck(mo, blockIndex)))
888 // Trace the second block section (right edge)
889 for(blockIndex--; blockIndex <= secondStop; blockIndex += bmapwidth)
891 /* jim parens added for gcc */
892 if((target = RoughBlockCheck(mo, blockIndex)))
897 // Trace the third block section (bottom edge)
898 for(blockIndex -= bmapwidth; blockIndex >= thirdStop; blockIndex--)
900 /* jim parens added for gcc */
901 if((target = RoughBlockCheck(mo, blockIndex)))
906 // Trace the final block section (left edge)
907 for(blockIndex++; blockIndex > finalStop; blockIndex -= bmapwidth)
909 /* jim parens added for gcc */
910 if((target = RoughBlockCheck(mo, blockIndex)))
919 //===========================================================================
923 //===========================================================================
925 static mobj_t *RoughBlockCheck(mobj_t *mo, int index)
931 link = blocklinks[index];
934 if (mo->player) // Minotaur looking around player
936 if ((link->flags&MF_COUNTKILL) ||
937 (link->player && (link != mo)))
939 if (!(link->flags&MF_SHOOTABLE))
944 if (link->flags2&MF2_DORMANT)
949 if ((link->type == MT_MINOTAUR) &&
950 (((mobj_t *)link->special1) == mo))
955 if(netgame && !deathmatch && link->player)
960 if(P_CheckSight(mo, link))
967 else if (mo->type == MT_MINOTAUR) // looking around minotaur
969 master = (mobj_t *)mo->special1;
970 if ((link->flags&MF_COUNTKILL) ||
971 (link->player && (link != master)))
973 if (!(link->flags&MF_SHOOTABLE))
978 if (link->flags2&MF2_DORMANT)
983 if ((link->type == MT_MINOTAUR) &&
984 (link->special1 == mo->special1))
989 if(netgame && !deathmatch && link->player)
994 if(P_CheckSight(mo, link))
1001 else if (mo->type == MT_MSTAFF_FX2) // bloodscourge
1003 if ((link->flags&MF_COUNTKILL ||
1004 (link->player && link != mo->target))
1005 && !(link->flags2&MF2_DORMANT))
1007 if (!(link->flags&MF_SHOOTABLE))
1012 if(netgame && !deathmatch && link->player)
1017 else if(P_CheckSight(mo, link))
1019 master = mo->target;
1020 angle = R_PointToAngle2(master->x, master->y,
1021 link->x, link->y) - master->angle;
1023 if (angle>226 || angle<30)
1033 if ((link->flags&MF_COUNTKILL ||
1034 (link->player && link != mo->target))
1035 && !(link->flags2&MF2_DORMANT))
1037 if (!(link->flags&MF_SHOOTABLE))
1042 if(netgame && !deathmatch && link->player)
1047 if (link == mo->target)
1052 else if(P_CheckSight(mo, link))