FS#8961 - Anti-Aliased Fonts.
[kugel-rb.git] / apps / plugins / doom / p_maputl.c
bloba2ef132d11c384f08df41e3f792703a043c3281d
1 /* Emacs style mode select -*- C++ -*-
2 *-----------------------------------------------------------------------------
5 * PrBoom a Doom port merged with LxDoom and LSDLDoom
6 * based on BOOM, a modified and improved DOOM engine
7 * Copyright (C) 1999 by
8 * id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
9 * Copyright (C) 1999-2000 by
10 * Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version 2
15 * of the License, or (at your option) any later version.
17 * This program is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
25 * 02111-1307, USA.
27 * DESCRIPTION:
28 * Movement/collision utility functions,
29 * as used by function in p_map.c.
30 * BLOCKMAP Iterator functions,
31 * and some PIT_* functions to use for iteration.
33 *-----------------------------------------------------------------------------*/
35 #include "doomstat.h"
36 #include "m_bbox.h"
37 #include "r_main.h"
38 #include "p_maputl.h"
39 #include "p_map.h"
40 #include "p_setup.h"
41 #include "rockmacros.h"
43 // P_AproxDistance
44 // Gives an estimation of distance (not exact)
47 fixed_t CONSTFUNC P_AproxDistance(fixed_t dx, fixed_t dy)
49 dx = D_abs(dx);
50 dy = D_abs(dy);
51 if (dx < dy)
52 return dx+dy-(dx>>1);
53 return dx+dy-(dy>>1);
57 // P_PointOnLineSide
58 // Returns 0 or 1
60 // killough 5/3/98: reformatted, cleaned up
62 int CONSTFUNC P_PointOnLineSide(fixed_t x, fixed_t y, const line_t *line)
64 return
65 !line->dx ? x <= line->v1->x ? line->dy > 0 : line->dy < 0 :
66 !line->dy ? y <= line->v1->y ? line->dx < 0 : line->dx > 0 :
67 FixedMul(y-line->v1->y, line->dx>>FRACBITS) >=
68 FixedMul(line->dy>>FRACBITS, x-line->v1->x);
72 // P_BoxOnLineSide
73 // Considers the line to be infinite
74 // Returns side 0 or 1, -1 if box crosses the line.
76 // killough 5/3/98: reformatted, cleaned up
78 int CONSTFUNC P_BoxOnLineSide(const fixed_t *tmbox, const line_t *ld)
80 switch (ld->slopetype)
82 int p;
83 default: // shut up compiler warnings -- killough
84 case ST_HORIZONTAL:
85 return
86 (tmbox[BOXBOTTOM] > ld->v1->y) == (p = tmbox[BOXTOP] > ld->v1->y) ?
87 p ^ (ld->dx < 0) : -1;
88 case ST_VERTICAL:
89 return
90 (tmbox[BOXLEFT] < ld->v1->x) == (p = tmbox[BOXRIGHT] < ld->v1->x) ?
91 p ^ (ld->dy < 0) : -1;
92 case ST_POSITIVE:
93 return
94 P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld) ==
95 (p = P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXTOP], ld)) ? p : -1;
96 case ST_NEGATIVE:
97 return
98 (P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld)) ==
99 (p = P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXTOP], ld)) ? p : -1;
104 // P_PointOnDivlineSide
105 // Returns 0 or 1.
107 // killough 5/3/98: reformatted, cleaned up
109 int CONSTFUNC P_PointOnDivlineSide(fixed_t x, fixed_t y, const divline_t *line)
111 return
112 !line->dx ? x <= line->x ? line->dy > 0 : line->dy < 0 :
113 !line->dy ? y <= line->y ? line->dx < 0 : line->dx > 0 :
114 (line->dy^line->dx^(x -= line->x)^(y -= line->y)) < 0 ? (line->dy^x) < 0 :
115 FixedMul(y>>8, line->dx>>8) >= FixedMul(line->dy>>8, x>>8);
119 // P_MakeDivline
122 void P_MakeDivline(const line_t *li, divline_t *dl)
124 dl->x = li->v1->x;
125 dl->y = li->v1->y;
126 dl->dx = li->dx;
127 dl->dy = li->dy;
131 // P_InterceptVector
132 // Returns the fractional intercept point
133 // along the first divline.
134 // This is only called by the addthings
135 // and addlines traversers.
137 // killough 5/3/98: reformatted, cleaned up
139 fixed_t CONSTFUNC P_InterceptVector(const divline_t *v2, const divline_t *v1)
141 fixed_t den = FixedMul(v1->dy>>8, v2->dx) - FixedMul(v1->dx>>8, v2->dy);
142 return den ? FixedDiv((FixedMul((v1->x-v2->x)>>8, v1->dy) +
143 FixedMul((v2->y-v1->y)>>8, v1->dx)), den) : 0;
147 // P_LineOpening
148 // Sets opentop and openbottom to the window
149 // through a two sided line.
150 // OPTIMIZE: keep this precalculated
153 fixed_t opentop;
154 fixed_t openbottom;
155 fixed_t openrange;
156 fixed_t lowfloor;
158 // moved front and back outside P-LineOpening and changed // phares 3/7/98
159 // them to these so we can pick up the new friction value
160 // in PIT_CheckLine()
161 sector_t *openfrontsector; // made global // phares
162 sector_t *openbacksector; // made global
164 void P_LineOpening(const line_t *linedef)
166 if (linedef->sidenum[1] == -1) // single sided line
168 openrange = 0;
169 return;
172 openfrontsector = linedef->frontsector;
173 openbacksector = linedef->backsector;
175 if (openfrontsector->ceilingheight < openbacksector->ceilingheight)
176 opentop = openfrontsector->ceilingheight;
177 else
178 opentop = openbacksector->ceilingheight;
180 if (openfrontsector->floorheight > openbacksector->floorheight)
182 openbottom = openfrontsector->floorheight;
183 lowfloor = openbacksector->floorheight;
185 else
187 openbottom = openbacksector->floorheight;
188 lowfloor = openfrontsector->floorheight;
190 openrange = opentop - openbottom;
194 // THING POSITION SETTING
198 // P_UnsetThingPosition
199 // Unlinks a thing from block map and sectors.
200 // On each position change, BLOCKMAP and other
201 // lookups maintaining lists ot things inside
202 // these structures need to be updated.
205 void P_UnsetThingPosition (mobj_t *thing)
207 if (!(thing->flags & MF_NOSECTOR))
209 /* invisible things don't need to be in sector list
210 * unlink from subsector
212 * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
213 * pointers, allows head node pointers to be treated like everything else
216 mobj_t **sprev = thing->sprev;
217 mobj_t *snext = thing->snext;
218 if ((*sprev = snext)) // unlink from sector list
219 snext->sprev = sprev;
221 // phares 3/14/98
223 // Save the sector list pointed to by touching_sectorlist.
224 // In P_SetThingPosition, we'll keep any nodes that represent
225 // sectors the Thing still touches. We'll add new ones then, and
226 // delete any nodes for sectors the Thing has vacated. Then we'll
227 // put it back into touching_sectorlist. It's done this way to
228 // avoid a lot of deleting/creating for nodes, when most of the
229 // time you just get back what you deleted anyway.
231 // If this Thing is being removed entirely, then the calling
232 // routine will clear out the nodes in sector_list.
234 sector_list = thing->touching_sectorlist;
235 thing->touching_sectorlist = NULL; //to be restored by P_SetThingPosition
238 if (!(thing->flags & MF_NOBLOCKMAP))
240 /* inert things don't need to be in blockmap
242 * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
243 * pointers, allows head node pointers to be treated like everything else
245 * Also more robust, since it doesn't depend on current position for
246 * unlinking. Old method required computing head node based on position
247 * at time of unlinking, assuming it was the same position as during
248 * linking.
251 mobj_t *bnext, **bprev = thing->bprev;
252 if (bprev && (*bprev = bnext = thing->bnext)) // unlink from block map
253 bnext->bprev = bprev;
258 // P_SetThingPosition
259 // Links a thing into both a block and a subsector
260 // based on it's x y.
261 // Sets thing->subsector properly
263 // killough 5/3/98: reformatted, cleaned up
265 void P_SetThingPosition(mobj_t *thing)
266 { // link into subsector
267 subsector_t *ss = thing->subsector = R_PointInSubsector(thing->x, thing->y);
268 if (!(thing->flags & MF_NOSECTOR))
270 // invisible things don't go into the sector links
272 // killough 8/11/98: simpler scheme using pointer-to-pointer prev
273 // pointers, allows head nodes to be treated like everything else
275 mobj_t **link = &ss->sector->thinglist;
276 mobj_t *snext = *link;
277 if ((thing->snext = snext))
278 snext->sprev = &thing->snext;
279 thing->sprev = link;
280 *link = thing;
282 // phares 3/16/98
284 // If sector_list isn't NULL, it has a collection of sector
285 // nodes that were just removed from this Thing.
287 // Collect the sectors the object will live in by looking at
288 // the existing sector_list and adding new nodes and deleting
289 // obsolete ones.
291 // When a node is deleted, its sector links (the links starting
292 // at sector_t->touching_thinglist) are broken. When a node is
293 // added, new sector links are created.
295 P_CreateSecNodeList(thing,thing->x,thing->y);
296 thing->touching_sectorlist = sector_list; // Attach to Thing's mobj_t
297 sector_list = NULL; // clear for next time
300 // link into blockmap
301 if (!(thing->flags & MF_NOBLOCKMAP))
303 // inert things don't need to be in blockmap
304 int blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
305 int blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
306 if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky < bmapheight)
308 // killough 8/11/98: simpler scheme using pointer-to-pointer prev
309 // pointers, allows head nodes to be treated like everything else
311 mobj_t **link = &blocklinks[blocky*bmapwidth+blockx];
312 mobj_t *bnext = *link;
313 if ((thing->bnext = bnext))
314 bnext->bprev = &thing->bnext;
315 thing->bprev = link;
316 *link = thing;
318 else // thing is off the map
319 thing->bnext = NULL, thing->bprev = NULL;
323 // killough 3/15/98:
325 // A fast function for testing intersections between things and linedefs.
327 boolean CONSTFUNC ThingIsOnLine(const mobj_t *t, const line_t *l)
329 int dx = l->dx >> FRACBITS; // Linedef vector
330 int dy = l->dy >> FRACBITS;
331 int a = (l->v1->x >> FRACBITS) - (t->x >> FRACBITS); // Thing-->v1 vector
332 int b = (l->v1->y >> FRACBITS) - (t->y >> FRACBITS);
333 int r = t->radius >> FRACBITS; // Thing radius
335 // First make sure bounding boxes of linedef and thing intersect.
336 // Leads to quick rejection using only shifts and adds/subs/compares.
338 if (D_abs(a*2+dx)-D_abs(dx) > r*2 || D_abs(b*2+dy)-D_abs(dy) > r*2)
339 return 0;
341 // Next, make sure that at least one thing crosshair intersects linedef's
342 // extension. Requires only 3-4 multiplications, the rest adds/subs/
343 // shifts/xors (writing the steps out this way leads to better codegen).
345 a *= dy;
346 b *= dx;
347 a -= b;
348 b = dx + dy;
349 b *= r;
350 if (((a-b)^(a+b)) < 0)
351 return 1;
352 dy -= dx;
353 dy *= r;
354 b = a+dy;
355 a -= dy;
356 return (a^b) < 0;
360 // BLOCK MAP ITERATORS
361 // For each line/thing in the given mapblock,
362 // call the passed PIT_* function.
363 // If the function returns false,
364 // exit with false without checking anything else.
368 // P_BlockLinesIterator
369 // The validcount flags are used to avoid checking lines
370 // that are marked in multiple mapblocks,
371 // so increment validcount before the first call
372 // to P_BlockLinesIterator, then make one or more calls
373 // to it.
375 // killough 5/3/98: reformatted, cleaned up
377 boolean P_BlockLinesIterator(int x, int y, boolean func(line_t*))
379 int offset;
380 const long *list; // killough 3/1/98: for removal of blockmap limit
382 if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
383 return true;
384 offset = y*bmapwidth+x;
385 offset = *(blockmap+offset);
386 list = blockmaplump+offset; // original was reading // phares
387 // delmiting 0 as linedef 0 // phares
389 // killough 1/31/98: for compatibility we need to use the old method.
390 // Most demos go out of sync, and maybe other problems happen, if we
391 // don't consider linedef 0. For safety this should be qualified.
393 if (!demo_compatibility) // killough 2/22/98: demo_compatibility check
394 list++; // skip 0 starting delimiter // phares
395 for ( ; *list != -1 ; list++) // phares
397 line_t *ld = &lines[*list];
398 if (ld->validcount == validcount)
399 continue; // line has already been checked
400 ld->validcount = validcount;
401 if (!func(ld))
402 return false;
404 return true; // everything was checked
408 // P_BlockThingsIterator
410 // killough 5/3/98: reformatted, cleaned up
412 boolean P_BlockThingsIterator(int x, int y, boolean func(mobj_t*))
414 mobj_t *mobj;
415 if (!(x<0 || y<0 || x>=bmapwidth || y>=bmapheight))
416 for (mobj = blocklinks[y*bmapwidth+x]; mobj; mobj = mobj->bnext)
417 if (!func(mobj))
418 return false;
419 return true;
423 // INTERCEPT ROUTINES
426 // 1/11/98 killough: Intercept limit removed
427 static intercept_t *intercepts, *intercept_p;
429 // Check for limit and double size if necessary -- killough
430 static void check_intercept(void)
432 static size_t num_intercepts;
433 size_t offset = intercept_p - intercepts;
434 if (offset >= num_intercepts)
436 num_intercepts = num_intercepts ? num_intercepts*2 : 128;
437 intercepts = realloc(intercepts, sizeof(*intercepts)*num_intercepts);
438 intercept_p = intercepts + offset;
442 divline_t trace;
444 // PIT_AddLineIntercepts.
445 // Looks for lines in the given block
446 // that intercept the given trace
447 // to add to the intercepts list.
449 // A line is crossed if its endpoints
450 // are on opposite sides of the trace.
452 // killough 5/3/98: reformatted, cleaned up
454 boolean PIT_AddLineIntercepts(line_t *ld)
456 int s1;
457 int s2;
458 fixed_t frac;
459 divline_t dl;
461 // avoid precision problems with two routines
462 if (trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16 ||
463 trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
465 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
466 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
468 else
470 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
471 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
474 if (s1 == s2)
475 return true; // line isn't crossed
477 // hit the line
478 P_MakeDivline(ld, &dl);
479 frac = P_InterceptVector(&trace, &dl);
481 if (frac < 0)
482 return true; // behind source
484 check_intercept(); // killough
486 intercept_p->frac = frac;
487 intercept_p->isaline = true;
488 intercept_p->d.line = ld;
489 intercept_p++;
491 return true; // continue
495 // PIT_AddThingIntercepts
497 // killough 5/3/98: reformatted, cleaned up
499 boolean PIT_AddThingIntercepts(mobj_t *thing)
501 fixed_t x1, y1;
502 fixed_t x2, y2;
503 int s1, s2;
504 divline_t dl;
505 fixed_t frac;
507 // check a corner to corner crossection for hit
508 if ((trace.dx ^ trace.dy) > 0)
510 x1 = thing->x - thing->radius;
511 y1 = thing->y + thing->radius;
512 x2 = thing->x + thing->radius;
513 y2 = thing->y - thing->radius;
515 else
517 x1 = thing->x - thing->radius;
518 y1 = thing->y - thing->radius;
519 x2 = thing->x + thing->radius;
520 y2 = thing->y + thing->radius;
523 s1 = P_PointOnDivlineSide (x1, y1, &trace);
524 s2 = P_PointOnDivlineSide (x2, y2, &trace);
526 if (s1 == s2)
527 return true; // line isn't crossed
529 dl.x = x1;
530 dl.y = y1;
531 dl.dx = x2-x1;
532 dl.dy = y2-y1;
534 frac = P_InterceptVector (&trace, &dl);
536 if (frac < 0)
537 return true; // behind source
539 check_intercept(); // killough
541 intercept_p->frac = frac;
542 intercept_p->isaline = false;
543 intercept_p->d.thing = thing;
544 intercept_p++;
546 return true; // keep going
550 // P_TraverseIntercepts
551 // Returns true if the traverser function returns true
552 // for all lines.
554 // killough 5/3/98: reformatted, cleaned up
556 boolean P_TraverseIntercepts(traverser_t func, fixed_t maxfrac)
558 intercept_t *in = NULL;
559 int count = intercept_p - intercepts;
560 while (count--)
562 fixed_t dist = INT_MAX;
563 intercept_t *scan;
564 for (scan = intercepts; scan < intercept_p; scan++)
565 if (scan->frac < dist)
566 dist = (in=scan)->frac;
567 if (dist > maxfrac)
568 return true; // checked everything in range
569 if (!func(in))
570 return false; // don't bother going farther
571 in->frac = INT_MAX;
573 return true; // everything was traversed
577 // P_PathTraverse
578 // Traces a line from x1,y1 to x2,y2,
579 // calling the traverser function for each.
580 // Returns true if the traverser function returns true
581 // for all lines.
583 // killough 5/3/98: reformatted, cleaned up
585 boolean P_PathTraverse(fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
586 int flags, boolean trav(intercept_t *))
588 fixed_t xt1, yt1;
589 fixed_t xt2, yt2;
590 fixed_t xstep, ystep;
591 fixed_t partial;
592 fixed_t xintercept, yintercept;
593 int mapx, mapy;
594 int mapxstep, mapystep;
595 int count;
597 validcount++;
598 intercept_p = intercepts;
600 if (!((x1-bmaporgx)&(MAPBLOCKSIZE-1)))
601 x1 += FRACUNIT; // don't side exactly on a line
603 if (!((y1-bmaporgy)&(MAPBLOCKSIZE-1)))
604 y1 += FRACUNIT; // don't side exactly on a line
606 trace.x = x1;
607 trace.y = y1;
608 trace.dx = x2 - x1;
609 trace.dy = y2 - y1;
611 x1 -= bmaporgx;
612 y1 -= bmaporgy;
613 xt1 = x1>>MAPBLOCKSHIFT;
614 yt1 = y1>>MAPBLOCKSHIFT;
616 x2 -= bmaporgx;
617 y2 -= bmaporgy;
618 xt2 = x2>>MAPBLOCKSHIFT;
619 yt2 = y2>>MAPBLOCKSHIFT;
621 if (xt2 > xt1)
623 mapxstep = 1;
624 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
625 ystep = FixedDiv (y2-y1,D_abs(x2-x1));
627 else
628 if (xt2 < xt1)
630 mapxstep = -1;
631 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
632 ystep = FixedDiv (y2-y1,D_abs(x2-x1));
634 else
636 mapxstep = 0;
637 partial = FRACUNIT;
638 ystep = 256*FRACUNIT;
641 yintercept = (y1>>MAPBTOFRAC) + FixedMul(partial, ystep);
643 if (yt2 > yt1)
645 mapystep = 1;
646 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
647 xstep = FixedDiv (x2-x1,D_abs(y2-y1));
649 else
650 if (yt2 < yt1)
652 mapystep = -1;
653 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
654 xstep = FixedDiv (x2-x1,D_abs(y2-y1));
656 else
658 mapystep = 0;
659 partial = FRACUNIT;
660 xstep = 256*FRACUNIT;
663 xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
665 // Step through map blocks.
666 // Count is present to prevent a round off error
667 // from skipping the break.
669 mapx = xt1;
670 mapy = yt1;
672 for (count = 0; count < 64; count++)
674 if (flags & PT_ADDLINES)
675 if (!P_BlockLinesIterator(mapx, mapy,PIT_AddLineIntercepts))
676 return false; // early out
678 if (flags & PT_ADDTHINGS)
679 if (!P_BlockThingsIterator(mapx, mapy,PIT_AddThingIntercepts))
680 return false; // early out
682 if (mapx == xt2 && mapy == yt2)
683 break;
685 if ((yintercept >> FRACBITS) == mapy)
687 yintercept += ystep;
688 mapx += mapxstep;
690 else
691 if ((xintercept >> FRACBITS) == mapx)
693 xintercept += xstep;
694 mapy += mapystep;
698 // go through the sorted list
699 return P_TraverseIntercepts(trav, FRACUNIT);