diff options
Diffstat (limited to 'src/p_maputl.c')
-rw-r--r-- | src/p_maputl.c | 683 |
1 files changed, 683 insertions, 0 deletions
diff --git a/src/p_maputl.c b/src/p_maputl.c new file mode 100644 index 0000000..62ce91c --- /dev/null +++ b/src/p_maputl.c | |||
@@ -0,0 +1,683 @@ | |||
1 | /* Emacs style mode select -*- C++ -*- | ||
2 | *----------------------------------------------------------------------------- | ||
3 | * | ||
4 | * | ||
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 | ||
11 | * Copyright 2005, 2006 by | ||
12 | * Florian Schulze, Colin Phipps, Neil Stevens, Andrey Budko | ||
13 | * | ||
14 | * This program is free software; you can redistribute it and/or | ||
15 | * modify it under the terms of the GNU General Public License | ||
16 | * as published by the Free Software Foundation; either version 2 | ||
17 | * of the License, or (at your option) any later version. | ||
18 | * | ||
19 | * This program is distributed in the hope that it will be useful, | ||
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
22 | * GNU General Public License for more details. | ||
23 | * | ||
24 | * You should have received a copy of the GNU General Public License | ||
25 | * along with this program; if not, write to the Free Software | ||
26 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | ||
27 | * 02111-1307, USA. | ||
28 | * | ||
29 | * DESCRIPTION: | ||
30 | * Movement/collision utility functions, | ||
31 | * as used by function in p_map.c. | ||
32 | * BLOCKMAP Iterator functions, | ||
33 | * and some PIT_* functions to use for iteration. | ||
34 | * | ||
35 | *-----------------------------------------------------------------------------*/ | ||
36 | |||
37 | #include "doomstat.h" | ||
38 | #include "m_bbox.h" | ||
39 | #include "r_main.h" | ||
40 | #include "p_maputl.h" | ||
41 | #include "p_map.h" | ||
42 | #include "p_setup.h" | ||
43 | |||
44 | // | ||
45 | // P_AproxDistance | ||
46 | // Gives an estimation of distance (not exact) | ||
47 | // | ||
48 | |||
49 | fixed_t CONSTFUNC P_AproxDistance(fixed_t dx, fixed_t dy) | ||
50 | { | ||
51 | dx = D_abs(dx); | ||
52 | dy = D_abs(dy); | ||
53 | if (dx < dy) | ||
54 | return dx+dy-(dx>>1); | ||
55 | return dx+dy-(dy>>1); | ||
56 | } | ||
57 | |||
58 | // | ||
59 | // P_PointOnLineSide | ||
60 | // Returns 0 or 1 | ||
61 | // | ||
62 | // killough 5/3/98: reformatted, cleaned up | ||
63 | |||
64 | int PUREFUNC P_PointOnLineSide(fixed_t x, fixed_t y, const line_t *line) | ||
65 | { | ||
66 | return | ||
67 | !line->dx ? x <= line->v1->x ? line->dy > 0 : line->dy < 0 : | ||
68 | !line->dy ? y <= line->v1->y ? line->dx < 0 : line->dx > 0 : | ||
69 | FixedMul(y-line->v1->y, line->dx>>FRACBITS) >= | ||
70 | FixedMul(line->dy>>FRACBITS, x-line->v1->x); | ||
71 | } | ||
72 | |||
73 | // | ||
74 | // P_BoxOnLineSide | ||
75 | // Considers the line to be infinite | ||
76 | // Returns side 0 or 1, -1 if box crosses the line. | ||
77 | // | ||
78 | // killough 5/3/98: reformatted, cleaned up | ||
79 | |||
80 | int PUREFUNC P_BoxOnLineSide(const fixed_t *tmbox, const line_t *ld) | ||
81 | { | ||
82 | switch (ld->slopetype) | ||
83 | { | ||
84 | int p; | ||
85 | default: // shut up compiler warnings -- killough | ||
86 | case ST_HORIZONTAL: | ||
87 | return | ||
88 | (tmbox[BOXBOTTOM] > ld->v1->y) == (p = tmbox[BOXTOP] > ld->v1->y) ? | ||
89 | p ^ (ld->dx < 0) : -1; | ||
90 | case ST_VERTICAL: | ||
91 | return | ||
92 | (tmbox[BOXLEFT] < ld->v1->x) == (p = tmbox[BOXRIGHT] < ld->v1->x) ? | ||
93 | p ^ (ld->dy < 0) : -1; | ||
94 | case ST_POSITIVE: | ||
95 | return | ||
96 | P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld) == | ||
97 | (p = P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXTOP], ld)) ? p : -1; | ||
98 | case ST_NEGATIVE: | ||
99 | return | ||
100 | (P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld)) == | ||
101 | (p = P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXTOP], ld)) ? p : -1; | ||
102 | } | ||
103 | } | ||
104 | |||
105 | // | ||
106 | // P_PointOnDivlineSide | ||
107 | // Returns 0 or 1. | ||
108 | // | ||
109 | // killough 5/3/98: reformatted, cleaned up | ||
110 | |||
111 | static int PUREFUNC P_PointOnDivlineSide(fixed_t x, fixed_t y, const divline_t *line) | ||
112 | { | ||
113 | return | ||
114 | !line->dx ? x <= line->x ? line->dy > 0 : line->dy < 0 : | ||
115 | !line->dy ? y <= line->y ? line->dx < 0 : line->dx > 0 : | ||
116 | (line->dy^line->dx^(x -= line->x)^(y -= line->y)) < 0 ? (line->dy^x) < 0 : | ||
117 | FixedMul(y>>8, line->dx>>8) >= FixedMul(line->dy>>8, x>>8); | ||
118 | } | ||
119 | |||
120 | // | ||
121 | // P_MakeDivline | ||
122 | // | ||
123 | |||
124 | static void P_MakeDivline(const line_t *li, divline_t *dl) | ||
125 | { | ||
126 | dl->x = li->v1->x; | ||
127 | dl->y = li->v1->y; | ||
128 | dl->dx = li->dx; | ||
129 | dl->dy = li->dy; | ||
130 | } | ||
131 | |||
132 | // | ||
133 | // P_InterceptVector | ||
134 | // Returns the fractional intercept point | ||
135 | // along the first divline. | ||
136 | // This is only called by the addthings | ||
137 | // and addlines traversers. | ||
138 | // | ||
139 | |||
140 | /* cph - this is killough's 4/19/98 version of P_InterceptVector and | ||
141 | * P_InterceptVector2 (which were interchangeable). We still use this | ||
142 | * in compatibility mode. */ | ||
143 | fixed_t PUREFUNC P_InterceptVector2(const divline_t *v2, const divline_t *v1) | ||
144 | { | ||
145 | fixed_t den; | ||
146 | return (den = FixedMul(v1->dy>>8, v2->dx) - FixedMul(v1->dx>>8, v2->dy)) ? | ||
147 | FixedDiv(FixedMul((v1->x - v2->x)>>8, v1->dy) + | ||
148 | FixedMul((v2->y - v1->y)>>8, v1->dx), den) : 0; | ||
149 | } | ||
150 | |||
151 | fixed_t PUREFUNC P_InterceptVector(const divline_t *v2, const divline_t *v1) | ||
152 | { | ||
153 | if (compatibility_level < prboom_4_compatibility) | ||
154 | return P_InterceptVector2(v2, v1); | ||
155 | else { | ||
156 | /* cph - This was introduced at prboom_4_compatibility - no precision/overflow problems */ | ||
157 | int_64_t den = (int_64_t)v1->dy * v2->dx - (int_64_t)v1->dx * v2->dy; | ||
158 | den >>= 16; | ||
159 | if (!den) | ||
160 | return 0; | ||
161 | return (fixed_t)(((int_64_t)(v1->x - v2->x) * v1->dy - (int_64_t)(v1->y - v2->y) * v1->dx) / den); | ||
162 | } | ||
163 | } | ||
164 | |||
165 | // | ||
166 | // P_LineOpening | ||
167 | // Sets opentop and openbottom to the window | ||
168 | // through a two sided line. | ||
169 | // OPTIMIZE: keep this precalculated | ||
170 | // | ||
171 | |||
172 | fixed_t opentop; | ||
173 | fixed_t openbottom; | ||
174 | fixed_t openrange; | ||
175 | fixed_t lowfloor; | ||
176 | |||
177 | // moved front and back outside P-LineOpening and changed // phares 3/7/98 | ||
178 | // them to these so we can pick up the new friction value | ||
179 | // in PIT_CheckLine() | ||
180 | sector_t *openfrontsector; // made global // phares | ||
181 | sector_t *openbacksector; // made global | ||
182 | |||
183 | void P_LineOpening(const line_t *linedef) | ||
184 | { | ||
185 | if (linedef->sidenum[1] == NO_INDEX) // single sided line | ||
186 | { | ||
187 | openrange = 0; | ||
188 | return; | ||
189 | } | ||
190 | |||
191 | openfrontsector = linedef->frontsector; | ||
192 | openbacksector = linedef->backsector; | ||
193 | |||
194 | if (openfrontsector->ceilingheight < openbacksector->ceilingheight) | ||
195 | opentop = openfrontsector->ceilingheight; | ||
196 | else | ||
197 | opentop = openbacksector->ceilingheight; | ||
198 | |||
199 | if (openfrontsector->floorheight > openbacksector->floorheight) | ||
200 | { | ||
201 | openbottom = openfrontsector->floorheight; | ||
202 | lowfloor = openbacksector->floorheight; | ||
203 | } | ||
204 | else | ||
205 | { | ||
206 | openbottom = openbacksector->floorheight; | ||
207 | lowfloor = openfrontsector->floorheight; | ||
208 | } | ||
209 | openrange = opentop - openbottom; | ||
210 | } | ||
211 | |||
212 | // | ||
213 | // THING POSITION SETTING | ||
214 | // | ||
215 | |||
216 | // | ||
217 | // P_UnsetThingPosition | ||
218 | // Unlinks a thing from block map and sectors. | ||
219 | // On each position change, BLOCKMAP and other | ||
220 | // lookups maintaining lists ot things inside | ||
221 | // these structures need to be updated. | ||
222 | // | ||
223 | |||
224 | void P_UnsetThingPosition (mobj_t *thing) | ||
225 | { | ||
226 | if (!(thing->flags & MF_NOSECTOR)) | ||
227 | { | ||
228 | /* invisible things don't need to be in sector list | ||
229 | * unlink from subsector | ||
230 | * | ||
231 | * killough 8/11/98: simpler scheme using pointers-to-pointers for prev | ||
232 | * pointers, allows head node pointers to be treated like everything else | ||
233 | */ | ||
234 | |||
235 | mobj_t **sprev = thing->sprev; | ||
236 | mobj_t *snext = thing->snext; | ||
237 | if ((*sprev = snext)) // unlink from sector list | ||
238 | snext->sprev = sprev; | ||
239 | |||
240 | // phares 3/14/98 | ||
241 | // | ||
242 | // Save the sector list pointed to by touching_sectorlist. | ||
243 | // In P_SetThingPosition, we'll keep any nodes that represent | ||
244 | // sectors the Thing still touches. We'll add new ones then, and | ||
245 | // delete any nodes for sectors the Thing has vacated. Then we'll | ||
246 | // put it back into touching_sectorlist. It's done this way to | ||
247 | // avoid a lot of deleting/creating for nodes, when most of the | ||
248 | // time you just get back what you deleted anyway. | ||
249 | // | ||
250 | // If this Thing is being removed entirely, then the calling | ||
251 | // routine will clear out the nodes in sector_list. | ||
252 | |||
253 | sector_list = thing->touching_sectorlist; | ||
254 | thing->touching_sectorlist = NULL; //to be restored by P_SetThingPosition | ||
255 | } | ||
256 | |||
257 | if (!(thing->flags & MF_NOBLOCKMAP)) | ||
258 | { | ||
259 | /* inert things don't need to be in blockmap | ||
260 | * | ||
261 | * killough 8/11/98: simpler scheme using pointers-to-pointers for prev | ||
262 | * pointers, allows head node pointers to be treated like everything else | ||
263 | * | ||
264 | * Also more robust, since it doesn't depend on current position for | ||
265 | * unlinking. Old method required computing head node based on position | ||
266 | * at time of unlinking, assuming it was the same position as during | ||
267 | * linking. | ||
268 | */ | ||
269 | |||
270 | mobj_t *bnext, **bprev = thing->bprev; | ||
271 | if (bprev && (*bprev = bnext = thing->bnext)) // unlink from block map | ||
272 | bnext->bprev = bprev; | ||
273 | } | ||
274 | } | ||
275 | |||
276 | // | ||
277 | // P_SetThingPosition | ||
278 | // Links a thing into both a block and a subsector | ||
279 | // based on it's x y. | ||
280 | // Sets thing->subsector properly | ||
281 | // | ||
282 | // killough 5/3/98: reformatted, cleaned up | ||
283 | |||
284 | void P_SetThingPosition(mobj_t *thing) | ||
285 | { // link into subsector | ||
286 | subsector_t *ss = thing->subsector = R_PointInSubsector(thing->x, thing->y); | ||
287 | if (!(thing->flags & MF_NOSECTOR)) | ||
288 | { | ||
289 | // invisible things don't go into the sector links | ||
290 | |||
291 | // killough 8/11/98: simpler scheme using pointer-to-pointer prev | ||
292 | // pointers, allows head nodes to be treated like everything else | ||
293 | |||
294 | mobj_t **link = &ss->sector->thinglist; | ||
295 | mobj_t *snext = *link; | ||
296 | if ((thing->snext = snext)) | ||
297 | snext->sprev = &thing->snext; | ||
298 | thing->sprev = link; | ||
299 | *link = thing; | ||
300 | |||
301 | // phares 3/16/98 | ||
302 | // | ||
303 | // If sector_list isn't NULL, it has a collection of sector | ||
304 | // nodes that were just removed from this Thing. | ||
305 | |||
306 | // Collect the sectors the object will live in by looking at | ||
307 | // the existing sector_list and adding new nodes and deleting | ||
308 | // obsolete ones. | ||
309 | |||
310 | // When a node is deleted, its sector links (the links starting | ||
311 | // at sector_t->touching_thinglist) are broken. When a node is | ||
312 | // added, new sector links are created. | ||
313 | |||
314 | P_CreateSecNodeList(thing,thing->x,thing->y); | ||
315 | thing->touching_sectorlist = sector_list; // Attach to Thing's mobj_t | ||
316 | sector_list = NULL; // clear for next time | ||
317 | } | ||
318 | |||
319 | // link into blockmap | ||
320 | if (!(thing->flags & MF_NOBLOCKMAP)) | ||
321 | { | ||
322 | // inert things don't need to be in blockmap | ||
323 | int blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT; | ||
324 | int blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT; | ||
325 | if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky < bmapheight) | ||
326 | { | ||
327 | // killough 8/11/98: simpler scheme using pointer-to-pointer prev | ||
328 | // pointers, allows head nodes to be treated like everything else | ||
329 | |||
330 | mobj_t **link = &blocklinks[blocky*bmapwidth+blockx]; | ||
331 | mobj_t *bnext = *link; | ||
332 | if ((thing->bnext = bnext)) | ||
333 | bnext->bprev = &thing->bnext; | ||
334 | thing->bprev = link; | ||
335 | *link = thing; | ||
336 | } | ||
337 | else // thing is off the map | ||
338 | thing->bnext = NULL, thing->bprev = NULL; | ||
339 | } | ||
340 | } | ||
341 | |||
342 | // | ||
343 | // BLOCK MAP ITERATORS | ||
344 | // For each line/thing in the given mapblock, | ||
345 | // call the passed PIT_* function. | ||
346 | // If the function returns false, | ||
347 | // exit with false without checking anything else. | ||
348 | // | ||
349 | |||
350 | // | ||
351 | // P_BlockLinesIterator | ||
352 | // The validcount flags are used to avoid checking lines | ||
353 | // that are marked in multiple mapblocks, | ||
354 | // so increment validcount before the first call | ||
355 | // to P_BlockLinesIterator, then make one or more calls | ||
356 | // to it. | ||
357 | // | ||
358 | // killough 5/3/98: reformatted, cleaned up | ||
359 | |||
360 | boolean P_BlockLinesIterator(int x, int y, boolean func(line_t*)) | ||
361 | { | ||
362 | int offset; | ||
363 | const long *list; // killough 3/1/98: for removal of blockmap limit | ||
364 | |||
365 | if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight) | ||
366 | return true; | ||
367 | offset = y*bmapwidth+x; | ||
368 | offset = *(blockmap+offset); | ||
369 | list = blockmaplump+offset; // original was reading // phares | ||
370 | // delmiting 0 as linedef 0 // phares | ||
371 | |||
372 | // killough 1/31/98: for compatibility we need to use the old method. | ||
373 | // Most demos go out of sync, and maybe other problems happen, if we | ||
374 | // don't consider linedef 0. For safety this should be qualified. | ||
375 | |||
376 | if (!demo_compatibility) // killough 2/22/98: demo_compatibility check | ||
377 | list++; // skip 0 starting delimiter // phares | ||
378 | for ( ; *list != -1 ; list++) // phares | ||
379 | { | ||
380 | line_t *ld = &lines[*list]; | ||
381 | if (ld->validcount == validcount) | ||
382 | continue; // line has already been checked | ||
383 | ld->validcount = validcount; | ||
384 | if (!func(ld)) | ||
385 | return false; | ||
386 | } | ||
387 | return true; // everything was checked | ||
388 | } | ||
389 | |||
390 | // | ||
391 | // P_BlockThingsIterator | ||
392 | // | ||
393 | // killough 5/3/98: reformatted, cleaned up | ||
394 | |||
395 | boolean P_BlockThingsIterator(int x, int y, boolean func(mobj_t*)) | ||
396 | { | ||
397 | mobj_t *mobj; | ||
398 | if (!(x<0 || y<0 || x>=bmapwidth || y>=bmapheight)) | ||
399 | for (mobj = blocklinks[y*bmapwidth+x]; mobj; mobj = mobj->bnext) | ||
400 | if (!func(mobj)) | ||
401 | return false; | ||
402 | return true; | ||
403 | } | ||
404 | |||
405 | // | ||
406 | // INTERCEPT ROUTINES | ||
407 | // | ||
408 | |||
409 | // 1/11/98 killough: Intercept limit removed | ||
410 | static intercept_t *intercepts, *intercept_p; | ||
411 | |||
412 | // Check for limit and double size if necessary -- killough | ||
413 | static void check_intercept(void) | ||
414 | { | ||
415 | static size_t num_intercepts; | ||
416 | size_t offset = intercept_p - intercepts; | ||
417 | if (offset >= num_intercepts) | ||
418 | { | ||
419 | num_intercepts = num_intercepts ? num_intercepts*2 : 128; | ||
420 | intercepts = realloc(intercepts, sizeof(*intercepts)*num_intercepts); | ||
421 | intercept_p = intercepts + offset; | ||
422 | } | ||
423 | } | ||
424 | |||
425 | divline_t trace; | ||
426 | |||
427 | // PIT_AddLineIntercepts. | ||
428 | // Looks for lines in the given block | ||
429 | // that intercept the given trace | ||
430 | // to add to the intercepts list. | ||
431 | // | ||
432 | // A line is crossed if its endpoints | ||
433 | // are on opposite sides of the trace. | ||
434 | // | ||
435 | // killough 5/3/98: reformatted, cleaned up | ||
436 | |||
437 | boolean PIT_AddLineIntercepts(line_t *ld) | ||
438 | { | ||
439 | int s1; | ||
440 | int s2; | ||
441 | fixed_t frac; | ||
442 | divline_t dl; | ||
443 | |||
444 | // avoid precision problems with two routines | ||
445 | if (trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16 || | ||
446 | trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16) | ||
447 | { | ||
448 | s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace); | ||
449 | s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace); | ||
450 | } | ||
451 | else | ||
452 | { | ||
453 | s1 = P_PointOnLineSide (trace.x, trace.y, ld); | ||
454 | s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld); | ||
455 | } | ||
456 | |||
457 | if (s1 == s2) | ||
458 | return true; // line isn't crossed | ||
459 | |||
460 | // hit the line | ||
461 | P_MakeDivline(ld, &dl); | ||
462 | frac = P_InterceptVector(&trace, &dl); | ||
463 | |||
464 | if (frac < 0) | ||
465 | return true; // behind source | ||
466 | |||
467 | check_intercept(); // killough | ||
468 | |||
469 | intercept_p->frac = frac; | ||
470 | intercept_p->isaline = true; | ||
471 | intercept_p->d.line = ld; | ||
472 | intercept_p++; | ||
473 | |||
474 | return true; // continue | ||
475 | } | ||
476 | |||
477 | // | ||
478 | // PIT_AddThingIntercepts | ||
479 | // | ||
480 | // killough 5/3/98: reformatted, cleaned up | ||
481 | |||
482 | boolean PIT_AddThingIntercepts(mobj_t *thing) | ||
483 | { | ||
484 | fixed_t x1, y1; | ||
485 | fixed_t x2, y2; | ||
486 | int s1, s2; | ||
487 | divline_t dl; | ||
488 | fixed_t frac; | ||
489 | |||
490 | // check a corner to corner crossection for hit | ||
491 | if ((trace.dx ^ trace.dy) > 0) | ||
492 | { | ||
493 | x1 = thing->x - thing->radius; | ||
494 | y1 = thing->y + thing->radius; | ||
495 | x2 = thing->x + thing->radius; | ||
496 | y2 = thing->y - thing->radius; | ||
497 | } | ||
498 | else | ||
499 | { | ||
500 | x1 = thing->x - thing->radius; | ||
501 | y1 = thing->y - thing->radius; | ||
502 | x2 = thing->x + thing->radius; | ||
503 | y2 = thing->y + thing->radius; | ||
504 | } | ||
505 | |||
506 | s1 = P_PointOnDivlineSide (x1, y1, &trace); | ||
507 | s2 = P_PointOnDivlineSide (x2, y2, &trace); | ||
508 | |||
509 | if (s1 == s2) | ||
510 | return true; // line isn't crossed | ||
511 | |||
512 | dl.x = x1; | ||
513 | dl.y = y1; | ||
514 | dl.dx = x2-x1; | ||
515 | dl.dy = y2-y1; | ||
516 | |||
517 | frac = P_InterceptVector (&trace, &dl); | ||
518 | |||
519 | if (frac < 0) | ||
520 | return true; // behind source | ||
521 | |||
522 | check_intercept(); // killough | ||
523 | |||
524 | intercept_p->frac = frac; | ||
525 | intercept_p->isaline = false; | ||
526 | intercept_p->d.thing = thing; | ||
527 | intercept_p++; | ||
528 | |||
529 | return true; // keep going | ||
530 | } | ||
531 | |||
532 | // | ||
533 | // P_TraverseIntercepts | ||
534 | // Returns true if the traverser function returns true | ||
535 | // for all lines. | ||
536 | // | ||
537 | // killough 5/3/98: reformatted, cleaned up | ||
538 | |||
539 | boolean P_TraverseIntercepts(traverser_t func, fixed_t maxfrac) | ||
540 | { | ||
541 | intercept_t *in = NULL; | ||
542 | int count = intercept_p - intercepts; | ||
543 | while (count--) | ||
544 | { | ||
545 | fixed_t dist = INT_MAX; | ||
546 | intercept_t *scan; | ||
547 | for (scan = intercepts; scan < intercept_p; scan++) | ||
548 | if (scan->frac < dist) | ||
549 | dist = (in=scan)->frac; | ||
550 | if (dist > maxfrac) | ||
551 | return true; // checked everything in range | ||
552 | if (!func(in)) | ||
553 | return false; // don't bother going farther | ||
554 | in->frac = INT_MAX; | ||
555 | } | ||
556 | return true; // everything was traversed | ||
557 | } | ||
558 | |||
559 | // | ||
560 | // P_PathTraverse | ||
561 | // Traces a line from x1,y1 to x2,y2, | ||
562 | // calling the traverser function for each. | ||
563 | // Returns true if the traverser function returns true | ||
564 | // for all lines. | ||
565 | // | ||
566 | // killough 5/3/98: reformatted, cleaned up | ||
567 | |||
568 | boolean P_PathTraverse(fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2, | ||
569 | int flags, boolean trav(intercept_t *)) | ||
570 | { | ||
571 | fixed_t xt1, yt1; | ||
572 | fixed_t xt2, yt2; | ||
573 | fixed_t xstep, ystep; | ||
574 | fixed_t partial; | ||
575 | fixed_t xintercept, yintercept; | ||
576 | int mapx, mapy; | ||
577 | int mapxstep, mapystep; | ||
578 | int count; | ||
579 | |||
580 | validcount++; | ||
581 | intercept_p = intercepts; | ||
582 | |||
583 | if (!((x1-bmaporgx)&(MAPBLOCKSIZE-1))) | ||
584 | x1 += FRACUNIT; // don't side exactly on a line | ||
585 | |||
586 | if (!((y1-bmaporgy)&(MAPBLOCKSIZE-1))) | ||
587 | y1 += FRACUNIT; // don't side exactly on a line | ||
588 | |||
589 | trace.x = x1; | ||
590 | trace.y = y1; | ||
591 | trace.dx = x2 - x1; | ||
592 | trace.dy = y2 - y1; | ||
593 | |||
594 | x1 -= bmaporgx; | ||
595 | y1 -= bmaporgy; | ||
596 | xt1 = x1>>MAPBLOCKSHIFT; | ||
597 | yt1 = y1>>MAPBLOCKSHIFT; | ||
598 | |||
599 | x2 -= bmaporgx; | ||
600 | y2 -= bmaporgy; | ||
601 | xt2 = x2>>MAPBLOCKSHIFT; | ||
602 | yt2 = y2>>MAPBLOCKSHIFT; | ||
603 | |||
604 | if (xt2 > xt1) | ||
605 | { | ||
606 | mapxstep = 1; | ||
607 | partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1)); | ||
608 | ystep = FixedDiv (y2-y1,D_abs(x2-x1)); | ||
609 | } | ||
610 | else | ||
611 | if (xt2 < xt1) | ||
612 | { | ||
613 | mapxstep = -1; | ||
614 | partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1); | ||
615 | ystep = FixedDiv (y2-y1,D_abs(x2-x1)); | ||
616 | } | ||
617 | else | ||
618 | { | ||
619 | mapxstep = 0; | ||
620 | partial = FRACUNIT; | ||
621 | ystep = 256*FRACUNIT; | ||
622 | } | ||
623 | |||
624 | yintercept = (y1>>MAPBTOFRAC) + FixedMul(partial, ystep); | ||
625 | |||
626 | if (yt2 > yt1) | ||
627 | { | ||
628 | mapystep = 1; | ||
629 | partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1)); | ||
630 | xstep = FixedDiv (x2-x1,D_abs(y2-y1)); | ||
631 | } | ||
632 | else | ||
633 | if (yt2 < yt1) | ||
634 | { | ||
635 | mapystep = -1; | ||
636 | partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1); | ||
637 | xstep = FixedDiv (x2-x1,D_abs(y2-y1)); | ||
638 | } | ||
639 | else | ||
640 | { | ||
641 | mapystep = 0; | ||
642 | partial = FRACUNIT; | ||
643 | xstep = 256*FRACUNIT; | ||
644 | } | ||
645 | |||
646 | xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep); | ||
647 | |||
648 | // Step through map blocks. | ||
649 | // Count is present to prevent a round off error | ||
650 | // from skipping the break. | ||
651 | |||
652 | mapx = xt1; | ||
653 | mapy = yt1; | ||
654 | |||
655 | for (count = 0; count < 64; count++) | ||
656 | { | ||
657 | if (flags & PT_ADDLINES) | ||
658 | if (!P_BlockLinesIterator(mapx, mapy,PIT_AddLineIntercepts)) | ||
659 | return false; // early out | ||
660 | |||
661 | if (flags & PT_ADDTHINGS) | ||
662 | if (!P_BlockThingsIterator(mapx, mapy,PIT_AddThingIntercepts)) | ||
663 | return false; // early out | ||
664 | |||
665 | if (mapx == xt2 && mapy == yt2) | ||
666 | break; | ||
667 | |||
668 | if ((yintercept >> FRACBITS) == mapy) | ||
669 | { | ||
670 | yintercept += ystep; | ||
671 | mapx += mapxstep; | ||
672 | } | ||
673 | else | ||
674 | if ((xintercept >> FRACBITS) == mapx) | ||
675 | { | ||
676 | xintercept += xstep; | ||
677 | mapy += mapystep; | ||
678 | } | ||
679 | } | ||
680 | |||
681 | // go through the sorted list | ||
682 | return P_TraverseIntercepts(trav, FRACUNIT); | ||
683 | } | ||